The Lightning Network (LN) utilizes gossip to share network topology, channel announcements and updates, and node announcements among its local constituents. Yet, our measurements show that this flooding-based gossip reconciliation is fundamentally inefficient. We propose, instead, to use set reconciliation protocols for sharing this information, and we systematically evaluate existing approaches under realistic network conditions. We further propose ADAPTIVEIBLT, a novel adaptive IBLT (Invertible Bloom Lookup Table) protocol with a partial-decoding enhancement. By simulating reconciliation in Core-Lightning and evaluating real gossip snapshots, we demonstrate the practical benefits of reconciliation in scaling gossip reconciliation from hours down to a few minutes.

Accurate root cause analysis plays a key role for developing mitigation strategies and understanding attack paths. Many security analysis tools rely on threat databases to accurately report information related to vulnerabilities, such as root cause weaknesses or affected platforms. However, these databases are not entirely correct, with many instances of missing or erroneous information linked to vulnerabilities. This paper presents a method for automated correction of invalid Common Weakness Enumeration (CWE) mappings of Common Vulnerability and Exposure (CVE) entries in the National Vulnerability Database (NVD), which can also be applied to other threat databases. We systematically investigate the prevalence of incorrect or missing root-cause mappings, revealing that more than half of CVEs are linked to invalid or insufficiently detailed CWEs, particularly those categorized as Prohibited or Discouraged. Through a longitudinal analysis of the NVD, we detect trends in manual updates to CVE-CWE mappings and show how these can inform predictions for future corrections. We develop and present FixV2W, an automated correction method that uses a Knowledge Graph embedding model to predict and rank best-fitting CWE matches for correcting previously invalid CVE-CWE mappings. We evaluate FixV2w using invalid mappings that were subsequently corrected by the NVD. Notably, focusing on the top-10 ranked answers for correcting prohibited mappings, we show that FixV2W finds the correct CWE in 65% of the cases, and a candidate within the same branch as the correct CWE in 93% of the cases. Moreover, most of the correct mappings appear at the first or second ranks.

Timeseries monitoring systems such as Prometheus play a crucial role in gaining observability of the underlying system infrastructure. These systems collect timeseries metrics from various system components and perform monitoring queries over periodic window-based aggregations (i.e., rule queries). However, despite wide adoption, the operational costs and query latency of rule queries remain high. In this paper, we identify major bottlenecks associated with repeated data scans and query computations concerning window overlaps in rule queries, and present PromSketch, an approximation-first query framework as intermediate caches for monitoring systems. It enables low operational costs and query latency, by combining approximate window-based query frameworks and sketch-based precomputation. PromSketch is implemented as a standalone module that can be integrated into Prometheus and VictoriaMetrics, covering 70% of Prometheus' aggregation over time queries. Our evaluation shows that PromSketch achieves up to a two-order-of-magnitude reduction in query latency over Prometheus and VictoriaMetrics, while lowering operational dollar costs of query processing by three orders of magnitude compared to Prometheus and by at least 4× compared to VictoriaMetrics with at most 5% average errors across statistics.

We conduct a longitudinal study of the National Vulnerability Database (NVD), focusing on the mappings between vulnerabilities (CVEs) and weaknesses (CWEs).Surprisingly, the study reveals that a significant portion of CVEs, fluctuating between 15% and 30% over the years, lack proper CWE mapping, and that almost 40% of the updates are non-informative.We introduce a methodology, based on knowledge graphs, for automating root cause weakness mapping for CVEs and for fixing existing inaccurate mappings.We showcase promising preliminary results toward this end.

Methods for promoting flexible use of the radio frequency spectrum in microwave radiometry are examined in order to assess the potential for future spectrum sharing paradigms. Results are shown that suggest that geophysical product retrieval performance can be maintained under a variety of channel frequencies and bandwidths.

The rapid growth of the Internet of Things (IoT) has resulted in an array of competing, largely incompatible wireless communication technologies. This plethora of technologies has resulted in a complex landscape, notably a lack of visibility, making it difficult for organizations to come up with appropriate policies and tools to secure their operational environments. In this article, we presentIoT-Scan, a holistic approach for IoT network reconnaissance to enable enumeration of IoT devices in one’s organization.IoT-Scanis based on software-defined radio (SDR) technology, which allows for a flexible software-based implementation of radio protocols. We present a series of passive, active, multichannel, and multiprotocol scanning algorithms to speed up the discovery of devices withIoT-Scan. We benchmark the passive scanning algorithms against a theoretical traffic model based on the nonuniform coupon collector problem. We implement the scanning algorithms for four popular IoT protocols: 1) ZigBee; 2) Bluetooth LE; 3) Z-Wave; and 4) LoRa. Through extensive experiments with dozens of IoT devices, we evaluate and compare the performance of the various algorithms in terms of their discovery time, packet loss, and energy consumption. Notably, using multiprotocol scanning, we demonstrate a reduction of 70% in the discovery times of Bluetooth and ZigBee devices in the 2.4-GHz band and of LoRa and Z-Wave devices in the 900-MHz band, compared to sequential passive scanning.

Space-Air-Ground Integrated Networks will facilitate seamless user experiences across a variety of 6G applications. The deployment of these networks will necessitate new approaches to spectrum allocation. Spectrum access by passive microwave sensors for earth-based and space-based scientific applications represents a spectrum use application having unique attributes that motivate consideration of spectrum sharing between these “incumbents” and commercial users to ensure the most efficient utilization of available frequencies across applications. Toward this end, we propose an economic framework where incumbents have priority use, with a primary and secondary commercial tier underneath. For commercial users, the option to join the primary tier is based on a model of short term post-paid leases of spectrum, while the secondary tier is available to join at no cost. Using a joint game-theoretic and queuing-theoretic model, we find that for practical parameters the revenue maximizing equilibrium is: 1) stable in the Evolutionary Stable Strategy sense; 2) associated with the maximum priority upgrade fee customers are willing to pay; 3) associated with an equilibrium where all customers wish to join the priority class; and 4) socially optimal. We validate our findings leveraging trace data from satellite radiometers operating in the vicinity of Boston, Massachusetts.

Security assessment relies on public information about products, vulnerabilities, and weaknesses. So far, databases in these categories have rarely been analyzed in combination. Yet, doing so could help predict unreported vulnerabilities and identify common threat patterns. In this article, we propose a methodology for producing and optimizing a knowledge graph that aggregates knowledge from common threat databases (CVE, CWE, and CPE). We apply the threat knowledge graph to predict associations between threat databases, specifically between products, vulnerabilities, and weaknesses. We evaluate the prediction performance both in closed world with associations from the knowledge graph and in open world with associations revealed afterward. Using rank-based metrics (i.e., Mean Rank, Mean Reciprocal Rank, and Hits@N scores), we demonstrate the ability of the threat knowledge graph to uncover many associations that are currently unknown but will be revealed in the future, which remains useful over different time periods. We propose approaches to optimize the knowledge graph and show that they indeed help in further uncovering associations. We have made the artifacts of our work publicly available.

Emerging V2X technology enables vehicles to exchange messages with each other (V2V) and with signaling infrastructure (I2V) on the roadways. Information propagation in transportation networks is highly influenced by both vehicle mobility and wireless communication. As for vehicle mobility, realistic traffic flow changes with time, exhibiting sharp time-triggered transitions, due to external factors such as traffic lights. Thus, mobility process is temporally heterogeneous and not smooth, which fundamentally alters the dynamics of V2X (V2V and I2V together) message propagation in a complex manner. As for wireless communication, communication heterogeneity is an integral component of V2X systems - different types of vehicles may have different communication capabilities, and V2V and I2V communications coexist. We propose a mathematical framework, based on a continuous-time Markov chain (CTMC), for characterizing the spatio-temporal spread of V2X information (1) when the traffic flow exhibits sharp time-triggered transitions and (2) when there exists communication heterogeneity comprising of different V2V commutation capabilities, different wireless communication conditions, and both V2V and I2V. We prove that the state evolutions under the CTMC model converge to a set of differential equations in the asymptotic limit of a large number of vehicles, enabling computations that gracefully scale with increase in network size and the number of vehicles. Our framework can accommodate arbitrary traffic synchronization patterns corresponding for example to incorporate the presence of an arbitrary number of traffic signals. Furthermore, numerical computations using this mathematical framework answer several questions that influence the practice of V2X network design and security.

Synchronization of transaction pools (mempools) has shown potential for improving the performance and block propagation delay of state-of-the-art blockchains. Indeed, various heuristics have been proposed in the literature to this end, all of which incorporate exchanges of unconfirmed transactions into their block propagation protocol. In this work, we take a different approach, maintaining transaction synchronization outside (and independently) of the block propagation channel. In the process, we formalize the synchronization problem within a graph theoretic framework and introduce a novel algorithm (SREP - Set Reconciliation-Enhanced Propagation) with quantifiable guarantees. We analyze the algorithm's performance for various realistic network topologies, and show that it converges on any connected graph in a number of steps that is bounded by the diameter of the graph. We confirm our analytical findings through extensive simulations that include comparison with MempoolSync, a recent approach from the literature. Our simulations show that SREP incurs reasonable overall bandwidth overhead and, unlike MempoolSync, scales gracefully with the size of the network.

Random jammers that overpower transmitted signals are a practical concern for many wireless communication protocols. As such, wireless receivers must be able to cope with standard channel noise and jamming (intentional or unintentional). To address this challenge, we propose a novel method to augment the resilience of the recent family of universal error-correcting GRAND algorithms. This method, called Erasure Decoding by Gaussian Elimination (EDGE), impacts the syndrome check block and is applicable to any variant of GRAND. We show that the proposed EDGE method naturally reverts to the original syndrome check function in the absence of erasures caused by jamming. We demonstrate this by implementing and evaluating GRAND-EDGE and ORBGRAND-EDGE. Simulation results, using a Random Linear Code (RLC) with a code rate of 105/128, show that the EDGE variants lower both the Block Error Rate (BLER) and the computational complexity by up to five order of magnitude compared to the original GRAND and ORBGRAND algorithms. We further compare ORBGRAND-EDGE to Ordered Statistics Decoding (OSD), and demonstrate an improvement of up to three orders of magnitude in the BLER.

The plethora of Internet of Things (IoT) protocols and the upcoming availability of new spectrum bands for wirelessly connected devices have made software-defined radio (SDR) technology increasingly useful to interact with radio-based communication. While SDR-based tools have grown in popularity in recent years due to their flexibility and adaptability towards new protocols, SDR software interfaces remain highly complex and technical, and inherently require specialized skillsets in digital signal processing (DSP) to operate. To address this problem, we present Snout, an SDR middleware platform that encapsulates and abstracts much of the current complexity in SDR toolchains. This allows SDR developers to create wireless networking applications usable by a wide range of users. For instance, network security professionals can monitor the IoT landscape across multiple protocols without needing to interact with the underlying software-defined DSP. Snout implements interfaces with common network analysis tools to allow for integration with traditional network security solutions, facilitating use cases such as traffic analysis or rogue device detection. Its software architecture enables scalability in terms of protocols and processing by modularizing the signal processing pipeline. To demonstrate Snout’s capabilities, we show how it can encapsulate GNU Radio flowgraphs, facilitate simultaneous multi-protocol scanning, and convert existing SDR-based protocol implementations into fully contained applications. We further demonstrate how Snout can handle GNU Radio flowgraphs with other signal processing software simultaneously. Through extensive experiments, we demonstrate that Snout incurs limited CPU performance overhead below 4% and a memory footprint below 100MB, and handles large amounts of events with sub-millisecond latency.

The Citizens Broadband Radio Service (CBRS) is a spectrum sharing framework on the 3.5 GHz tier with three priority tiers: the incumbents, priority commercial users (PAL), and general commercial users (GAA). Thus, commercial users compete for resources within the second and third priority tiers. The interaction between commercial providers and customers is complicated by the presence of the incumbents, who impact the availability of spectrum but bypass the market entirely. In particular, PAL customers are themselves subject to preemption even with the priority purchase. In this paper, we propose a game-theoretic framework to shed light into the equilibrium outcomes and the impact of the incumbents into these. We determine that there exist several possible equilibrium regions, including one with a unique mixed equilibrium which is stable in the evolutionary stable strategy sense, and others featuring unstable mixed equilibria and stable pure equilibria. We show that for fixed parameters, the maximum possible revenue a provider can obtain is associated with a stable equilibrium and is thus guaranteed. However, changes in incumbent behavior can result in phase changes which have a sizable impact on the maximum potential revenue.

In the set reconciliation problem, remote parties seek to reconcile similar sets of data according to an efficiency objective, such as minimizing communication or computation. Though investigated for many individual distributed applications, this problem still lacks a holistic treatment, and this is the aim of this work. Specifically, we design and analyze GenSync, a unified set reconciliation framework that incorporates several state-of-the-art set reconciliation protocols with an integrated testbed. We compare and analyze the various protocols and offer general guidelines for selecting a good protocol for a given application. Through extensive experiments, we demonstrate that the optimal choice of protocol is highly sensitive to several parameters, including network properties (e.g., bandwidth and latency) and computing power. Notably, none of our framework’s protocols are universally dominant under diverse conditions, and a poor protocol choice may lead to a 5x hit in performance. To demonstrate our framework, we measure the effects of protocol choice in reconciling memory pools of adjacent Bitcoin nodes.

Block relay protocols play a key role in the performance and security of public blockchains. As a result, several such protocols have been deployed in the context of Bitcoin and its variants (e.g., legacy, compact block relay and Graphene) in an attempt to reduce bandwidth utilization. However, the relative performance of these protocols in realistic networking conditions (e.g., with nodes churning - joining and leaving the network) is still not known. This paper aims to fill this key knowledge gap using an experimental testbed of twelve full nodes connected to the Bitcoin Cash blockchain. With the aid of novel logging tools, we contrast the performance of these three protocols, in realistic scenarios, with respect to communication, delay, and block decoding success. Our main findings are that Graphene generally performs the best when nodes remain connected, boasting an average propagation delay of 190 ms (i.e., 29% lower than compact block and 80% lower than the legacy protocol). However, when nodes churn at a high rate, compact blocks may perform better. Through a careful temporal analysis, we identify some root causes of the protocol inefficiencies, together with potential mitigation. We have made our measurement framework and experimental logs publicly available to the broader research community.

Orphan transactions are those whose parental income sources are missing at the time that they are processed. These transactions typically languish in a local buffer until they are evicted or all their parents are discovered, at which point they may be propagated further. To date, there has been little work in the literature on characterizing the nature and impact of such orphans, and yet it is intuitive that they should affect the performance of the Bitcoin network. This work thus seeks to methodically research such effects through a measurement campaign on live Bitcoin nodes. Our data show that about 45% of orphan transactions end up being included in the blockchain. Surprisingly, orphan transactions tend to have fewer parents on average than non-orphan transactions, and their missing parents have a lower fee, larger size, and lower transaction fee per byte than all other received transactions. Moreover, the network overhead incurred by these orphan transactions can be significant, exceeding 17% when using the default orphan memory pool size (i.e., 100 transactions), although this overhead can be made negligible, without significant computational or memory demands, if the pool size is simply increased to 1000 transactions. Finally, we show that when a node with an empty mempool first joins the network, 25% of the transactions that it receives become orphan, whereas in steady-state this quantity drops to about 1%.

Efficient and reliable propagation of blocks is vital to the scalability of the Bitcoin network. As a result, several schemes, such as the compact block protocol (BIP 152), have been proposed over the last few years to speed up the block propagation. Even so, we provide experimental evidence that (i) the vast majority (97%) of Bitcoin nodes exhibit only intermittent network connectivity (i.e., churn), and (ii) this churn results in significant number of unsuccessful compact blocks, roughly three times the statistic for continuously connected nodes. We conduct experiments on the Bitcoin network that show that churn results in a roughly five fold increase in block propagation time (i.e., 566.89 ms vs. 109.31 ms) on average. To effect our analysis, we develop a statistical model for churn, based on empirical network data, and use this model to actuate live test nodes on the Bitcoin network. The performance of the system is measured within a novel framework that we developed for logging the internal behavior of a Bitcoin node, and which we share for public use. Finally, to mitigate the problem of missing transactions in churning nodes, we propose and implement into Bitcoin Core a new synchronization protocol, dubbed MempoolSync. Our measurements show that churning nodes implementing MempoolSync experience significantly better performance than standard nodes not implementing MempoolSync, including average block propagation delay reduced by over 50%.

Recent work demonstrates that IEEE 802.11 networks are vulnerable to cascading DoS attacks, wherein a single node can remotely and suddenly congest an entire network. In this paper, we propose, analyze, simulate, and experimentally verify a counter-measure against such attacks. Our main idea is to optimize the duration of packet transmissions in order to weaken coupling effects between neighboring pairs of nodes. Toward that end, we propose a new theoretical model that relates the utilization of neighboring pairs of nodes using a sequence of iterative equations. The model captures important specifications of the IEEE 802.11 MAC layer. Through a fixed point analysis of the sequence, we show how to optimally set the packet duration so that, on one hand, cascading DoS attacks are avoided and, on the other hand, throughput is maximized. We validate the analysis through extensive ns-3 simulations and demonstrate the effectiveness of the mitigation through experiments with real Wi-Fi cards. A key insight is that IEEE 802.11 networks with relatively large MAC overhead are less susceptible to cascading DoS attacks than networks with smaller MAC overhead.

We present and evaluate Truncate-after-Preamble (TaP) attacks, whereby a receiver cannot decode an incoming signal despite good channel conditions. In a TaP attack, the attacker announces a large payload length using a standard preamble and packet length field, but omits to transmit the payload. We implement the TaP attack on a SDR platform, and evaluate the effectiveness of the attack on five Zigbee and seven Wi-Fi devices sold by different manufacturers. We show that all of the Zigbee devices are vulnerable to the attack, while the Wi-Fi devices are vulnerable to the attack to varying degrees. Chiefly, we show that an attacker can cause over 90% packet loss on a Zigbee or Wi-Fi channel, using respectively six or five orders of magnitude less energy than a constant jammer would. Finally, we present several methods, with different degrees of sophistication, for detecting the attacks.

Network mapping tools designed for IP-based networks generally do not provide access to non-IP based wireless protocols used by Internet of Things (IoT) devices, such as Zigbee and Bluetooth LE. We present Snout, a versatile and extensible software defined radio-based tool for IoT network mapping and penetration testing. Snout is geared towards the various IoT protocols that are not accessible with traditional network enumeration tools, such as Nmap. The tool allows for device enumeration, vulnerability assessment, as well as more offensive techniques such as packet replay and spoofing, which we demonstrate for the Zigbee protocol. Snout is built on an open-source stack, and is designed for extensibility towards other IoT protocols and capabilities.

Many performance characteristics of wireless devices are fundamentally influenced by their vendor-specific physical layer implementation. Yet, characterizing the physical layer behavior of wireless devices usually requires complex testbeds with expensive equipment, making such behavior inaccessible and opaque to the end user. In this work, we propose and implement a new testbed architecture for software-defined radio-based wireless device performance benchmarking. The testbed is capable of accessing and measuring physical layer protocol features of real wireless devices. The testbed further allows tight control of timing events, at a microsecond time granularity. Using the testbed, we measure the receiver sensitivity and signal capture behavior of Wi-Fi devices from different vendors. We identify marked differences in their performance, including a variation of as much as 20 dB in their receiver sensitivity. We further assess the response of the devices to truncated packets and show that this procedure can be employed to fingerprint the devices.

Location spoofing is a proven and powerful attack against Vehicle-to-everything (V2X) communication systems that can cause traffic congestion and other safety hazards. Recent work also demonstrates practical spoofing attacks that can circumvent application layer sanity checks. In this paper, we propose three novel physical layer plausibility checks that leverage the received signal strength indicator (RSSI) of basic safety messages (BSMs). These plausibility checks have multi-step mechanisms to improve not only the detection rate, but also to decrease false positives. These checks can be run independently by each vehicle and do not rely on the assumption that the majority of vehicles is honest. We comprehensively evaluate the performance of these plausibility checks using the VeReMi dataset (which we enhance along the way) for several types of attacks. We show that the best performing physical layer plausibility check among the three considered achieves an overall detection rate of 83.73% and a precision of 95.91%, far outperforming recently proposed machine learning-based misbehavior detection methods operating at the application layer.

Abstract Bluetooth Low Energy (BLE) devices use public (non-encrypted) advertising channels to announce their presence to other devices. To prevent tracking on these public channels, devices may use a periodically changing, randomized address instead of their permanent Media Access Control (MAC) address. In this work we show that many state-of-the-art devices which are implementing such anonymization measures are vulnerable to passive tracking that extends well beyond their address randomization cycles. We show that it is possible to extract identifying tokens from the pay-load of advertising messages for tracking purposes. We present an address-carryover algorithm which exploits the asynchronous nature of payload and address changes to achieve tracking beyond the address randomization of a device. We furthermore identify an identity-exposing attack via a device accessory that allows permanent, non-continuous tracking, as well as an iOS side-channel which allows insights into user activity. Finally, we provide countermeasures against the presented algorithm and other privacy flaws in BLE advertising.

With the emergence of connected and autonomous vehicles, sensors are increasingly deployed within cars to support new functionalities. Traffic generated by these sensors congest traditional intra-car networks, such as CAN buses. Furthermore, the large amount of wires needed to connect sensors makes it harder to design cars in a modular way. To alleviate these limitations, we propose, simulate, and implement a hybrid wired/wireless architecture, in which each node is connected to either a wired interface or a wireless interface or both. Specifically, we propose a new protocol, called Hybrid-Backpressure Collection Protocol (Hybrid-BCP), to efficiently collect data from sensors in intra-car networks. Hybrid-BCP is backward-compatible with the CAN bus technology, and builds on the BCP protocol, designed for wireless sensor networks. We theoretically prove that an idealized version of Hybrid-BCP achieves optimal throughput. Our testbed implementation, based on CAN and ZigBee transceivers, demonstrates the load balancing and routing functionalities of Hybrid-BCP and its resilience to DoS attacks and wireless jamming attacks. We further provide simulation results, obtained with the ns-3 simulator and based on real intra-car RSSI traces, that compare between the performance of Hybrid-BCP and a tree-based data collection protocol. Notably, the simulations show that Hybrid-BCP outperforms the tree-based protocol on throughput by 12 percent. The results also show that Hybrid-BCP maintains high packet delivery rate and low packet delay for safety-critical sensors that are directly connected to the sink through wire.

Recent work shows that an adversary can exploit a coupling effect induced by hidden nodes to launch a cascading attack causing global congestion in a Wi-Fi network. The underlying assumption is that the power of interference caused by a hidden node is an order of magnitude stronger than the signal sent to the receiver. In this paper, we investigate the feasibility of cascading attacks with weakly interfering hidden nodes, that is when the signal-to-interference ratio is high. Through extensive ns-3 simulations, including for an indoor building model, we show that cascading attacks are still feasible. The attacks leverage two PHY-layer phenomena: receiver capture and bit rate adaptation. We show that the attack relies on a coupling effect, whereby the average bit rate of a transmission pair drops sharply as the channel utilization of a neighboring pair gets higher. This coupling effect facilitates the propagation of the attack throughout the network.

The Controller Area Network (CAN) is a shared medium, priority-based communication protocol, widely used in the automotive industry for interconnecting electrical components. Although allowing messages to take priority over others in accessing the shared medium is naturally desirable for vehicular applications, it also provides a vulnerability for Denial-of-Service (DoS) attacks. This paper studies the impact of such priority- based DoS attacks and proposes a mitigating scheme. We find that implementation details have a significant impact on the efficiency of priority- based DoS attacks. Nevertheless, with a proper configuration, a single attacker can block an entire CAN network and deem it unusable. To mitigate this problem, we propose integrating a wireless interface and design a hybrid wired/wireless protocol that schedules packet transmissions on the wired and wireless links. Our testbed results show that the hybrid wired/wireless protocol improves the throughput under a two-node DoS attack by a factor of four. Additional experimental results demonstrate that our hybrid wired/wireless protocol is robust to jamming attacks on the wireless link.

This paper characterizes the outcomes of secondary spectrum markets when multiple providers compete for secondary demand. We study a competition model in which each provider aims to enhance its revenue by opportunistically serving a price-dependent secondary demand, while also serving dedicated primary demand. We consider two methodologies for sharing spectrum between primary and secondary demand: In coordinated access, spectrum providers have the option to decline a secondary access request if that helps enhance their revenue. We explicitly characterize a break-even price such that profitability of secondary access provision is guaranteed if secondary access is priced above the break-even price, regardless of the volume of secondary demand. Consequently, we establish that competition among providers that employ optimal coordinated access leads to a price war, as a result of which the provider with the lowest break-even price captures the entire market. This result holds for arbitrary secondary demand functions. In uncoordinated access, primary and secondary users share spectrum on equal basis, akin to ISM bands. Under this policy, we characterize a market sharing price that determines a provider's willingness to share the market. We show an instance where the market sharing price is strictly greater than the break-even price, indicating that market equilibrium in an uncoordinated access setting can be fundamentally different as it opens up the possibility of providers sharing the market at higher prices.

In recent years cybersecurity has gained prominence as a field of expertise and the relevant practical skills are in high demand. To reduce the cost and amount of dedicated hardware required to set up a cybersecurity lab to teach those skills, several virtualization and outsourcing approaches were developed but the resulting setup has often increased in total complexity, hampering adoption. In this paper we present a very simple (and therefore highly scalable) setup that incorporates state-of-the-art industry tools. We also describe a structured set of lab assignments developed for this setup that build one on top of the other to cover the material of a semester-long Cybersecurity course taught at Boston University. We explore alternative lab architectures, discuss other existing sets of lab assignments and present some ideas for further improvement.

We present TeaCP, a prototype toolkit for the evaluation and analysis of collection protocols in both simulation and experimental environments running on TinyOS. Our toolkit consists of a testing system, which runs a collection protocol of choice, and an optional SD card-based logging system, which stores the logs generated by the testing system. The SD card datalogger allows a wireless sensor network (WSN) to be deployed flexibly in various environments, especially where wired transfer of data is difficult. Using the saved logs, TeaCP evaluates a wide range of performance metrics, such as reliability, throughput, and delay. TeaCP further allows visualization of packet routes and the topology evolution of the network, under both static and dynamic conditions, even in the face of transient disconnections. Through simulation of an intra-car WSN and real lab experiments, we demonstrate the functionality of TeaCP for comparing the performance of two prominent collection protocols, the Collection Tree Protocol (CTP) and the Backpressure Collection Protocol (BCP). We also present the usage of TeaCP as a high level diagnosis tool, through which an inconsistency of the BCP implementation for the CC2420 radio chips is identified and resolved.

We introduce a private commons model that consists of network providers who serve a fixed primary demand and strategically price to improve their revenues from an additional secondary demand. For general forms of secondary demand, we establish the existence and uniqueness of two characteristic prices: the break-even price and the market sharing price. We show that the market sharing price is always greater than the break-even price, leading to a price interval in which a provider is both profitable and willing to share the demand. Making use of this result, we give insight into the nature of market outcomes.

We experimentally investigate the benefits of multi- hop networking for intra-car data aggregation under the current state-of-the-art Collection Tree Protocol (CTP). We show how this protocol actively adjusts collection routes according to channel dynamics in various practical car environments, resulting in performance gains over single-hop aggregation. Throughout our experiments, we target traditional performance metrics such as delivery rate, number of transmissions per packet, and delay, and our results confirm, both qualitatively and quantitatively, that multi-hop communication can provide a reliable and robust approach for data collection within a car.

We investigate profitability from secondary spectrum provision under unknown relationships between price charged for spectrum use and demand drawn at the given price. We show that profitability is governed by the applied admission policy and the price charged to secondary users. We explicitly identify a critical price (market entry price) such that if secondary demand is charged below that price, the licensee endures losses from spectrum provision, regardless of the applied admission policy. Furthermore, we show that an admission policy that admits secondary demand only when no channel is occupied is profitable for any price that exceeds the critical price. We prove that this policy is profit-robust to variations in secondary demand, i.e., if the policy is profitable for a certain price, it will be profitable for any secondary demand that the price generates, as long as the price generates demand. We also investigate profitability from a set of policies that allow more secondary users to access spectrum by defining the number of users that can be concurrently served. Our results demonstrate profit-robustness of these policies and explicitly characterize profitable prices. We provide a numerical study to verify our theoretical findings.

Recent experimental studies reveal that several well-known and widely deployed rate adaptation algorithms (RAAs) in 802.11 WLANs are vulnerable to selective jamming attacks. However, previous work resorts to complex jamming strategies that are hard to implement and does not provide applicable solutions to this problem. In this work, we analyze the vulnerabilities of existing RAAs to simple jamming attacks and propose judicious use of randomization to address this problem. We introduce a theoretical framework based on a bursty periodic jamming model to analyze the vulnerabilities of popular RAAs, such as ARF and SampleRate. Our parameterized analysis shows that a jamming rate of 10% or below is sufficient to bring the throughput of these algorithms below the base rate of 1 Mb/s. Thereafter, we propose Randomized ARF (RARF), which has higher resistance to jamming attacks. We derive a closed-form lower bound on the minimum jamming rate required to keep the RARF throughput below the base rate. Finally, we conduct ns-3 simulations implementing various RAAs and jamming strategies for an IEEE 802.11g WLAN. Our simulations validate jamming strategies under different channel models and show that the minimum jamming rate required against RARF is about 33%.

We consider a wireless provider who caters to two classes of customers, namely primary users (PUs) and secondary users (SUs). PUs have long term contracts while SUs are admitted and priced according to current availability of excess spectrum. The average rate at which SUs attempt to access the spectrum is a function on the currently advertised price, referred to as the demand function. We analyze the problem of maximizing the average profit gained by admissions of SUs, when the demand function is unknown. We introduce a new on-line algorithm, called Measurement-based Threshold Pricing (MTP), that requires the optimization of only two parameters, a price and a threshold, whereby SU calls are admitted and charged a fixed price when the channel occupancy is lower than the threshold and rejected otherwise. At each iteration, MTP measures the average arrival rate of SUs corresponding to a certain test price. We prove that these measurements of the secondary demand are sufficient for MTP to converge to a local optimal price and corresponding optimal threshold, within a number of measurements that is logarithmic in the total number of possible prices. We further provide an adaptive version of MTP that adjusts to time-varying demand and establish its convergence properties. We conduct numerical studies showing the convergence of MTP to near-optimal online profit and its superior performance over a traditional reinforcement learning approach.

We consider the problem of generating a connected identifying code for an arbitrary graph. After a brief motivation, we show that the decision problem regarding the existence of such a code is NP-complete, and we propose a novel polynomial-time approximation ConnectID that transforms any identifying code into a connected version of at most twice the size, thus leading to an asymptotically optimal approximation bound. When the input identifying code to is robust to graph distortions, we show that the size of the resulting connected code is related to the best error-correcting code of a given minimum distance, permitting the use of known coding bounds. In addition, we show that the size of the input and output codes converge for increasing robustness, meaning that highly robust identifying codes are almost connected. Finally, we evaluate the performance ConnectID of on various random graphs. Simulations for Erdos-Rényi random graphs show that the connected codes generated are actually at most 25% larger than their unconnected counterparts, while simulations with robust input identifying codes confirm that robustness often provides connectivity for free.

Delay-tolerant network (DTN) architectures have recently been proposed as a means to enable efficient routing of messages in vehicular area networks (VANETs), which are characterized by alternating periods of connectivity and disconnection. Under such architectures, when multihop connectivity is available, messages propagate at the speed of radio over connected vehicles. On the other hand, when vehicles are disconnected, messages are carried by vehicles and propagate at vehicle speed. Our goal in this paper is to analytically determine what gains are achieved by DTN architectures and under which conditions, using the average message propagation speed as the primary metric of interest. We develop an analytical model for a bidirectional linear network of vehicles, as found on highways. We derive both upper and lower bounds on the average message propagation speed by exploiting a connection with the classical pattern-matching problem in probability theory. The bounds reveal an interesting phase transition behavior. Specifically, we find out that, below a certain critical threshold, which is a function of the traffic density in each direction, the average message speed is the same as the average vehicle speed, i.e., DTN architectures provide no gain. On the other hand, we determine another threshold above which the average message speed quickly increases as a function of traffic density and approaches radio speed. Based on the bounds, we also develop an approximation model for the average message propagation speed that we validate through numerical simulations.

We examine the problem of minimizing feedback in reliable wireless broadcasting by pairing rateless coding with extreme value theory. Our key observation is that, in a broadcast environment, this problem resolves into estimating the maximum number of packets dropped among many receivers rather than for each individual receiver. With rateless codes, this estimation relates to the number of redundant transmissions needed at the source in order for all receivers to correctly decode a message with high probability. We develop and analyze two new data dissemination protocols, called Random Sampling (RS) and Full Sampling with Limited Feedback (FSLF), based on the moment and maximum likelihood estimators in extreme value theory. Both protocols rely on a single-round learning phase, requiring the transmission of a few feedback packets from a small subset of receivers. With fixed overhead, we show that FSLF has the desirable property of becoming more accurate as the receivers' population gets larger. Our protocols are channel-agnostic, in that they do not require a priori knowledge of (i.i.d.) packet loss probabilities, which may vary among receivers. We provide simulations and an improved full-scale implementation of the Rateless Deluge over-the-air programming protocol on sensor motes as a demonstration of the practical benefits of our protocols, which translate into about 30% latency and energy consumption savings. Furthermore, we apply our protocols to real-time (RT) oblivious rateless codes in broadcast settings. Through simulations, we demonstrate a 100-fold reduction in the amount of feedback packets while incurring an increase of only 10%–20% in the number of encoded packets transmissions.

No abstract available.

Our project demonstrates the capabilities of a symbiotic phone-robot hybrid device, wherein the robot provides gross motor control and the phone provides fine course corrections and sensing capability. The crude robot generates movement subject to mechanical wheel asymmetries and non-linear motor effects; the inexpensive phone provides a variety of on-board sensors and a reasonably powerful CPU/memory. We demonstrate the utility of the combined device to provide a reasonably accurate autonomous signal mapping on an untrained floor plan in our building.

Identifying codes have been proposed as an abstraction for implementing monitoring tasks such as indoor localization using wireless sensor networks. In this approach, sensors' radio coverage overlaps in unique ways over each identifiable region, according to the codewords of an identifying code. While connectivity of the underlying identifying code is necessary for routing data to a sink, existing algorithms that produce identifying codes do not guarantee such a property. As such, we propose a novel polynomial-time algorithm called ConnectID that transforms any identifying code into a connected version that is also an identifying code and is provably at most twice the size of the original. We evaluate the performance of ConnectID on various random graphs, and our simulations show that the connected codes generated are actually at most 25% larger than their non-connected counterparts.

We investigate, both theoretically and experimentally, the stability of CSMA-based wireless mesh networks, where a network is said to be stable if and only if the queue of each relay node remains (almost surely) finite. We identify two key factors that impact stability: the network size and the so-called “stealing effect,” a consequence of the hidden-node problem and nonzero transmission delays. We consider the case of a greedy source and prove, by using Foster's theorem, that three-hop networks are stable, but only if the stealing effect is accounted for. We also prove that four-hop networks are, on the contrary, always unstable (even with the stealing effect) and show by simulations that instability extends to more complex linear and nonlinear topologies. To tackle this instability problem, we propose and evaluate a novel, distributed flow-control mechanism called EZ-flow. EZ-flow is fully compatible with the IEEE 802.11 standard (i.e., it does not modify headers in packets), can be implemented using off-the-shelf hardware, and does not entail any communication overhead. EZ-flow operates by adapting the minimum congestion window parameter at each relay node, based on an estimation of the buffer occupancy at its successor node in the mesh. We show how such an estimation can be conducted passively by taking advantage of the broadcast nature of the wireless channel. Real experiments, run on a nine-node test-bed deployed over four different buildings, show that EZ-flow effectively smooths traffic and improves delay, throughput, and fairness performance.

In response to the high throughput needs of grid and cloud computing applications, several production networks have recently started to support advance reservation of dedicated circuits. An important open problem within this context is to devise advance reservation algorithms that can provide provable throughput performance guarantees independently of the specific network topology and arrival pattern of reservation requests. In this paper, we first show that the throughput performance of greedy approaches, which return the earliest possible completion time for each incoming request, can be arbitrarily worse than optimal. Next, we introduce two new online, polynomial-time algorithms for advance reservation, called BatchAll and BatchLim. Both algorithms are shown to be throughput-optimal through the derivation of delay bounds for 1 + ε bandwidth augmented networks. The BatchLim algorithm has the advantage of returning the completion time of a connection immediately as a request is placed, but at the expense of looser delay performance than BatchAll. We then propose a simple approach that limits path dispersion, i.e., the number of parallel paths used by the algorithms, while provably bounding the maximum reduction factor in the transmission throughput. We prove that the number of paths needed to approximate any flow is quite small and never exceeds the total number of edges in the network. Through simulation for various topologies and traffic parameters, we show that the proposed algorithms achieve reasonable delay performance, even at request arrival rates close to capacity bounds, and that three to five parallel paths are sufficient to achieve near-optimal performance.

We consider a wireless provider who caters to two classes of customers, namely primary and secondary users. Primary users have long term contracts while secondary users are admitted and priced according to current availability of excess spectrum. Secondary users accept an advertised price with a certain probability defined by an underlying demand function. We analyze the problem of maximizing profit gained by admission of secondary users. Previous studies in the field usually assume that the demand function is known and that the call length distribution is also known and exponentially distributed. In this paper, we analyze more realistic settings where both of these quantities are unknown. Our main contribution is to derive near-optimal pricing strategies under such settings. We focus on occupancy-based pricing policies, which depend only on the total number of ongoing calls in the system. We first show that such policies are insensitive to call length distribution except through the mean. Next, we introduce a new on-line, occupancy-based pricing algorithm, called Measurement-based Threshold Pricing (MTP) that operates by measuring the reaction of secondary users to a specific price and does not require the demand function to be known. MTP optimizes a profit function that depends on price only. We prove that while the profit function can be multimodal, MTP converges to one of the local optima as fast as if the function were unimodal. Lastly, we provide numerical studies demonstrating the near-optimal performance of occupancy-based policies for diverse sets of call length distributions and demand functions and the quick convergence of MTP to near-optimal on-line profit.

We examine the problem of minimizing feedbacks in reliable wireless broadcasting, by pairing rateless coding with extreme value theory. Our key observation is that, in a broadcast environment, this problem resolves into estimating the maximum number of packets dropped among many receivers rather than for each individual receiver. With rateless codes, this estimation relates to the number of redundant transmissions needed at the source in order for all receivers to correctly decode a message with high probability. We develop and analyze two new data dissemination protocols, called Random Sampling (RS) and Full Sampling with Limited Feedback (FSLF), based on the moment and maximum likelihood estimators in extreme value theory. Both protocols rely on a single-round learning phase, requiring the transmission of a few feedback packets from a small subset of receivers. With fixed overhead, we show that FSLF has the desirable property of becoming more accurate as the receivers's population gets larger. Our protocols are channel agnostic, in that they do not require a-priori knowledge of (i.i.d.) packet loss probabilities, which may vary among receivers. We provide simulations and an improved full-scale implementation of the Rateless Deluge over-the-air programming protocol on sensor motes as a demonstration of the practical benefits of our protocols, which translate into about 30% latency and energy consumption savings.

New architectures have recently been proposed and deployed to support end-to-end advance reservation of network resources. These architectures rely on the use a centralized scheduler, which may be unpractical in large or administratively heterogeneous networks. In this work, we explore and demonstrate the feasibility of implementing distributed solutions for advance reservation. We introduce a new distributed, distance-vector algorithm, called Distributed Advance Reservation (DAR), that provably returns the earliest time possible for setting up a connection between any two nodes. Our main findings in this context are the following: (i) we prove that widest path routing and path switching (i.e, allowing a connection to switch between different paths) are necessary to guarantee earliest scheduling; (ii) we propose a novel approach for loop-free distributed widest path routing, leveraging the recently proposed DIV framework. Our routing results directly extend to on-demand QoS routing problems.

The advent of practical rateless codes enables implementation of highly efficient packet-level forward error correction (FEC) strategies for reliable data broadcasting in loss-prone wireless networks, such as sensor networks. Yet, the critical question of accurately quantifying the proper amount of redundancy has remained largely unsolved. In this paper, we exploit advances in extreme value theory to rigorously address this problem. Under the asymptotic regime of a large number of receivers, we derive a closed-form expression for the cumulative distribution function (CDF) of the completion time of file distribution. We show the existence of a phase transition associated with this CDF and accurately locate the transition point. We derive tight convergence bounds demonstrating the accuracy of the asymptotic estimate for the practical case of a finite number of receivers. Further, we asymptotically characterize the CDF of the completion time under heterogeneous packet loss, by establishing a close relationship between the data broadcasting and multi-set coupon collector problems. We demonstrate the benefits of our approach through simulation and through real experiments on a Tmote Sky sensor testbed. Specifically, we augment the existing Rateless Deluge software dissemination protocol with an extreme value FEC strategy. The experimental results reveal reduction by a factor of five in retransmission request messages and by a factor of two in total dissemination time, at the cost of a marginally higher number of data packet transmissions in the order of 5%.

We analyze the performance limits of data dissemination with multichannel, single radio sensors under random packet loss. We formulate the problem of minimizing the average delay of data dissemination as a stochastic shortest path problem and show that, for an arbitrary topology network, an optimal control policy can be found in a finite number of steps, using value iteration or Dijkstra's algorithm. However, the computational complexity of this solution is generally prohibitive. We thus focus on two special classes of network topologies of practical interest, namely single-hop clusters and multihop cluster chains. For these topologies, we derive the structure of policies that achieve an asymptotically optimal average delay, in networks with large number of nodes. Our analysis reveals that a single radio in each node suffices to achieve performance gain directly proportional to the total number of channels available. Through simulation, we show that the derived policies perform close to optimal even for networks with small and moderate numbers of nodes and can be implemented with limited overhead.

Recent analytical and experimental work demonstrate that IEEE 802.11-based wireless mesh networks are prone to turbulence. Manifestations of such turbulence take the form of large buffer build-up at relay nodes, end-to-end delay fluctuations, and traffic congestion. In this paper, we propose and evaluate a novel, distributed flow-control mechanism to address this problem, called EZ-flow. EZ-flow is fully compatible with the IEEE 802.11 standard (i.e., it does not modify headers in packets), can be implemented using off-the-shelf hardware, and does not entail any communication overhead. EZ-flow operates by adapting the minimum congestion window parameter at each relay node, based on an estimation of the buffer occupancy at its successor node in the mesh. We show how such an estimation can be conducted passively by taking advantage of the broadcast nature of the wireless channel. Real experiments, run on a 9-node testbed deployed over 4 different buildings, show that EZ-flow effectively smoothes traffic and improves delay, throughput, and fairness performance. We further corroborate these results with a mathematical stability analysis and extensive ns-2 simulations run for different traffic workloads and network topologies.

The erasure resilience of rateless codes, such as Luby-Transform (LT) codes, makes them particularly suitable to a wide variety of loss-prone wireless and sensor network applications, ranging from digital video broadcast to software updates. Yet, traditional rateless codes usually make no use of a feedback communication channel, a feature available in many wireless settings. As such, we generalize LT codes to situations where receiver(s) provide feedback to the broadcaster. Our approach, referred to as Shifted LT (SLT) code, modifies the robust soliton distribution of LT codes at the broadcaster, based on the number of input symbols already decoded at the receivers. While implementing this modification entails little change to the LT encoder and decoder, we show both analytically and through real experiments, that it achieves significant savings in communication complexity, memory usage, and overall energy consumption. Furthermore, we show that significant savings can be even achieved with a low number of feedback messages (on the order of the square root of the total number of input symbols) transmitted at a uniform rate. The practical benefits of Shifted LT codes are demonstrated through the implementation of a real over-the-air programming application for sensor networks, based on the Deluge protocol.

The advent of practical rateless codes enables implementation of highly efficient packet-level forward error correction (FEC) strategies for reliable data broadcasting in loss-prone wireless networks. Yet, the critical question of accurately quantifying the proper amount of redundancy has remained largely unsolved. In this paper, we exploit advances in extreme value theory to rigorously address this problem. Under the asymptotic regime of a large number of receivers, we derive a closed-form expression for the cumulative distribution function (CDF) of the completion time of file distribution. We show the existence of a phase transition associated with this CDF and accurately locate the transition point. We derive tight convergence bounds demonstrating the accuracy of the asymptotic estimate for the practical case of a finite number of receivers. We also provide an asymptotic closed-form expression on the expected completion time under heterogeneous packet loss. We demonstrate the benefits of our approach through simulation and through real experiments on a testbed of 20 Tmote Sky sensors. Specifically, we augment the existing Rateless Deluge software dissemination protocol with an extreme value FEC strategy. The experimental results reveal reduction by a factor of five in retransmission request messages and by a factor of two in total dissemination time, at the cost of a marginally higher number of data packet transmissions in the order of 5%.

We investigate both theoretically and experimentally the stability of CSMA-based wireless mesh networks, where a network is said to be stable if and only if the queue of each relay node remains (almost surely) finite. We identify two key factors that impact stability: the network size and the so-called "stealing effect", a consequence of the hidden node problem and non-zero propagation delays. We consider the case of a greedy source and prove, by using Foster's theorem, that 3-hop networks are stable, but only if the stealing effect is accounted for. On the other hand, we prove that 4-hop networks are always unstable (even with the stealing effect) and show by simulations that instability extends to more complex linear and non-linear topologies. We devise a stabilization strategy that throttles the source and prove that there exists a finite, non-zero rate at which the source can transmit while keeping the system stable. We run real experiments on a testbed composed of IEEE 802.11 nodes, which show the contrasting behavior of 3-hop and 4-hop networks and the effectiveness of our stabilization strategy.

Network coding and cooperative diversity have each extensively been explored in the literature as a means to substantially improve the performance of wireless networks. Yet, little work has been conducted to compare their performance under a common framework. Our goal in this paper is to fill in this gap. Specifically, we consider a single-hop wireless network consisting of a base station and N receivers. We perform an asymptotic analysis, as N rarr infin, of the expected delay associated with the broadcasting of a file consisting of K packets. We show that if K is fixed, cooperation outperforms network coding, in the sense that the expected delay is proportional to K (and thus within a constant factor of the optimal delay) in the former case while it grows logarithmically with N in the latter case. On the other hand, if K grows with N at a rate at least as fast as (logN)r, for r Gt 1, then we show that the average delay of network coding is also proportional to K and lower than the average delay of cooperation if the packet error probability is smaller than 0.36. Our analytical findings are validated through extensive numerical simulations.

Recent deregulation initiatives enable cellular providers to sell excess spectrum for secondary usage. In this paper, we investigate the problem of optimal spot pricing of spectrum by a provider in the presence of both non-elastic primary users, with long-term commitments, and opportunistic, elastic secondary users. We first show that optimal pricing can be formulated as an infinite horizon average reward problem and solved using stochastic dynamic programming. Next, we investigate the design of efficient single pricing policies. We provide numerical and analytical evidences that static pricing policies do not perform well in such settings (in sharp contrast to settings where all the users are elastic). On the other hand, we prove that deterministic threshold pricing achieves optimal profit amongst all single-price policies and performs close to global optimal pricing. We characterize the profit regions of static and threshold pricing, as a function of the arrival rate of primary users. Under certain reasonable assumptions on the demand function, we show that the profit region of threshold pricing can be far larger than that of static pricing. Moreover, we also show that these profit regions critically depend on the support of the demand function rather than specific form of it. We prove that the profit function of threshold pricing is unimodal in price and determine a restricted interval in which the optimal threshold lies. These two properties enable very efficient computation of the optimal threshold policy that is far faster than that of the global optimal policy.

Over-the-air programming (OAP) is a fundamental service in sensor networks that relies upon reliable broadcast for efficient dissemination. As such, existing OAP protocols become decidedly inefficient (with respect to energy, communication or delay) in unreliable broadcast environments, such as those with relatively high node density or noise. In this paper, we consider OAP approaches based on rateless codes, which significantly improve OAP in such environments by drastically reducing the need for packet rebroadcasting. We thus design and implement two rateless OAP protocols, rateless Deluge and ACKless Deluge, both of which replace the data transfer mechanism of the established OAP Deluge protocol with rateless analogs. Experiments with Tmote Sky motes on single-hop networks with packet loss rates of 7% show these protocols to save significantly in communication over regular Deluge (roughly 15-30% savings in the data plane, and 50-80% in the control plane), and multi-hop experiments reveal similar trends. Simulations further shows that our new protocols scale better than standard Deluge (in terms of communication and energy) to high network density. TinyOS code for our implementation can be found at http://nislab.bu.edu.

In this paper, we present an analytical model for delay tolerant message propagation in a dynamic vehicular network. The analysis provides upper and lower bounds for message propagation as function of traffic density, vehicle speed and radio range. The model is an extension of previous work which considered a particular network setting. The results from the analytical model are compared with simulation results for various vehicular traffic densities. The work demonstrates that increased mobility of vehicles actually aids in messaging contrary to the expectation that it would be a hindrance due to frequent topology changes. An increase in vehicle speed from 0 m/s to 20 m/s results in a corresponding increase in message propagation rate of 200 m/s for vehicular density of 25 vehicles/km.

We consider pricing secondary access to wireless spectrum in cellular CDMA networks. We study the case for a primary license holder interested in leasing the right of providing service in a given geographical region of its coverage network. The goal is to price access to the cells in that region under heterogeneous call traffic demand with the objective of profit maximization. While a revenue is gained from the leased region due to the exercised price, the primary license holder incurs a loss due to reduced spatial coverage of the network and also due to interference effect from the leased into the retained region. We exploit the spatial effect of interference due to geographical locations of the cells and set a price per cell rather than pricing the whole region by a scalar quantity. We employ reduced load approximations which have proved useful in classical telephony and characterize optimal prices for different pricing philosophies, e.g., flat pricing and demand-based pricing. The obtained formula of prices suggests charging per admitted call in proportion with the interference that the call generates. The charged amount balances the corresponding loss of revenue due to the influence of an admitted call. We present an iterative price computing technique and provide a numerical study in support of our analytical results.

Wireless Sensor Networks (WSNs) provide an important means of monitoring the physical world, but their limitations present challenges to fundamental network services such as routing. In this work we utilize an abstraction of WSNs based on the theory of identifying codes. This abstraction has been useful in recent literature for a number of important monitoring problems, such as localization and contamination detection. In our case, we use it to provide a joint infrastructure for efficient and robust monitoring and routing in WSNs. Specifically, we provide an efficient and distributed algorithm for generating robust identifying codes with a logarithmic performance guarantee based on a novel reduction to the set k-multicover problem; to the best of our knowledge, this is the first such guarantee for the robust identifying codes problem, which is known to be NP-hard. We also show how this same identifying-code infrastructure provides a natural labeling that can be used for near-optimal routing with very small routing tables. We provide experimental results for various topologies that illustrate the superior performance of our approximation algorithms over previous identifying code heuristics.

We analyze the performance limits of data dissemination with multi-channel, single radio sensors. We formulate the problem of minimizing the average delay of data dissemination as a stochastic shortest path problem and show that, for an arbitrary topology network, an optimal control policy can be found in a finite number of steps, using value iteration or Dijsktra's algorithm. However, the computational complexity of this solution is generally prohibitive. We thus focus on two special classes of network topologies of practical interest, namely single-hop clusters and multi-hop cluster trees. For these topologies, we derive the structure of policies that achieve an average delay within a factor 1 + e of the optimal average delay, in networks with large number of nodes. Through simulation, we show that these policies perform close to optimal even for networks with small and moderate numbers of nodes. Our analysis and simulations reveal that multichannel data dissemination policies lead to a drastic reduction in the average delay, up to a factor as large as the total number of channels available, even though each node can communicate over only one channel at any point of time. Finally, we present the foundations of a methodology, based on extreme value theory, allowing the implementation of our near-optimal dissemination policies with minimal overhead.

We introduce a new algorithmic framework for advanced channel reservation in ultra high speed networks, called Graded Channel Reservation (GCR). GCR allows users to specify minimum bandwidth and duration requirements for their connections. GCR returns the highest graded path, selected according to a general, multi-criteria optimization objective. In particular, if the optimization criterion is delay, we prove that GCR returns the earliest time available to establish the connection. The computational complexity is polynomial in the size of the graph and the number of pending requests. We introduce a number of variants to GCR, including one that that provides the capability to switch between different paths during a connection. We present practical methods for minimizing or limiting the number of path switches. Through extensive simulations, we evaluate the performance of GCR and its variants under various topological settings and applications workload. Our results show that, for certain traffic parameters, optimized path selection combined with path switching can reduce the average delay of requests by an order of magnitude and increase the saturation throughput by as much as 50%. I.

This paper discusses the use of rateless codes to increase performance in wireless sensor networks.

The objective of the paper is to provide qualitative insight into the global effects of distributed mechanisms, such as carrier sense multiple access (CSMA) and rate control, on the performance and stability of multi-hop wireless networks. Toward this end, we introduce a linear queueing network model where the service capacity of each node is modulated by the transmission state of its neighbor. We derive lower bounds on the steady-state utilization at each queue of such networks and demonstrate the existence of a phase transition phenomenon, whereby infinitesimal traffic increase at a single node in the network can suddenly render the entire network instable. We also present NS simulation results that show how this phenomenon can actually take place in IEEE 802.11 multi-hop wireless networks. Our results have direct bearing on rate control schemes, in that they indicate a minimum admissible threshold rate required to prevent network instability.

We consider wireless sensor networks with multiple gateways and multiple classes of traffic carrying data generated by different sensory inputs. The objective is to devise joint routing, power control and transmission scheduling policies in order to gather data in the most efficient manner while respecting the needs of different sensing tasks (fairness). We formulate the problem as maximizing the utility of transmissions subject to explicit fairness constraints. We propose an efficient decomposition algorithm drawing upon large-scale decomposition ideas in mathematical programming. We show that our algorithm terminates in a finite number of iterations and produces a policy that is asymptotically optimal at low transmission power levels. Moreover, numerical results establish that this policy is near-optimal even at high power levels. We also demonstrate how to adapt our algorithm to accommodate energy constraints and node failures. The approach we introduce can efficiently determine near-optimal transmission policies for dramatically larger problem instances than an alternative enumeration approach.

No abstract available.

IEEE 802.11 wireless networks employ the so-called RTS/CTS mechanism in order to avoid data packet collisions. The main design assumption is that all the nodes in the vicinity of a sender and a receiver will hear the RTS or CTS packets, and defer their transmission appropriately. This assumption happens to not hold, in general, even under perfect operating conditions. Often, neighboring nodes are "masked" by other ongoing transmissions nearby and, hence, are unable to receive the RTS or CTS packets correctly. We refer to such nodes as masked nodes. In this paper, we describe the masked node problem and show scenarios leading to data packet collisions. We evaluate the impact of masked nodes through mathematical analysis and real experiments on a small IEEE 802.11 ad hoc network. The analytical and experimental data closely match and reveal that the presence of a masked node in a network can result in an order of magnitude increase in data packet loss compared to a network without masked nodes. These results are further validated by extensive simulations on a large-scale network, which show that masked nodes also significantly affect delay and throughput performance. Therefore, masked nodes severely limit the effectiveness of the RTS/CTS mechanism in preventing performance degradation in wireless LANs.

Ethernet networks rely on the so-called spanning tree protocol (IEEE 802.1d) in order to break cycles, thereby avoiding the possibility of infinitely circulating packets and deadlocks. This protocol imposes a severe penalty on the performance and scalability of large gigabit Ethernet backbones, since it makes inefficient use of expensive fibers and may lead to bottlenecks. We propose a significantly more scalable cycle-breaking approach, based on the novel theory of turn-prohibition. Specifically, we introduce, analyze and evaluate a new algorithm, called tree-based turn-prohibition (TBTP). We show that this polynomial-time algorithm maintains backward-compatibility with the IEEE 802.1d standard and never prohibits more than 1/2 of the turns in the network, for any given graph and any given spanning tree. Through extensive simulations on a variety of graph topologies, we show that it can lead to an order of magnitude improvement over the spanning tree protocol with respect to throughput and end-of-end delay metrics. In addition, we propose and evaluate heuristics to determine the replacement order of legacy switches that results in the fastest performance improvement.

We propose a novel framework for location detection with sensor networks, based on the theory of identifying codes. The key idea of this approach is to allow sensor coverage areas to overlap so that each resolvable position is covered by a unique set of sensors. In this setting, determining a sensor-placement with a minimum number of sensors is equivalent to constructing an optimal identifying code, an NP-complete problem in general. We, thus, propose and analyze new polynomial-time algorithms for generating irreducible (but not necessarily optimal) codes for arbitrary topologies. Our algorithms incorporate robustness properties that are critically needed in harsh environments. We further introduce distributed versions of these algorithms, allowing sensors to self-organize and determine a (robust) identifying code without any central coordination. Through analysis and simulation, we show that our algorithms produce nearly optimal solutions for a wide range of parameters. In addition, we demonstrate a tradeoff between system robustness and the number of active sensors (which is related to the expected lifetime of the system). Finally, we present experimental results, obtained on a small testbed, that demonstrate the feasibility of our approach.

We propose a new framework for providing robust location detection in emergency response systems, based on the theory of identifying codes. The key idea of this approach is to allow sensor coverage areas to overlap in such a way that each resolvable position is covered by a unique set of sensors. In this setting, determining a sensor-placement with a minimum number of sensors is equivalent to constructing an optimal identifying code, an NP-complete problem in general. We thus propose and analyze a new polynomial-time algorithm for generating irreducible codes for arbitrary topologies. We also generalize the concept of identifying codes to incorporate robustness properties that are critically needed in emergency networks and provide a polynomial-time algorithm to compute irreducible robust identifying codes. Through analysis and simulation, we show that our approach typically requires significantly fewer sensors than existing proximity-based schemes. Alternatively, for a fixed number of sensors, our scheme can provide robustness in the face of sensor failures or physical damage to the system.

Distributed self-organization algorithms for wireless sensor (and actuator) networks must have low message complexity from energy and bandwidth considerations. In this paper, we present a novel approach for message-efficient clustering, in which nodes allocate local growth budgets to neighbors. We introduce two algorithms that make use of this approach. Unlike the expanding ring approach [C.V. Ramamoorhty, A. Bhide, and J. Srivastava, Proc. IEEE INFOCOM '87, 1987], our algorithms do not involve the initiator in each round, and do not violate the specified upper bound on the cluster size at any time. We derive analytical performance bounds of our algorithms and also provide performance results from simulations. The algorithms produce clusters of bounded size and low diameter, using significantly fewer messages than the expanding ring approach.

The RTS/CTS mechanism is widely used in wireless networks in order to avoid packet collisions and, thus, achieve high throughput. In ad hoc networks, however the current implementation of the RTS/CTS mechanism may lead to interdependencies so that nodes become unable to transmit any packets during long periods of time. This effect manifests itself in the form of congestion where, after a certain point, the network throughput decreases with increasing load instead of maintaining its peak value. In this paper, we describe and analyze this problem in detail and provide a backward-compatible solution, called RTS validation. Our simulations show that this solution leads to a 60% gain in the peak throughput in addition to stabilizing the throughput at high load.

Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage, latency, and energy consumption since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync) predicated upon previous information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity and energy consumption of CPIsync is practical and that the-overall latency is typically much smaller than that of slow sync or alternative synchronization approaches based on Bloom (1970) filters. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.

Network calculus is known to apply in general only to feedforward routing networks, i.e., networks where routes do not create cycles of interdependent packet flows. We address the problem of using network calculus in networks of arbitrary topology. For this purpose, we introduce a novel graph-theoretic algorithm, called turn-prohibition (TP), that breaks all the cycles in a network and, thus, prevents any interdependence between flows. We prove that the TP-algorithm prohibits the use of at most 1/3 of the total number of turns in a network, for any network topology. Using analysis and simulation, we show that the TP-algorithm significantly outperforms other approaches for breaking cycles, such as the spanning tree and up/down routing algorithms, in terms of network utilization and delay bounds. Our simulation results also show that the network utilization achieved with the TP-algorithm is within a factor of two of the maximum theoretical network utilization, for networks of up to 50 nodes of degree four. Thus, in many practical cases, the restriction of network calculus to feedforward routing networks may not represent a too significant limitation.

Network calculus is known to apply in general only to feedforward routing networks, i.e., networks where routes do not create cycles of interdependent packet flows. We address the problem of using network calculus in networks of arbitrary topology. For this purpose, we introduce a novel algorithm, called turn-prohibition (TP), that breaks all the cycles in a network and thus prevents any interdependence between flows. We prove that the TP-algorithm prohibits the use of at most 1/3 of the total number turns in a network, for any network topology. Using analysis and simulation, we show that the TP-algorithm significantly outperforms other approaches for breaking cycles, such as the spanning tree and up/down routing algorithms, in terms of network utilization and delay bounds. Our simulation results also show that the network utilization achieved with the TP-algorithm is within a factor of two of the maximum theoretical network utilization, for networks of up to 50 nodes of degree four. Thus, in many practical cases, the restriction of network calculus to feed-forward routing networks may not represent a significant limitation.

Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage and latency, since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync - characteristic polynomial interpolation-based synchronization) predicated upon recent information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity of CPIsync is practical, and that the overall latency is typically much smaller than that of slow sync. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.

A network calculus is developed for processes whose burstiness is stochastically bounded by general decreasing functions. This calculus is useful for a large class of input processes, including important processes exhibiting "subexponentially bounded burstiness" such as fractional Brownian motion. Moreover, it allows judicious capture of the salient features of real-time traffic, such as the "cell" and "burst" characteristics of multiplexed traffic. This accurate characterization is achieved by setting the bounding function as a sum of exponentials.

We develop a network calculus for processes whose burstiness is stochastically bounded by general decreasing functions. This calculus enables one to prove the stability of feedforward networks and obtain statistical upper bounds on interesting performance measures such as delay, at each buffer in the network. The bounding methodology is useful for a large class of input processes, including important processes exhibiting "subexponentially bounded burstiness" such as fractional Brownian motion. Moreover, it generalizes previous approaches and provides much better bounds for common models of real-time traffic, like Markov modulated processes and other multiple time-scale processes. We expect that this new calculus will be of particular interest in the implementation of services providing statistical guarantees.

In cellular networks, blocking occurs when a base station has no free channel to allocate to a mobile user. One distinguishes between two kinds of blocking, the first is called new call blocking and refers to blocking of new calls, the second is called handoff blocking and refers to blocking of ongoing calls due to the mobility of the users. We first provide explicit analytic expressions for the two kinds of blocking probabilities in two asymptotic regimes, i.e., for very slow mobile users and for very fast mobile users, and show the fundamental differences between these blocking probabilities. Next, an approximation is introduced in order to capture the system behavior for moderate mobility. The approximation is based on the idea of isolating a set of cells and having a simplifying assumption regarding the handoff traffic into this set of cells, while keeping the exact behavior of the traffic between cells in the set. It is shown that a group of 3 cells is enough to capture the difference between the blocking probabilities of handoff call attempts and new call attempts.