Distributed algorithms for constructing structures such as a maximal independent set (MIS) or maximal matching (MM) are well-studied in standard message-passing network models. In this paper, we consider a natural variant of this problem in which we begin with an instance of the graph structure and partition our algorithm execution that follows into two stages. During the first stage after the graph structure is calculated, some additional precomputation is done. In the second stage, an arbitrary collection of k nodes are crashed. The goal is to then repair the structure as efficiently as possible. We are interested in the circumstances under which the repair can be faster than the time required to build the structure from scratch, and focus, in particular, on trade-offs in which extra precomputation rounds during the first stage can be traded for faster repairs during the second.

This paper considers the problem of Byzantine fault-tolerance in distributed multi-agent optimization. In this problem, each agent has a local cost function, and in the fault-free case, the goal is to design a distributed algorithm that allows all the agents to find a minimum point of all the agents' aggregate cost function. We consider a scenario where some agents might be Byzantine faulty that renders the original goal of computing a minimum point of all the agents' aggregate cost vacuous. A more reasonable objective for an algorithm in this scenario is to allow all the non-faulty agents to compute the minimum point of only the non-faulty agents' aggregate cost. Prior work shows that if there are up to f (out of n) Byzantine agents then a minimum point of the non-faulty agents' aggregate cost can be computed exactly if and only if the non-faulty agents' costs satisfy a certain redundancy property called 2f-redundancy. However, 2f-redundancy is an ideal property that can be satisfied only in systems free from noise or uncertainties, which can make the goal of exact fault-tolerance unachievable in some applications. Thus, we introduce the notion of (f,ε)-resilience, a generalization of exact fault-tolerance wherein the objective is to find an approximate minimum point of the non-faulty aggregate cost, with ε accuracy. This approximate fault-tolerance can be achieved under a weaker condition that is easier to satisfy in practice, compared to 2f-redundancy. We obtain necessary and sufficient conditions for achieving (f, ε)-resilience characterizing the correlation between relaxation in redundancy and approximation in resilience. In case when the agents' cost functions are differentiable, we obtain conditions for (f, ε)-resilience of the distributed gradient-descent method when equipped with robust gradient aggregation; such as comparative gradient elimination or coordinate-wise trimmed mean.

In this paper, we consider contention resolution algorithms that are augmented with predictions about the network. We begin by studying the natural setup in which the algorithm is provided a distribution defined over the possible network sizes that predicts the likelihood of each size occurring. The goal is to leverage the predictive power of this distribution to improve on worst-case time complexity bounds. Using a novel connection between contention resolution and information theory, we prove lower bounds on the expected time complexity with respect to the Shannon entropy of the corresponding network size random variable, for both the collision detection and no collision detection assumptions. We then analyze upper bounds for these settings, assuming now that the distribution provided as input might differ from the actual distribution generating network sizes. We express their performance with respect to both entropy and the statistical divergence between the two distributions---allowing us to quantify the cost of poor predictions. Finally, we turn our attention to the related perfect advice setting, parameterized with a length b ≥ 0, in which all active processes in a given execution are provided the best possible b bits of information about their network. We provide tight bounds on the speed-up possible with respect to b for deterministic and randomized algorithms, with and without collision detection. These bounds provide a fundamental limit on the maximum power that can be provided by any predictive model with a bounded output size.

The tutorial will include an introduction to (i) distributed optimization and distributed machine learning, (ii) security or fault-tolerance for distributed optimization and learning, and (iii) privacy in distributed optimization and learning. The presentation will cover the basic principles, and some representative solutions. Server-based and peer-to-peer solutions will be discussed. In particular, Byzantine fault-tolerant algorithms for distributed optimization and learning will be discussed. Privacy mechanisms to be discussed include differential privacy and its variations for systems based on multiple servers.

Byzantine consensus is a classical problem in distributed computing. Each node in a synchronous system starts with a binary input. The goal is to reach agreement in the presence of Byzantine faulty nodes. We consider the setting where communication between nodes is modelled via an undirected communication graph. In the classical point-to-point communication model all messages sent on an edge are private between the two endpoints of the edge. This allows a faulty node to equivocate, i.e., lie differently to its different neighbors. Different models have been proposed in the literature that weaken equivocation. In the local broadcast model, every message transmitted by a node is received identically and correctly by all of its neighbors. In the hypergraph model, every message transmitted by a node on a hyperedge is received identically and correctly by all nodes on the hyperedge. Tight network conditions are known for each of the three cases. We introduce a more general model that encompasses all three of these models. In the local multicast model, each node u has one or more local multicast channels. Each channel consists of multiple neighbors of u in the communication graph. When node u sends a message on a channel, it is received identically by all of its neighbors on the channel. For this model, we identify tight network conditions for consensus. We observe how the local multicast model reduces to each of the three models above under specific conditions. In each of the three cases, we relate our network condition to the corresponding known tight conditions. The local multicast model also encompasses other practical network models of interest that have not been explored previously, as elaborated in the paper.

This paper considers the problem of Byzantine fault-tolerance in distributed multi-agent optimization. In this problem, each agent has a local cost function. The goal of a distributed optimization algorithm is to allow the agents to collectively compute a minimum of their aggregate cost function. We consider the case when a certain number of agents may be Byzantine faulty. Such faulty agents may not follow a prescribed algorithm, and they may send arbitrary or incorrect information regarding their local cost functions. Unless a fault-tolerance mechanism is employed, traditional distributed optimization algorithms cannot tolerate such faulty agents.

This paper considers the problem of approximate consensus in directed asynchronous message-passing networks where some nodes may become Byzantine faulty. We obtain a tight necessary and sufficient condition on the underlying directed communication network for asynchronous Byzantine approximate consensus to be achievable. Interestingly, this condition coincides with the tight condition for synchronous Byzantine exact consensus. Our consensus algorithm may be viewed as a non-trivial generalization of an algorithm previously proposed for the special case of complete networks. The tight condition and techniques identified in the paper shed light on the fundamental properties for solving approximate consensus in asynchronous directed networks.

Byzantine broadcast (BB) and Byzantine agreement (BA) are two most fundamental problems and essential building blocks in distributed computing, and improving their efficiency is of interest to both theoreticians and practitioners. In this paper, we study extension protocols of BB and BA, i.e., protocols that solve BB/BA with long inputs of l bits using lower costs than l single-bit instances. We present new protocols with improved communication complexity in almost all settings: authenticated BA/BB with t < n/2, authenticated BB with t < (1-ε)n, unauthenticated BA/BB with t < n/3, and asynchronous reliable broadcast and BA with t < n/3. The new protocols are advantageous and significant in several aspects. First, they achieve the best-possible communication complexity of Θ(nl) for wider ranges of input sizes compared to prior results. Second, the authenticated extension protocols achieve optimal communication complexity given the current best available BB/BA protocols for short messages. Third, to the best of our knowledge, our asynchronous and authenticated protocols in the setting are the first extension protocols in that setting.

We consider Byzantine consensus in a synchronous system where nodes are connected by a network modeled as a directed graph, i.e., communication links between neighboring nodes are not necessarily bi-directional. The directed graph model is motivated by wireless networks wherein asymmetric communication links can occur. In the classical point-to-point communication model, a message sent on a communication link is private between the two nodes on the link. This allows a Byzantine faulty node to equivocate, i.e., send inconsistent information to its neighbors. This paper considers the local broadcast model of communication, wherein transmission by a node is received identically by all of its outgoing neighbors, effectively depriving the faulty nodes of the ability to equivocate. Prior work has obtained sufficient and necessary conditions on undirected graphs to be able to achieve Byzantine consensus under the local broadcast model. In this paper, we obtain tight conditions on directed graphs to be able to achieve Byzantine consensus with binary inputs under the local broadcast model. The results obtained in the paper provide insights into the trade-off between directionality of communication links and the ability to achieve consensus.

This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical point-to-point communication model, it is well-known that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to ƒ Byzantine faulty nodes: n & 3 #8805; 3 ≥ ƒ+ 1 and vertex connectivity at least 2 ƒ + 1. In the classical point-to-point communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors.

The focus of this paper is on causal consistency in a partially replicated distributed shared memory (DSM) system that provides the abstraction of shared read/write registers. Maintaining causal consistency in distributed shared memory systems has received significant attention in the past, mostly on full replication wherein each replica stores a copy of all the registers in the shared memory. To ensure causal consistency, all causally preceding updates must be performed before an update is performed at any given replica. Therefore, some mechanism for tracking causal dependencies is required, such as vector timestamps with the number of vector elements being equal to the number of replicas in the context of full replication. In this paper, we investigate causal consistency in partially replicated systems, wherein each replica may store only a subset of the shared registers. Building on the past work, this paper makes three key contributions:

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

Consider a point-to-point message-passing network. We are interested in the asynchronous crash-tolerant consensus problem in incomplete networks. We study the feasibility and efficiency of approximate consensus under different restrictions on topology knowledge and the relay depth, i.e., the maximum number of hops any message can be relayed. These two constraints are common in large-scale networks, and are used to avoid memory overload and network congestion respectively. Specifically, for positive integer values k and k', we consider that each node knows all its neighbors of at most k-hop distance (k-hop topology knowledge), and the relay depth is k'. We consider both directed and undirected graphs. More concretely, we answer the following question in asynchronous systems: "What is a tight condition on the underlying communication graphs for achieving approximate consensus if each node has only a k-hop topology knowledge and relay depth k'?" To prove that the necessary conditions presented in the paper are also sufficient, we have developed algorithms that achieve consensus in graphs satisfying those conditions: - The first class of algorithms requires k-hop topology knowledge and relay depth k. Unlike prior algorithms, these algorithms do not flood the network, and each node does not need the full topology knowledge. We show how the convergence time and the message complexity of those algorithms is affected by k, providing the respective upper bounds. - The second set of algorithms requires only one-hop neighborhood knowledge, i.e., immediate incoming and outgoing neighbors, but needs to flood the network (i.e., relay depth is n, where n is the number of nodes). One result that may be of independent interest is a topology discovery mechanism to learn and "estimate" the topology in asynchronous directed networks with crash faults.

Consider an asynchronous incomplete directed network. We study the feasibility and efficiency of approximate crash-tolerant consensus under different restrictions on topology knowledge and relay depth, i.e., the maximum number of hops any message can be relayed.

Practical algorithms for determining causality by assigning timestamps to events have focused on online algorithms, where a permanent timestamp is assigned to an event as soon as it is created. We address the problem of reducing size of the timestamp by utilizing the underlying topology (which is often not fully connected since not all processes talk to each other) and deferring the assignment of a timestamp to an event for a suitably chosen period of time after the event occurs. Specifically, we focus on inline timestamps, which are a generalization of offline timestamps that are assigned after the computation terminates. We show that for a graph with vertex cover VC, it is possible to assign inline timestamps which contains only 2|VC|+2 elements.

The CAP theorem is a fundamental result that applies to distributed storage systems. In this article, we first present and prove two CAP-like impossibility theorems. To state these theorems, we present probabilistic models to characterize the three important elements of the CAP theorem: consistency (C), availability or latency (A), and partition tolerance (P). The theorems show the un-achievable envelope, that is, which combinations of the parameters of the three models make them impossible to achieve together. Next, we present the design of a class of systems called Probabilistic CAP (PCAP) that perform close to the envelope described by our theorems. In addition, these systems allow applications running on a single data center to specify either a latency Service Level Agreement (SLA) or a consistency SLA. The PCAP systems automatically adapt, in real time and under changing network conditions, to meet the SLA while optimizing the other C/A metric. We incorporate PCAP into two popular key-value stores: Apache Cassandra and Riak. Our experiments with these two deployments, under realistic workloads, reveal that the PCAP systems satisfactorily meets SLAs and perform close to the achievable envelope. We also extend PCAP from a single data center to multiple geo-distributed data centers.

Byzantine vector consensus requires that non-faulty processes reach agreement on adecision (or output) that is in the convex hull of the inputs at the non-faulty processes. Recent work has shown that, for n processes with up to f Byzantine failures, when the inputs are d-dimensional vectors of reals, n >= max (3f + 1, (d + 1)f + 1) is the tight bound for synchronous systems, and n >= (d + 2)f + 1 is tight for approximate consensus in asynchronous systems. Due to the dependence of the lower bound on vector dimension d, the number of processes necessary becomes large when the vector dimension is large. With the hope of reducing the lower bound on n, we propose relaxed versions of Byzantine vector consensus: k-relaxed Byzantine vector consensus and (delta, p)-relaxed Byzantine vector consensus. k-relaxed consensus only requires consensus for projections of inputs on every subset of k dimensions. (delta, p)-relaxed consensus requires that the output be within distance d of the convex hull of the non-faulty inputs, where distance is defined using the L_{p}-norm. An input-dependent delta allows the distance from the non-faulty convex hull to be dependent on the maximum distance between the non-faulty inputs. We show that for k-relaxed consensus with k > 1, and for (delta, p)-relaxed consensus with constant delta >= 0, the bound on n is identical to the bound stated above for the original vector consensus problem. On the other hand, when k = 1 or d depends on the inputs, we show that the bound on n is smaller when d >= 3. Input-dependent delta may be of interest in practice. In essence, input-dependent delta scales with the spread of the inputs.

This paper addresses the problem of distributed multi-agent optimization in which each agent i has a local cost function hi(x), and the goal is to optimize a global cost function that aggregates the local cost functions. Such optimization problems are of interest in many contexts, including distributed machine learning, distributed resource allocation, and distributed robotics.

Byzantine vector consensus requires that non-faulty processes reach agreement on a decision (or output) that is in the convex hull of the inputs at the non-faulty processes. Recent work has shown that, for n processes with up to f Byzantine failures, when the inputs are d-dimensional vectors of reals, n ≥ max{(3f+1,(d+1)f+1)} is the tight bound for synchronous systems, and n≥(d+2)f+1 is tight for approximate consensus in asynchronous systems. Due to the dependence of the lower bound on vector dimension d, the number of processes necessary becomes large when the vector dimension is large. With the hope of reducing the lower bound on n, we propose relaxed versions of Byzantine vector consensus: k-relaxed Byzantine vector consensus and (δ,p)-relaxed Byzantine vector consensus. k-relaxed consensus only requires consensus for projections of inputs on every subset of k dimensions. (δ,p)-relaxed consensus requires that the output be within distance δ of the convex hull of the non-faulty inputs, where distance is defined using the Lp-norm. An input-dependent δ allows the distance from the non-faulty convex hull to be dependent on the maximum distance between the non-faulty inputs.

The surge of proximity-based applications on mobile devices has promoted the need for effective neighbor discovery protocols in mobile wireless networks. In contrast to existing works, which can achieve energy efficient neighbor discovery with bounded latency only in the scenario without strong interference, we aim at designing techniques for practical and robust neighbor discovery. We propose ReCorder to achieve robust neighbor discovery in mobile wireless networks despite the "noisy" communication media. Specifically, we exploit the cross-correlation property of pseudo-random sequences to eliminate the necessity of beacon decoding in existing neighbor discovery protocols. In ReCorder, a neighbor discovery message can be detected through cross-correlation on an RCover preamble, and contains a ReCord identity signature, which is unique for each of the nodes. We also design algorithms for RCover detection and ReCord recognization. The performance of ReCorder has been evalueated using the USRP-N210 testbed. Our evaluation results show that ReCorder can achieve robust neighbor discovery at an SINR lower than the existing beaconing and decoding based neighbor discovery protocols by almost 10dB. Furthermore, ReCorder can avoid degrading the decoding of background IEEE 802.11a/g transmissions with BPSK modulation, which is important for its co-existence with concurrent wireless streams.

This paper considers reliable communication in presence of Byzantine faulty nodes, using multiple node-disjoint routes. To tolerate f Byzantine faults, at least 2f + 1 node-disjoint paths are needed between a source and destination node pair. However, often the faulty nodes' misbehavior manifests itself as a "disagreement" between information provided by the faulty node and its neighbors. This disagreement can be captured in the form of a conflict graph. Even though the conflict graph does not always allow us to identify faulty nodes precisely, we show that it can still be used to reduce the number of paths necessary for reliable communication (to smaller than 2f+1). We consider two strategies for using the node-disjoint paths for reliable delivery of messages: replication and coding across different paths. For each strategy, we propose iPath, a scheme to identify the optimal set of paths that needs to be used to achieve reliable communication for a given conflict graph.

Bandwidth is a shared and limited resource of the wireless LAN. The MAC protocols are mainly responsible for efficiently sharing it among all the stations. The IEEE 802.11 standard uses Distributed Coordination Function (DCF) as its default MAC protocol which employs Carrier Sense Multiple Access using Collision Avoidance (CSMA/CA) scheme with binary exponential backoff algorithm. Despite its ubiquitous acceptance, it has two major drawbacks: i) channel idle time and ii) collision overhead. Besides, this protocol uses explicit ack which comes with significant overheads, for example preamble, frame header etc. In this paper, we propose a scheme called O-ACK which reduces the overhead of explicit ack and backoff interval by leveraging piggybacking, packet overhearing and token based scheduling. Our NS2 based simulation results confirm that this protocol significantly outperforms the DCF protocol.

Consider a point-to-point network in which nodes are connected by directed links. This paper proves tight necessary and sufficient conditions on the underlying communication graphs for solving the following fault-tolerant consensus problems: Exact crash-tolerant consensus in synchronous systems, Approximate crash-tolerant consensus in asynchronous systems, and Exact Byzantine consensus in synchronous systems.

In wireless LANs, MAC protocols perform one of the most important tasks: efficiently sharing the limited bandwidth among the contending stations. In IEEE 802.11, Distributed Coordination Function (DCF) is used as a default MAC protocol. Despite its wide acceptance, it has two major downsides: i) Channel idle time and ii) Collision overheads. Besides, the use of the explicit ack frames incurs extra overhead due to the preamble, packet headers etc. This paper presents an optimized version of the Overheard-ACK (O-ACK) protocol (presented in [2]) which incorporates piggybacking, packet overhearing and token based scheduling to significantly reduce the overheads. The previous version of O-ACK creates chains of transmissions, where consecutive transmissions are separated by SIFS interval, which increases the throughput. But on the downside, as two adjacent transmissions are separated by only SIFS idle time, a newly arrived station cannot start transmission. Our current version of O-ACK ensures higher throughput and fairness in multiple AP scenario by continuously adapting the chain creation process based on the surrounding environment. Our NS-2 based simulation results confirm that this protocol significantly outperforms the DCF protocol.

A network with densely deployed access points can perform better and more reliably by adapting the transmission parameters like transmission power, minimum size of contention window (cwmin), maximum size of contention window (cwmax) and transmission rate. To understand the impact of these parameters on performance of CSMA-based protocol in a multi-AP network, we are building a testbed called DAPnet. DAPnet lets us change cwmin, cwmax, transmission rate, transmission power and operating channel of the nodes in the network remotely. The testbed is partially deployed and soon will be completely deployed at the Coordinate Science Lab (CSL) which is a research center at the University of Illinois. This testbed consists of 40 devices equipped with USB wireless cards. In this paper we discuss the challenges, design and implementation of DAPnet and how it can be used to improve reliability and performance of Dense-AP network.

In a multichannel wireless system, the performance of a link depends on many factors. The link quality is subject to temporal, spatial and spectral diversity, i.e. the SNR is time varying, link-dependent and channel-dependent. In addition, the performance also depends on MAC dynamics and the degree of congestion present in the channel. As a result, different links can experience different performance on the same channel, and the performance of a link varies across channels and time. An effective way to exploit and cope with the diversity in the wireless system is to use opportunistic channel switching. This technique allows a link to dynamically search for a channel/spectrum where it can maximize its performance at a given point of time. In addition, we observe that the link diversity can make it beneficial to have channels configured with different PHY/MAC parameters (e.g. different transmit power, data rates, or carrier sensing threshold). We refer to these as heterogeneous channels. A group of links may perform better under a set of parameters while a different group may perform better under a different set. In this paper we combine an opportunistic channel switching scheme with heterogeneous channels in multichannel Wireless LANs (WLANs) and show that the combined approach is effective in increasing link throughput and fairness.

Carrier Sense Multiple Access (CSMA) protocols have been shown to reach the full capacity region for data communication in wireless networks, with polynomial complexity. However, current literature achieves the throughput optimality with an exponential delay scaling with the network size, even in a simplified scenario for transmission jobs with uniform sizes. Although CSMA protocols with order-optimal average delay have been proposed for specific topologies, no existing work can provide worst-case delay guarantee for each job in general network settings, not to mention the case when the jobs have non-uniform lengths while the throughput optimality is still targeted. In this paper, we tackle on this issue by proposing a two-timescale CSMA-based data communication protocol with dynamic decisions on rate control, link scheduling, job transmission and dropping in polynomial complexity. Through rigorous analysis, we demonstrate that the proposed protocol can achieve a throughput utility arbitrarily close to its offline optima for jobs with non-uniform sizes and worst-case delay guarantees, with a tradeoff of longer maximum allowable delay.

Distributed Coordination Function (DCF) is defined in IEEE 802.11 standard, which is widely used in practice. Despite of its wide use, it has several limitations. Because of the idle and collision times, it suffers from poor channel utilization. Besides, the control packets, particularly, Acknowledgement (ACK), consume non-trivial amount of bandwidth. Though the number of control bits in an ACK frame is small, the added overheads like the preamble, packet header etc. make the situation worse. In this paper, we propose a scheme called Overheard ACK where the explicit ACK frame has been eliminated by using the leverage of packet overhearing. Also, by incorporating explicit and implicit token-passing, this protocol attempts to schedule transmissions without having to use random access, dramatically reducing the idle time and collision time. Simulation results using NS2 confirm that this protocol significantly outperforms the conventional 802.11 DCF.

This paper defines a new consensus problem, convex hull consensus. The input at each process is a d-dimensional vector of reals (or, equivalently, a point in the d-dimensional Euclidean space), and the output at each process is a convex polytope contained within the convex hull of the inputs at the fault-free processes. We explore the convex hull consensus problem under crash faults with incorrect inputs, and present an asynchronous approximate convex hull consensus algorithm with optimal fault tolerance that reaches consensus on an optimal output polytope.

This paper presents the design and performance evaluation of Concurrent-MAC, a MAC protocol for increasing concurrent transmissions in multi-AP wireless LANs. Based on SINR values between stations and APs, sets of concurrent transmitters are identified by the backhaul of APs. A station gaining access to the channel, schedules a set of its neighbors for concurrent transmissions. Neighbors chosen for concurrent transmission can start transmitting on the channel, immediately after they overhear the privilege given to them for concurrent transmission. Our simulation results show that, in dense wireless LANs, Concurrent-MAC can improve aggregate throughput significantly compared to 802.11 DCF.

Consider a network of n processes, each of which has a d-dimensional vector of reals as its input. Each process can communicate directly with all the processes in the system; thus the communication network is a complete graph. All the communication channels are reliable and FIFO (first-in-first-out).

With the growing deployment of wireless communication technologies, radio spectrum is becoming a scarce resource. Thus, mechanisms to efficiently allocate the available spectrum are of interest. In this paper, we model the radio spectrum allocation problem as a sealed-bid reserve auction, and propose SMALL, which is a Strategy-proof Mechanism for radio spectrum ALLocation. Furthermore, we extend SMALL to adapt to multiradio spectrum buyers, which can bid for more than one radio. We evaluate SMALL with simulations. Simulation results show that SMALL has good performance in median to large scale spectrum auctions.

Recently, it has been shown that a simple, distributed backlog-based carrier-sense multiple access (CSMA) algorithm is throughput-optimal. However, throughput optimality is established under the perfect or ideal carrier-sensing assumption, i.e., each link can precisely sense the presence of other active links in its neighborhood. In this paper, we investigate the achievable throughput of the CSMA algorithm under imperfect carrier sensing. Through the analysis on both false positive and negative carrier sensing failures, we show that CSMA can achieve an arbitrary fraction of the capacity region if certain access probabilities are set appropriately. To establish this result, we use the perturbation theory of Markov chains.

Preserving source location privacy in wireless sensor networks can be critical for several practical applications. Existing solutions proposed specifically for sensor networks rely on a combination of dynamic routing and dummy traffic to hide real event messages. While some privacy protection guarantees can be given, these solutions also tend to be expensive due to fake transmissions and non-shortest path routing overheads. In this paper, we propose a novel idea, of using a combination of directional antennas, transmit power control and information compression to provide lightweight and energy-efficient source location privacy. We discuss the adversary model extensively and then carefully layout characteristics of a realistic adversary. We show how use of directional antennas makes eavesdropping more costly for a realistic adversary and establish relationships between probability of compromise of location privacy, characteristics of directional antennas and size of the adversary's eavesdropping network. Finally, we show how a simple information compression measure can greatly reduce message latency and prolong battery life by conserving energy. Results of extensive simulations in NS2, with our realistic directional antenna add-on, show that compared to existing solutions, we can achieve comparable privacy protection, better message latency, delivery ratio and many orders of magnitude improvement in energy consumption.

In this paper, we compare performance of several Byzantine agreement algorithms, including NCBA, a network coding based algorithm. Unlike existing practical BFT protocols such as PBFT by Castro and Liskov [1], which utilize collision-resistant hash functions to reduce traffic load for BFT, NCBA uses a computationally efficient error-detection network coding scheme. Since NCBA does not rely on any hash function, it is always correct rather than correct only with high probability as PBFT. Through extensive experiments, we verified that NCBA performs at least as well as Digest, without relying on any cryptographic assumption on the hardness of breaking the hash function. To the best of our knowledge, this is the first implementation of BFT with network coding.

Consensus algorithms allow a set of nodes to reach an agreement on a quantity of interest. For instance, a consensus algorithm may be used to allow a network of sensors to determine the average value of samples collected by the different sensors. Similarly, a consensus algorithm can also be used by the nodes to synchronize their clocks. Research on consensus algorithms has a long history, with contributions from different research communities, including distributed computing, control systems, and social science.

The goal of Byzantine Broadcast (BB) is to allow a set of fault-free nodes to agree on information that a source node wants to broadcast to them, in the presence of Byzantine faulty nodes. We consider design of efficient algorithms for BB in synchronous point-to-point networks, where the rate of transmission over each communication link is limited by its "link capacity". The throughput of a particular BB algorithm is defined as the average number of bits that can be reliably broadcast to all fault-free nodes per unit time using the algorithm without violating the link capacity constraints. The capacity of BB in a given network is then defined as the supremum of all achievable BB throughputs in the given network, over all possible BB algorithms.

This paper proves a necessary and sufficient condition for the existence of iterative, algorithms that achieve approximate Byzantine consensus in arbitrary directed graphs, where each directed edge represents a communication channel between a pair of nodes. The class of iterative algorithms considered in this paper ensures that, after each iteration of the algorithm, the state of each fault-free node remains in the convex hull of the states of the fault-free nodes at the end of the previous iteration. The following convergence requirement is imposed: for any ε > 0, after a sufficiently large number of iterations, the states of the fault-free nodes are guaranteed to be within ε of each other.

In this paper, we make a case for using watchdogs to protect against misbehavior in dense wireless networks. We introduce “Generalized Watchdogs” and identify when and how watchdogs can be necessary and sufficient against misbehavior. We study feasibility of watchdog approach and show that the order of capacity bounds is preserved asymptotically even with watchdogs. We use generalized watchdogs to design protocols to improve both security and performance of TCP over wireless networks such that the application at the destination never accepts a corrupted packet and we achieve this without modifying TCP. We show that a strict dependence on availability and success of watchdogs can lead to “watchdog induced losses” and establish their effects on TCP throughput. We then propose solutions to deal with these losses and make watchdogs intelligent so they can tune the overheads incurred. With hop-by-hop verification of packet correctness, we ensure that tampered packets are not forwarded in the network and thus save potential wastage of network resources. We use NS-2 simulations of both controlled as well as realistic network scenarios, to show that watchdogs can provide simple, lightweight and reliable means of misbehavior detection, tolerance and most importantly “deterrence” while saving costs of security infrastructure. With a combination of intelligent watchdogs and source coding, and by leveraging route adaptation, our scheme achieves twice the throughput of a cryptographic alternative and that too in presence of as high as 30% packet tampering.

Opportunistic routing emerged as a novel technique to cope with the problem of highly unpredictable and lossy wireless channels in urban wireless mesh networks. However, existing opportunistic routing protocols only consider single-radio wireless nodes, and assume that all the nodes work on the same channel, without exploiting possible concurrent transmissions by multi-radio nodes over orthogonal channels provided by IEEE 802.11 protocols. Examples show that simply integrating existing channel assignment schemes and the opportunistic routing technique may not achieve satisfactory system performance. In this paper, we present WACA, which is a Workload-Aware Channel Assignment algorithm for opportunistic routing in multi-channel, multi-radio wireless mesh networks. Evaluation results show that WACA always achieves highest average throughput among the evaluated algorithms, and its median throughput is at least 16.1% higher than the compared ones.

This paper considers networked systems and develops distributed algorithm that is resilient against potential packet drops in the communication links between system components. We apply this algorithm to the problem of coordinating distributed energy resources (DERs) for the provision of ancillary services in electrical networks, e.g., reactive power support for voltage control. In this problem, each system component can contribute a certain amount of active and/or reactive power, bounded from above and (possibly) below by capacity constraints, and the objective is to coordinate the components so as to collectively provide a predetermined total amount of active and/or reactive power. In the algorithm we propose to address this problem, each DER maintains a set of variables and updates them through information exchange with neighboring DERs. We show that, as long as the underlying graph that describes the information exchange between components is strongly connected, and the predetermined total amount of active and/or reactive power does not violate (upper or lower) total capacity constraints, DERs can use this approach to calculate, in a distributed fashion, their fair contribution (subject to their capacity constraints). We show that the proposed algorithms reach almost surely convergence to the fair solution, even in the presence of communication link failures.

Abstract We propose a link layer protocol and link‐state routing protocol suite for multi‐channelad hocnetworks. The proposed protocol suite addresses several practical issues that arise when nodes equipped with two radio interfaces want to utilize available channels. The routing layer makes a hybrid channel assignment where one interface is fixed and the other is switchable. Based on that, the routing layer runs a shortest path routing algorithm augmented with channel diversity. The link layer implements a slotted structure to minimize broadcast overhead inherent to multi‐channel networks. By using flow‐ and packet‐level simulators, we make some important observations. First, a hybrid channel assignment is good for connectivity and amenable to shortest‐path routing. Second, seeking a shortest‐path can be a better routing strategy in terms of global system throughput than complex channel‐diverse routing. Third, channel switching delay is not a throttling factor in terms of global system throughput. Copyright © 2010 John Wiley & Sons, Ltd.

Abstract The RFID reader collision problem, in which an RFID reader's interrogation is interfered by other concurrent readers' transmission, is considered an important issue to reliable operation and thus to the wide‐spread deployment of RFID networks. In this paper, we present modeling and analysis of the RFID reader collision problem. We observe asymmetry between an RFID reader's and a tag's communication capabilities and develop an RFID radio model based on the asymmetry. By the model, we characterize the spatial reuse of RFID reader networks, and deriveconcurrent interrogation distancebeyond which readers can transmit simultaneously without causing collision and the carrier sense threshold corresponding to the distance. We also examine the dual‐channel mode where available bandwidth is divided into two channels by which reader‐to‐tag communication and tag‐to‐reader communication are separated. We analyze and evaluate the performance of the dual‐channel mode in terms of spatial reuse and interrogation completion time. Copyright © 2010 John Wiley & Sons, Ltd.

Recently, it has been shown that a simple, distributed CSMA algorithm can achieve throughput-optimality. However, the optimality is established under the ideal carrier sensing assumption, i.e., each link can precisely sense the presence of other active links in its neighborhood. This paper, in contrast, investigates the achievable throughput of the CSMA algorithm under imperfect carrier sensing. The main result is that CSMA can achieve an arbitrary fraction of the capacity region if certain access probabilities are set appropriately. To establish this result, we use the perturbation theory of Markov chains.

We consider the problem of maximizing the throughput of Byzantine agreement, when communication links have finite capacity. Byzantine agreement is a classical problem in distributed computing. In existing literature, the communication links are implicitly assumed to have infinite capacity. The problem changes significantly when the capacity of links is finite. We define the throughput and capacity of agreement, and identify necessary conditions of achievable agreement throughputs. We propose an algorithm structure for achieving agreement capacity in general networks. We also introduce capacity achieving algorithms for two classes of networks: (i) arbitrary four-node networks with at most 1 failure; and (ii) symmetric networks of arbitrary size.

Due to the limitation of radio spectrum resource and fast growing of wireless applications, careful channel allocation is highly needed to mitigate the performance degradation of wireless networks because of interference among different users. While most of the existing works consider allocating fixed-width channels, combining contiguous channels may provide an alternative way to better utilize the available channels. In this paper, we study the problem of adaptive-width channel allocation from a game-theoretic point of view, in which the nodes are rational and always pursue their own objectives. We first model the problem as a strategic game, and show the existence of Nash equilibrium (NE), when there is no exogenous factor to influence players' behavior. We further propose a charging scheme to influence the players' behavior, by which the system is guaranteed to converge to a Dominant Strategy Equilibrium (DSE), a solution concept that gives participants much stronger incentives. We show that, when the system converges to a DSE, it also achieves global optimality, in terms of system-wide throughput without starvation. Numerical results verify that with our charging scheme, the system-wide throughput obtained is higher as compared to the throughput obtained when system is in NE.

With the growing deployment of wireless communication technologies, radio spectrum is becoming a scarce resource. Thus mechanisms to efficiently allocate the available spectrum are of interest. In this paper, we model the radio spectrum allocation problem as a sealed-bid reserve auction, and propose SMALL, which is a Strategy-proof Mechanism for radio spectrum ALLocation. Furthermore, we extend SMALL to adapt to multi-radio spectrum buyers, which can bid for more than one radio.

In this paper, we present an efficient deterministic algorithm for consensus in presence of Byzantine failures. Our algorithm achieves consensus on an L-bit value with communication complexity O(nL + n4L0.5 + n6) bits, in a network consisting of n processors with up to t Byzantine failures, such that t

Delay in a duty-cycled network occurs when the sender waits for its receiver to be awake. Exploiting multiple receivers instead of a single receiver at each hop allows the sender to use the node that wakes up the soonest and so reduce delay. However, current MAC-layer anycast protocols either suffer from high signaling or synchronization overhead and are only appropriate for low duty cycle, low traffic scenarios. In this paper, we propose Any-MAC - a generic, low overhead extension that can be applied to any existing asynchronous MAC protocol to enable MAC-layer anycast. The extensive research in duty-cycle protocols provides us many MAC protocols, each appropriate for a particular network and application scenario. Thus, to construct an anycast solution to reduce delay for a specific network scenario, Any-MAC simply needs to extend the appropriate MAC protocol designed for that scenario. By applying anycast to existing protocols, X-MAC and NPM, we show that Any-MAC uses only simple modification to the base protocols and improves the performance significantly. Our evaluations in ns-2 show that with Any-MAC, both protocols can achieve 30% improvements in delay by exploiting the inherent route level redundancy in the network.

In this paper, we propose to reduce the effect of rate-independent MAC overheads in random access protocols by partitioning the transmission channel spectrum into a narrow channel and a wide channel. The narrow channel is used for transmitting the short packets (approximately 100 bytes long) and the wide channel is used for transmitting the longer packets. We intend to use multiple radios, one each for the different channel partitions. Narrow width channels have a reduced capacity, which lowers the maximum transmission rate achievable on these channels. As a result, the channel wastage due to the rate-independent MAC overheads can be reduced. We propose a protocol called WiSP (channel Width Selection based on Packet size) to estimate the appropriate channel widths depending on the relative traffic load involving short and long packets in the network. We evaluate our protocol using extensive simulations and demonstrate its effectiveness in achieving higher throughputs. We propose our algorithm to complement the frame aggregation (an existing approach that aggregates multiple packets to be sent in a single transmit opportunity) technique. We show that there are scenarios during which the frame aggregation can perform poorly, and show that our proposed algorithm can provide a good performance even in those situations when used along with frame aggregation.

We present two singulation schemes for passive RFID systems. The first scheme, called expanding horizon, uses interrogator transmit power control to singulate tags in concentric annuli. We show through analysis that this scheme is very time-efficient and conserves energy. Our second scheme is a combination parallel interrogation and TDMA scheme that applies to multiple interrogator situations. It leverages the capture effect to singulate many tags, even when these tags may be receiving signals from multiple interrogators. This provides a time-efficient scheme, as shown in our simulations.

We consider exploiting space-time correlations of passive RFID tags for localization and tracking. Consider tags with storage memory distributed densely in space. Users move through the field, scanning the tags. Subsets of these tags are space-time correlated with respect to the user's trajectory. For example, if two adjacent tags are scanned close together in time, they are highly correlated. We can represent this correlation value as a weighted virtual arrow pointing from the earlier scanned tag to the later scanned tag. A user continuously calculates these arrows, and stores them locally in the tags, forming a digital path, for localization and tracking of herself by other users. We specify several of these correlation functions and evaluate them experimentally. We provide statistical measures of performance, as well as visualizations of the resulting arrow fields created by users.

Significant research effort has been directed towards the design and performance analysis of imperfect scheduling policies for wireless networks. These imperfect schedulers are of interest despite being sub-optimal, as they allow for more tractable implementation at the expense of some loss in performance. However much of this prior work takes a uniform scaling approach to analyzing scheduling performance, whereby the performance of a scheduling policy is characterized in terms of a single scalar quantity, the efficiency-ratio. While suitable for characterizing worst-case performance, this approach limits one's ability to understand the different extents of performance degradation that may be experienced by different links in a network. Such an understanding is very valuable when average performance is of greater interest than the worst-case, or when certain links are more important than others. Furthermore, once one approaches scheduler design with non-uniform performance guarantees in mind, one finds that simple modifications to well-known scheduling algorithms can yield substantially improved non-uniform scaling results compared to the original algorithms. In this paper, we make a comprehensive case for adopting such an approach by presenting non-uniform scaling results for a set of algorithms that are variants of well-known algorithms from the class of maximal schedulers.

We consider the problem of misbehavior detection in wireless networks. A commonly adopted approach is to exploit the broadcast nature of the wireless medium, where nodes monitor their downstream neighbors locally using overheard messages. We call such nodes the Watchdogs. We propose a lightweight misbehavior detection scheme which integrates the idea of watchdogs and error detection coding. We show that even if the watchdog can only observe a fraction of packets, by choosing the error detection code properly, an attacker can be detected with high probability while achieving throughput arbitrarily close to optimal. Such properties reduce the incentive for the attacker to attack. We then consider the problem of locating the misbehaving node and propose a simple protocol, which locates the misbehaving node with high probability. The protocol requires exactly two watchdogs per unreliable relay node.

We consider the problem of selfish misbehavior in scheduling algorithms of wireless networks. All wireless scheduling algorithms are designed under the assumption that network users will follow the algorithm specifications. In this paper, we study two scheduling algorithms in which a selfish user might misbehave in order to achieve better performance. In the first case, we consider a network that implements cross-layered rate control mechanism to determine arrival rate of users as well as link schedules. We explain a scenario in which a selfish user obtains extra throughput by misleading the scheduling component of the network. We find an equivalent optimization framework that captures misbehavior pattern of the selfish user. We present a solution to prevent such a greedy behavior by imposing a cost term on the utility function of the users. In the second part of the work, we consider the family of random access scheduling algorithms in which users of the wireless network wait for randomly chosen back-off intervals before accessing the medium. A selfish user might wait for smaller back-off in order to obtain an unfair advantage. We present a comparison method to detect such a greedy misbehavior.

In this paper, we propose Opportunistic Carrier Prediction (OCP) that jointly addresses exposed terminal and hidden terminal problems in wireless networks. OCP is based on the rationale that past interference information can be a good indicator for the outcome of future packet delivery. Each OCP sender maintains a summary of past interference information and opportunistically accesses the channel when it is confident that the packet transmission will be successful and cause no collision to other flows. To realize OCP, we propose (1) a novel data structure for each sender to summarize the interference information and (2) physical layer preemptive decoding scheme for each sender to collect the identities of the interferers. We show that OCP improves the system throughput by up to 170%, packet delivery success ratio by up to 400% in random topologies, while almost eliminating starvation.

In this paper, we consider the problem of maximizing the throughput of Byzantine agreement, when communication links have finite capacity. Byzantine agreement is a classical problem in distributed computing, with initial solutions presented in the seminal work of Pease, Shostak and Lamport. The notion of throughput here is similar to that used in the networking/communications literature on unicast or multicast traffic. We identify necessary conditions for an agreement throughput of R to be achievable. We also provide tight sufficient conditions by construction for agreement throughput R in four-node networks.

In this work, we have proposed to partition a channel into a narrow and a wide subchannel for overcoming MAC overheads. The narrow subchannel is used for sending short packets and the wide channel is used for sending long packets. We have proposed a centralized algorithm for partitioning the channel and have discussed some interesting problems when extending this to a distributed algorithm.

In this abstract, we have studied the problem of channel assignment in multi-radio, multi-channel wireless mesh networks, considering the support of opportunistic routing technique. First, we have formally modeled the channel assignment problem. Second, we have presented our multichannel opportunistic routing protocol. Third, we have shown the infeasibility of traditional channel assignment schemes, in the context of opportunistic routing. Finally, we have proposed a workload-aware channel assignment and routing algorithm, which can take advantages from both opportunistic throughput gain and multi-channel throughput gain.

We create a distributed storage infrastructure by embedding passive RFID tags in trees, for forest search and rescue. As a hiker moves through the forest, her reader writes a unique identifier (ID) and increasing sequence numbers (SNs) to tags, called (ID,SN) pairs. This creates a digital path for searchers to follow if the hiker is lost. Since tag memory is limited, hikers must share this constrained resource to preserve their digital paths. At each tag, we consider a hiker overwriting an existing (ID,SN) pair if the tag is already full, according to one of four algorithms. In Oldest Selection (OS), the hiker deletes the oldest (ID,SN) pair. In Random Selection (RS), the hiker randomly deletes an (ID,SN) pair. In Highest Frequency Selection (HFS), the hiker deletes the (ID,SN) pair associated with the ID that she has seen the most in previous tag encounters. In Lowest Delete Frequency Selection (LDFS), the hiker deletes the (ID,SN) pair associated with the ID that she has deleted the least in previous tag encounters. HFS performs the best, but requires hikers to remember the number of ID encounters in the past, for each hiker ID.

In this work, we introduce the problem of reading and writing to a system of high storage passive RFID tags. We consider design goals, based on motivating applications. We consider access protocols and provide preliminary performance results. Future work includes defining more detailed access protocols (and in which scenarios they are applicable). We also plan to evaluate these protocols more extensively through simulations and experiments using RFID hardware.

This paper studies the reliable broadcast problem in a radio network with locally bounded failures. We present a sufficient condition for achievability of reliable broadcast in a general graph subject to Byzantine/crash-stop failures. We then consider the problem of reliable broadcast in an infinite grid (or finite toroidal) radio network under Byzantine and crash-stop failures. We present bounds on the maximum number of failures that may occur in any given neighborhood without rendering reliable broadcast impossible. For the Byzantine failure model, we describe an algorithm which is optimal for the grid network model, as it tolerates faults up to a previously established upper bound for this model. Our results indicate that it is possible to achieve reliable broadcast if slightly less than one-fourth fraction of nodes in any neighborhood are faulty. We also show that reliable broadcast is achievable with crash-stop failures if slightly less than half the nodes in any given neighborhood may be faulty.

In wireless sensor networks (WSN), energy efficiency is crucial to achieving satisfactory network lifetime. The most commonly used and may be the only efficient method to reduce the energy consumption significantly is to turn off the radios most of the time, except when it has to participate in data communication. The key challenge is to operate the radio at a low duty cycle but still ensure the delay is relatively low. Various power-saving medium-access control (MAC) protocols have been proposed along this thread. However, most of such protocols focus on a point-to-point communication setting, in which a node will drop an overheard packet if it is not the destination. On the other hand, cooperative wireless communication has been drawing extensive attention in the past few years. Node cooperation has been exploited to reduce end-to-end delay, improve transmission reliability, etc. However, not much has been done in utilizing node cooperation to save energy. This idea may sound absurd since cooperation requires more nodes involved in a communication and would result in more energy being consumed. But is this true? In this paper, we will exploit the possibility of cooperative power saving in wireless ad-hoc networks. The trade-off between energy consumption and delay will be studied. Interestingly, our analytical and simulation results show that cooperation can indeed help achieve a better delay-power consumption trade-off. Our results also show that cooperation together with asymmetric power allocation can achieve the optimal delay-power trade-off.

While a network with stationary nodes can provide large capacity in many current wireless systems, a network with mobile users suffers from severe performance degradation. This happens due to quick channel variation and its resulting protocol overheads that are especially large for multiuser multiple-input multiple-output (MIMO) systems. In this paper, we propose a relay-assisted multiuser MIMO downlink system to support highly mobile wireless access. Through a theoretical throughput analysis that explicitly considers the protocol overheads, we show that the MIMO relay significantly enhances the sum throughput of the system.

A joint congestion control, channel allocation and scheduling algorithm for multi-channel multi-interface multi- hop wireless networks is discussed. The goal of maximizing a utility function of the injected traffic, while guaranteeing queue stability, is defined as an optimization problem where the input traffic intensity, channel loads, interface to channel binding and transmission schedules are jointly optimized by a dynamic algorithm. Due to the inherent NP-Hardness of the scheduling problem, a simple centralized heuristic is used to define a lower bound for the performance of the whole optimization algorithm. The behavior of the algorithm for different numbers of channels, interfaces and traffic flows is shown through simulations.

We present a dynamic spatial backoff method to resolve channel contention in wireless ad-hoc networks. We argue that each node should adjust its receiver sensitivity level according to the mean channel gain of its particular transmitter-receiver link, in order to see the full benefit of spatial backoff and improve the throughput. We designed a distributed algorithm that adjusts each transmitters carrier sense threshold and transmission rate dynamically based on local information and limited receiver feedback, for wireless channels that have small-scale multipath fading. We evaluated the algorithm using different topologies, under various fading conditions. Results show that our algorithm is able to achieve aggregate throughput near or better than the maximum achievable by the static scheme, without a priori knowledge of the network topology or fading condition.

M term as the Editor-in-Chief (EIC) of Transactions on Mobile Computing (TMC) ended on 31 December 2007. I would like to take this opportunity to thank the many individuals who have contributed to the success of TMC. First, I would like to thank all of the Associate Editors who have served on the editorial board of TMC. We could not have maintained the high standards of the journal and the timeliness of the review process without their conscientious work. My thanks to Jennifer Carruth, whose help as the Transactions Assistant has been invaluable. Her contributions to TMC have helped us in maintaining a relatively short submission-to-decision time for the submitted manuscripts, and also in making the review process a positive experience for the authors. The TMC Steering Committee, chaired by Rajesh Gupta, offered useful advice throughout my tenure as EIC. Their guidance has been important in setting editorial policies for the journal. Many IEEE Computer Society staff members were also of signifi cant assistance during my tenure. In particular, I would like to thank Alicia Stickley, Suzanne Wagner, Kimberly Sperka, and Angela Burgess for their support. Last but not least, my thanks to all of the authors who submitted their manuscripts to TMC and all of the reviewers without whose help we could not maintain the high quality of TMC. Since its inception in 2002, with Tom La Porta as the fi rst EIC, TMC has grown signifi cantly. TMC was published quarterly in 2002 and has been published monthly since 2006. Along with the increasing reputation of TMC, the number of submissions has also increased signifi cantly. Despite the increase in volume, we have been able to maintain high quality due to the hard work of our editors and reviewers. I believe that TMC has now established itself as a leading journal in the area of mobile computing and wireless networking. It is with great pleasure that I welcome Mani B. Srivastava as the new EIC of TMC. Mani has previously served in leadership roles for other publications, and also on the TMC Editorial Board. I have no doubt that TMC will continue to grow under his leadership. I trust that our readers and authors will continue supporting TMC over the years to come.

Abstract Using directional antennas can be beneficial for wireless ad hoc networks consisting of a collection of wireless hosts. The most important benefit includes a reduction of the radio interference. Thus, it can significantly increase the spatial reuse, thereby improving the network throughput. To best utilize directional antennas, a suitable Medium Access Control (MAC) protocol must be designed. Current MAC protocols, such as the IEEE 802.11 standard, do not benefit when using directional antennas, because these protocols have been designed for omnidirectional antennas. In this paper, we present modified MAC protocols suitable for 802.11 based ad hoc networks using directional antennas. Our comprehensive simulation results demonstrate the performance improvement obtained with the proposed protocols. Copyright © 2007 John Wiley & Sons, Ltd.

We consider the problem of reliable broadcast in a wireless network in which nodes are prone to failure. Each node can fail independently with probability p. Failures are permanent. The primary focus is on Byzantine failures, but we also handle crash-stop failures. We consider two network models: a regular grid, and a random network. Our necessary and sufficient conditions for the Byzantine failure model indicate that p should be less than frac12, and the critical node degree is Theta(dmin+(lnn/ln(1/2p))+ln(1/2(1-p))) (where dminis the minimum node degree associated with a non-empty neighborhood, and is a small constant). For a random network we prove that, for failure probability less than frac12, the critical average degree for reliable broadcast is O(lnn/frac12-p+frac12ln(1/2(1-p))). We briefly discuss the issue of crash-stop failures for which we have results that improve upon previously existing results for this model, when p approaches 0. We also identify an interesting similarity in the structure of various known results in the literature pertaining to a set of related problems in the realm of connectivity and reliable broadcast.

This paper argues for the need to address the issue of multi-channel network performance under constraints on channel switching. We present examples from emergent directions in wireless networking to motivate the need for such a study, and introduce some models to capture channel switching constraints. For some of these models, we study connectivity and capacity of a wireless network comprising n randomly deployed nodes, equipped with a single interface each, when there are c=O(logn) channels of equal bandwidth W/c available. We consider an adjacent (c,f) channel assignment where a node may switch between f adjacent channels, but the adjacent channel block is randomly assigned. We show that the per-flow capacity for this channel assignment model is Theta(Wradic(f/cnlogn)). We then show the adjacent (c,2) assignment maps to the case of untuned radios. We also consider a random (c,f) assignment where each node may switch between a pre-assigned random subset of f channels. For this model, we prove that per-flow capacity is O(Wradic(prnd/nlogn)) (where prnd=1-(1-f/c)(1-f/(c-1))...(1-f/(c-f+1)) and Omega(Wradic(f/cnlogn))).

The majority of existing wireless rate controls are based on the implicit assumption that frames are corrupted due to the random, arbitrary environmental and thermal noises. They generally reduce the channel rate on frame losses, trading lower efficiency in frequency band utilization for more robust modulation so that the current noise level may be tolerable. In highly interfered wireless networks where frames are lost mainly due to interference from other wireless transceivers, simply reducing the channel rate prolongs the frame transmission time and therefore aggravates frame loss ratio. This positive feedback in the rate control loop quickly diverges the interfered transceivers into a suboptimal channel rate and drives the network into a state with high interference. In the worst case, interfered transceivers can be starved. In this paper we present RAF, the rate-adaptive framing that jointly controls the channel rate and frame size according to the observed interference patterns and noise level at the receiver. Based on the inputs from physical layer carrier sense, the receiver derives the optimal channel rate and frame size that maximize throughput, and informs the transmitter of such optimal configuration in a few bits in the per-frame acknowledgement. Through intensive simulations we show that RAF consistently outperforms ARF, RBAR, and OAR in all simulated scenarios.

We argued for the need to study the performance of multi-channel networks in situations where there are constraints on channel switching. We proposed some constraint models in [1] to capture some expected constraints, and analyzed two such models, viz., adjacent (c,f) assignment and random (c,f) assignment. We studied the impact of such restricted switching, quantified by the parameter f (where f is the number of channels an individual node may switch to) in the regime c = O(log n). One of our proposed models was termed random (c,f) assignment.

Abstract — As the use of sensor networks increases, security in this domain becomes a very real concern. One fundamental aspect of providing confidentiality and authentication is key distribution. While public-key encryption has provided these properties historically, sensors are resource constrained and benefit from symmetric key approaches. In this work, we propose a novel protocol for symmetric key distribution that uses the multiple channels available on sensor hardware. This channel diversity, along with spatial diversity of device locations, allows neighboring sensors to establish secure link keys from plaintext keys that are broadcast by sensors in their neighborhood. In particular, we show that using even one extra channel during the initialization procedure significantly improves the security of key establishment. Via analysis and simulation, we show that our protocol performs well in terms of network connectivity and resilience to colluding malicious devices, when compared to previous work. We show that our protocol can achieve over 90 % connectivity among neighboring sensors with link keys that are uncompromised even when 80 % of the devices in the network are malicious and collude. Finally, we present a thorough discussion of the comparative advantages and disadvantages of our approach compared to previous techniques. I.

We study the problem of achieving global broadcast in a radio network where a node can multicast messages to all of its neighbors (that is, nodes within some given distance r), and up to t nodes in any single neighborhood may be corrupted. Previous work assumes that corrupted nodes can neither cause collisions nor spoof addresses of honest nodes. In this work, we eliminate these assumptions and allow each faulty node to cause a (known) bounded number of collisions and spoof the addresses of arbitrary other nodes. We show that the maximum tolerable t in this case is identical to the maximum tolerable t when collisions and address spoofing are not allowed. Thus, by causing collisions and spoofing addresses an adversary may be able to degrade the efficiency of achieving broadcast, but it cannot affect the feasibility of this task.

We investigate the possibility of using directional antennas for medium access control in wireless ad hoc networks. Previous research in ad hoc networks typically assumes the use of omnidirectional antennas at all nodes. With omnidirectional antennas, while two nodes are communicating using a given channel, MAC protocols such as IEEE 802.11 require all other nodes in the vicinity to remain silent. With directional antennas, two pairs of nodes located in each other's vicinity may potentially communicate simultaneously, increasing spatial reuse of the wireless channel. Range extension due to higher gain of directional antennas can also be useful in discovering fewer hop routes. However, new problems arise when using directional beams that simple modifications to 802.11 may not be able to mitigate. This paper identifies these problems and evaluates the tradeoffs associated with them. We also design a directional MAC protocol (MMAC) that uses multihop RTSs to establish links between distant nodes and then transmits CTS, DATA, and ACK over a single hop. While MMAC does not address all the problems identified with directional communication, it is an attempt to exploit the primary benefits of beamforming in the presence of some of these problems. Results show that MMAC can perform better than IEEE 802.11, although we find that the performance is dependent on the topology and flow patterns in the system.

In distributed multiple access control protocols, two categories of overhead are usually associated with contention resolution. One is channel idle overhead, where all contending stations are waiting to transmit. Another is collision overhead, which occurs when multiple contending stations attempt to transmit simultaneously. Either idle overhead or collision overhead being large, contention resolution algorithm would be inefficient. Prior research work tries to minimize both the idle and the collision overheads using various methods. In this paper, we propose to apply "pipelining" techniques to the design of multiple access control protocol so that channel idle overhead could be (partially) hidden and the collision overhead could be reduced. While the concept of pipelined scheduling can be applied to various MAC protocol designs in general, in this paper, we focus on its application to IEEE 802.11 DCF. In particular, an implicitly pipelined dual-stage contention resolution MAC protocol (named DSCR) is proposed. With IEEE 802.11, the efficiency of contention resolution degrades dramatically with the increasing load due to high probability of collision. Using the implicit pipelining technique, DSCR hides the majority of channel idle time and reduces the collision probability, hence, improves channel utilization, average access delay, and access energy cost over 802.11 significantly both in wireless LANs and in multihop networks. The simulation results, as well as some analysis, are presented to demonstrate the effectiveness of DSCR.

To reduce medium access control (MAC) overhead and improve channel utilization, there has been extensive research on dynamically adjusting the channel access behavior of a contending station based on channel feedback information. This paper explores an alternative approach, named pipelined packet scheduling, to reduce the MAC overhead. MAC overheads can be divided into bandwidth-dependent and bandwidth-independent components and these overheads can both be reduced by using split-channel pipelining mechanisms, as demonstrated in this paper. In the past, pipelining mechanisms have not been well studied. This paper introduces two total pipelining schemes that attempt to fully pipeline contention resolution with data transmission. Further, the paper identifies shortcomings of total pipelining in the wireless environment and proposes a partial pipelining approach to overcome these shortcomings. Simulation results show that substantial performance improvement in channel utilization, average packet access delay, and access energy cost can be achieved with a properly designed scheme.

The aggregate throughput of a wireless ad hoc network depends on the channel capacity, channel utilization (i.e., the fraction of channel capacity used for generating good put), and the concurrent transmissions allowed in the network. While channel utilization is determined by MAC overhead, physical carrier sense has been used as an effective way to avoid interference and exploit spatial reuse. Prior research has attempted to identify the optimal carrier sense range that can maximize the aggregate throughput. However, the impact of MAC overhead has been ignored. In this paper, we use both an analytical model and simulation results to show that MAC overhead has significant impact on the choice of optimal carrier sense range. If MAC overhead is not taken into account properly in determining the optimal carrier sense range, the aggregate throughput can suffer a significant loss.

Energy efficient protocols are important in ad hoc networks since battery life for wireless devices is limited. The IEEE 802.11 protocol specifies a simple power save mechanism (PSM) to conserve energy. Packets are advertised for a fixed length of time, known as an advertisement window, at epochs known as beacon intervals. However, the protocol needlessly wastes energy when traffic is relatively light in a network. In this paper, we address this problem by proposing the use of carrier sensing to dynamically adjust the size of the advertisement windows. The adjustment is based on the amount of traffic that needs to be advertised in the current window as opposed to the static window size used by 802.11 PSM. Carrier sensing is used for two different aspects of our protocol. First, carrier sensing is used as an energy efficient method to provide a binary signal which lets neighbors know if a node intends to advertise any packets in the upcoming window. Second, carrier sensing is used as a mechanism for nodes to keep track of whether their neighbors have already stopped listening for advertisements and possibly returned to sleep. Using the ns-2 simulator we show that our techniques can significantly reduce the energy consumption of 802.11 PSM while only slightly increasing latency

This paper studies how the capacity of a static multi-channel network scales as the number of nodes, n, increases. Gupta and Kumar have determined the capacity of single-channel networks, and those bounds are applicable to multi-channel networks as well, provided each node in the network has a dedicated interface per channel.In this work, we establish the capacity of general multi-channel networks wherein the number of interfaces, m, may be smaller than the number of channels, c. We show that the capacity of multi-channel networks exhibits different bounds that are dependent on the ratio between c and m. When the number of interfaces per node is smaller than the number of channels, there is a degradation in the network capacity in many scenarios. However, one important exception is a random network with up to O(log n) channels, wherein the network capacity remains at the Gupta and Kumar bound of Θ(W√noverlog n) bits/sec, independent of the number of interfaces available at each node. Since in many practical networks, number of channels available is small (e.g., IEEE 802.11 networks), this bound is of practical interest. This implies that it may be possible to build capacity-optimal multi-channel networks with as few as one interface per node. We also extend our model to consider the impact of interface switching delay, and show that in a random network with up to O(log n) channels, switching delay may not affect capacity if multiple interfaces are used.

We consider the problem of reliable broadcast in an infinite grid (or finite toroidal) radio network under Byzantine and crash-stop failures. We present bounds on the maximum number of failures that may occur in any given neighborhood without rendering reliable broadcast impossible. We improve on previously proved bounds for the number of tolerable Byzantine faults [6]. Our results indicate that it is possible to achieve reliable broadcast if slightly less than one fourth fraction of nodes in any neighborhood are faulty, and impossible otherwise. We also show that reliable broadcast is achievable with crash-stop failures if slightly less than half the nodes in any given neighborhood may be faulty. In particular, we establish exact thresholds under a specific distance metric.

A hybrid wireless network is an extension to an infrastructure network, where a mobile host may connect to an access point using multi-hop wireless routes, via other mobile hosts. The access points are configured to operate on one of multiple available channels. Mobile hosts and wireless routers can select its operating channel dynamically through channel switching. In this environment, we propose a routing protocol that finds routes to balance load among channels while maintaining connectivity. The protocol works with nodes equipped with a single network interface, which distinguishes our work with other multi-channel routing protocols that require multiple interfaces per node. The protocol discovers multiple routes to multiple access points, possibly operating on different channels. Based on traffic load information, each node selects the "best" route to an access point, and synchronizes its channel with the access point. With this behavior, the channel load is balanced, removing hot spots and improving channel utilization. The protocol assures every node has at least one route to an access point, where all intermediate nodes are operating on the same channel. Our simulation results show that the proposed protocol successfully adapts to changing traffic conditions and improves performance over a single-channel protocol and a multi-channel protocol with no load balancing.

Multiple channels are available for use in IEEE 802.11. Multiple channels can increase the available network capacity, but require new protocols to exploit the available capacity. This paper studies the problem of improving the capacity of multi-channel wireless networks by using multiple interfaces. We consider the scenario when multiple interfaces are available, but the number of available interfaces is lesser than the number of available channels. We provide a classification of interface assignment strategies, and propose a new strategy that does not require modifications to IEEE 802.11. We also identify routing heuristics that are suitable for use with the proposed interface assignment strategy.

This paper presents TCP-DCR, a set of simple modifications to the TCP protocol to improve its robustness to channel errors in wireless networks. TCP-DCR is based on the simple idea of allowing the link-level mechanism to recover the packets lost, due to channel errors, thereby limiting the response of the transport protocol to mostly congestion losses. This is done by delaying the triggering of congestion response algorithms for a small bounded period of time /spl tau/ to allow the link-level retransmissions to recover the loss due to channel errors. If at the end of the delay /spl tau/ the packet is not recovered, then it is treated as a packet lost due to congestion. We analyze TCP-DCR to show that the delay in congestion response does not impact the fairness towards the native implementations of TCP that respond to congestion immediately after receiving three dupacks. We evaluate TCP-DCR through simulations to show that it offers significantly better performance when channel errors contribute more towards packet losses in the network with no or minimal impact on the performance when congestion is the primary cause for packet loss. We also present an analysis to show that the number of flows in the network significantly influences protocol evaluation in the wireless networks.

Wireless medium access control (MAC) protocols such as IEEE 802.11 use distributed contention resolution mechanisms for sharing the wireless channel. In this environment, selfish hosts that fail to adhere to the MAC protocol may obtain an unfair throughput share. For example, IEEE 802.11 requires hosts competing for access to the channel to wait for a "backoff" interval, randomly selected from a specified range/before initiating a transmission. Selfish hosts may wait for smaller backoff intervals than well-behaved hosts, thereby obtaining an unfair advantage. We present modifications to the IEEE 802.11 protocol to simplify detection of such selfish hosts and analyze the optimality of the chosen strategy. We also present a penalty scheme for punishing selfish misbehavior. We develop two misbehavior models to capture the behavior of misbehaving hosts. Simulation results under these misbehavior models indicate that our detection and penalty schemes are successful in handling MAC layer misbehavior.

This paper presents several distributed algorithms that cause a token to continually circulate through all the nodes of a mobile ad hoc network. An important application of such algorithms is to ensure total order of message, delivery in a group communication service. Some of the proposed algorithms are aware of, and adapt to changes in the ad hoc network topology. When using a token circulation algorithm, a round is said to complete when every node has been visited at least once. Criteria for comparing the algorithms include the average time, required to complete a round, number of bytes sent per round, and number of nodes visited per round. Comparison between the proposed algorithms is performed using simulation results obtained from a detailed simulation model (with ns-2 simulator). We also give a rigorous worst-case analysis of the proposed LR algorithm, which gives the best overall performance in the simulation.

For increasing the life of sensor networks, each node must conserve energy as much as possible. In this paper, we propose a protocol in which energy is conserved by amortizing the energy cost of communication over multiple packets. In addition, we allow sensors to control the amount of buffered packets since storage space is limited. To achieve this, a two-radio architecture is used which allows a sensor to "wakeup" a neighbor with a busy tone and send its packets for that destination. However, this process is expensive because all neighbors must awake and listen to the primary channel to determine who is the intended destination. Therefore, triggered wakeups on the primary channel are proposed to avoid using the more costly wakeup procedure. We present a protocol for efficiently determining how large the period for these wakeups should be such that energy consumption is reduced.

Fairness is an important issue when accessing a shared wireless channel. With fair scheduling, it is possible to allocate bandwidth in proportion to weights of the packet flows sharing the channel. This paper presents a fully distributed algorithm for fair scheduling in a wireless LAN. The algorithm can be implemented without using a centralized coordinator to arbitrate medium access. The proposed protocol is derived from the Distributed Coordination Function in the IEEE 802.11 standard. Simulation results show that the proposed algorithm is able to schedule transmissions such that the bandwidth allocated to different flows is proportional to their weights. An attractive feature of the proposed approach is that it can be implemented with simple modifications to the IEEE 802.11 standard.

Currently, a TCP sender considers all losses as congestion signals and reacts to them by throttling its sending rate. With Internet becoming more heterogeneous with more and more wireless error-prone links, a TCP connection may unduly throttle its sending rate and experience poor performance over paths experiencing random losses unrelated to congestion. The problem of distinguishing congestion losses from random losses is particularly hard when congestion is light: congestion losses themselves appear to be random. The key idea is to "de-randomize" congestion losses. This paper proposes a simple biased queue management scheme that "de-randomizes" congestion losses and enables a TCP receiver to diagnose accurately the cause of a loss and inform the TCP sender to react appropriately. Bounds on the accuracy of distinguishing wireless losses and congestion losses are analytically established and validated through simulations. Congestion losses are identified with an accuracy higher than 95% while wireless losses are identified with an accuracy higher than 75%. A closed form is derived for the achievable improvement by TCP endowed with a discriminator with a given accuracy. Simulations confirm this closed form. TCP-Casablanca, a TCP-Newreno endowed with the proposed discriminator at the receiver, yields through simulations an improvement of more than 100% on paths with low levels of congestion and about 1% random wireless packet loss rates. TCP-Ifrane, a sender-based TCP-Casablanca yields encouraging performance improvement.

In this paper, we discuss power save mechanisms that allow hosts to go to sleep to conserve energy. When sleeping hosts need to receive packets from other hosts, these hosts must somehow wake up the sleeping hosts. The paper discusses a busy-tone mechanism for this purpose, and an approach to improve the mechanism by using multiple busy tones. We generalize this protocol to develop the notion of multi-level power save mechanisms, and present some examples to illustrate this notion.

This work addresses deafness - a problem that appears when MAC protocols are designed using directional antennas. Briefly, deafness is caused when a transmitter fails to communicate to its intended receiver, because the receiver is beamformed towards a direction away from the transmitter. Existing CSMA/CA protocols rely on the assumption that congestion is the predominant cause of communication failure, and adopt backoff schemes to handle congestion. While this may be appropriate for omnidirectional antennas, for directional antennas, both deafness and congestion can be the reason for communication failures. An appropriate directional MAC protocol needs to classify the actual cause of failure, and react accordingly. This paper quantifies the impact of deafness on directional medium access control, and proposes a tone-based mechanism as one way of addressing deafness. The tone-based mechanism, ToneDMAC, assumes congestion as the default reason for communication failures, and applies a corrective measure whenever the cause is deafness. Simulation results indicate that ToneDMAC can alleviate deafness, and perform better than existing directional MAC protocols.

Providing anonymous connection service in mobile ad hoc networks is a challenging task. In addition to security concerns, performance concerns must be addressed properly as well. Chaum's mix method (Comms. of the ACM, vol.24(2), p.84-88, 1981) can effectively thwart an adversary's attempt at tracing packet routes and can hide the source and/or destination of packets. However, applying the mix method in ad hoc networks may cause significant performance degradation due to its non-adaptive mix route selection algorithm. We propose a dynamic mix routing algorithm to find topology-dependent mix routes for anonymous connections. Its effectiveness in improving network performance is validated by simulation results. We also address the potential degradation of anonymity due to dynamic mix routing.

The advances in wireless networking have enabled new paradigms in computing. An abundance of information and services provided by remote servers is expected to become available to wireless users. A fundamental issue in this environment is efficiently locating needed content. Such content may be in the form of files, services, or any other kind of data. In this paper, we describe an algorithm for efficient content location in location-aware ad hoc networks. The Geography-based Content Location Protocol (GCLP) makes use of physical location information to lower proactive traffic while reducing query cost. The results of our analysis show that GCLP performs favorably in terms of overhead and scalability.

This paper proposes a medium access control (MAC) protocol for ad hoc wireless networks that utilizes multiple channels dynamically to improve performance. The IEEE 802.11 standard allows for the use of multiple channels available at the physical layer, but its MAC protocol is designed only for a single channel. A single-channel MAC protocol does not work well in a multi-channel environment, because of the multi-channel hidden terminal problem . Our proposed protocol enables hosts to utilize multiple channels by switching hannels dynamically, thus increasing network throughput. The protocol requires only one transceiver per host, but solves the multi-channel hidden terminal problem using temporal synchronization. Our scheme improves network throughput signifiantly, especially when the network is highly congested. The simulation results show that our protocol successfully exploits multiple hannels to achieve higher throughput than IEEE 802.11. Also, the performance of our protocol is comparable to another multi-hannel MAC protocol that requires multiple transceivers per host. Since our protocol requires only one transceiver per host, it an be implemented with a hardware complexity comparable to IEEE 802.11.

This paper proposes a vehicle-to-vehicle communication protocol for cooperative collision warning. Emerging wireless technologies for vehicle-to-vehicle (V2V) and vehicle-to-roadside (V2R) communications such as DSRC are promising to dramatically reduce the number of fatal roadway accidents by providing early warnings. One major technical challenge addressed in this paper is to achieve low-latency in delivering emergency warnings in various road situations. Based on a careful analysis of application requirements, we design an effective protocol, comprising congestion control policies, service differentiation mechanisms and methods for emergency warning dissemination. Simulation results demonstrate that the proposed protocol achieves low latency in delivering emergency warnings and efficient bandwidth usage in stressful road scenarios.

Energy saving is a critical task for sensor networks with limited energy supply. Wakeup schemes that turn off sensors' radio when communication is not necessary have great potential in energy saving. However, existing wakeup schemes encounter critical tradeoffs between energy saving and wakeup latency, and little attention has been paid to reducing the packet end-to-end delay while preserving the energy saving capability. We argue that a long delay can be detrimental for large sensor networks. We propose a wakeup scheme that helps to achieve the balance between energy saving and end-to-end delay. The conditions under which the proposed scheme can show improvement are identified.

Flow control in a mobile ad hoc network (MANET) must face many new challenges such as frequent rerouting and bandwidth variation of the wireless links. TCP's implicit AIMD flow control performs poorly in this environment, because it often cannot keep up with the dynamics of the network. This paper explores the potential utility of explicit flow control in the MANET domain. To this end, we propose an end-to-end rate-based flow control scheme (called EXACT), where a flow's allowed rate is explicitly conveyed from intermediate routers to the end-hosts in each data packet's special control header. As a result, EXACT reacts quickly and precisely to re-routing and bandwidth variation, which makes it especially suitable for a dynamic MANET network and also discusses several supporting mechanisms required for such a scheme at the MAC and the transport layers. By ns-2 simulations, we show that EXACT outperforms TCP in terms of fairness and efficiency, especially in a highly dynamic MANET environment.

Recent years have witnessed the widespread deployment of IEEE 802.11 LANs in areas such as airports, campuses, and enterprises. These networks allow users to access network services and the Internet in remote locations and without the need Tor wires. The data rates for 802.11a, b and g far surpass that of wide-area cellular networks, however, the range of transmission of 802.11 is much less than that of cellular (250m versus 20km). Employing ad-hoc mode in 802.11 can extend traditional WLANs to multiple hops, thus increasing coverage and reducing the need for additional infrastructure. The amount of network extension (in terms of wireless hops) is limited by the density of the network (i.e., the availability of wireless devices that can serve as relays for other devices), and the scalability of stand-alone wireless ad-hoc networks. In this paper, we introduce a k-hop architecture and routing protocol utilizing a "beaconing" approach for route discovery and maintenance. We demonstrate through simulations the efficiency and reliability of our routing protocol in the presence of mobility and high node density.

For increasing the life of sensor networks, each node must conserve energy as much as possible. In this paper, we propose a protocol in which energy is conserved by amortizing the energy cost of communication over multiple packets. In addition, we allow sensors to control the amount of buffered packets since storage space is limited. To achieve this, a two-radio architecture is used which allows a sensor to "wakeup" a neighbor with a busy tone and send its packets for that destination. However, this process is expensive because all neighbors must awake and listen to the primary channel to determine who is the intended destination. Therefore, triggered wakeups on the primary channel are proposed to avoid using the more costly wakeup procedure. We present a protocol for efficiently determining how large the period for these wakeups should be such that energy consumption is minimized.

Selfish hosts in wireless networks that fail to adhere to the MAC protocol may obtain an unfair share of the channel bandwidth. We present modifications to the IEEE 802.11 backoff mechanism to simplify detection of such selfish hosts. We also present a correction scheme for penalizing greedy misbehavior which attempts to restrict the misbehaving nodes to a fair share of the channel bandwidth. Simulation results indicate that our detection and correction schemes are fairly successful in handling MAC layer misbehavior.

TCP uses packet loss as a feedback from the network to adapt its sending rate. TCP keeps increasing its sending rate as long as no packet loss occurs (unless constrained by buffer size). Alternative congestion avoidance techniques (CATs) have been proposed to avoid such "aggressive" behavior. These CATs use simple statistics on observed round-trip times and/or throughput of a TCP connection in response to variations in congestion window size. These CATs have a supposed ability to detect queue build-up.The objective of this paper is to question the ability of these CATs to reliably detect queue build-up under real network conditions. For this purpose, the sample coefficient of correlation between round-trip time and the number of packets in flight is analyzed for 14,218 connections over 737 Internet paths. These coefficients of correlation were extracted from a set of tcpdump traces collected by Vern Paxson.The coefficients of correlation measured confirm that the correlation between RTT and window size is often weak.

This paper presents an optimization of the power saving mechanism in the Distributed Coordination Function (DCF) in the IEEE 802.11 standard. In the IEEE 802.11 power saving mode specified for DCF, time is divided into so-called beacon intervals. At the start of each beacon interval, each node in the power saving mode periodically wakes up for a duration called the ATIM window. The nodes are required to be synchronized to ensure that all nodes wake up at the same time. During the ATIM window, the nodes exchange control packets to determine whether they need to stay awake for the rest of the beacon interval. The size of the ATIM window has a significant impact on energy saving and throughput achieved by the nodes. This paper proposes an adaptive mechanism to dynamically choose a suitable ATIM window size. We also allow the nodes to stay awake for only a fraction of the beacon interval following the ATIM window. On the other hand, IEEE 802.11 DCF mode requires the nodes to stay awake either for the entire beacon interval following the ATIM window or none at all. Simulation results show that the proposed approach outperforms the IEEE 802.11 power saving mechanism in terms of throughput and the amount of energy consumed.

Previous research in wireless ad hoc networks typically assumes the use of omnidirectional antennas at all nodes. With omnidirectional antennas, while two nodes are communicating using a given channel, MAC protocols such as IEEE 802.11 require all other nodes in the vicinity to stay silent. With directional antennas, two pairs of nodes located in each other's vicinity may potentially communicate simultaneously, depending on the directions of transmission. This can increase spatial reuse of the wireless channel. In addition, the higher gain of directional antennas allows a node to communicate with other nodes located far away, implying that messages could be delivered to the destination in fewer hops. In this paper, we propose a MAC protocol that exploits the characteristics of directional antennas. Our design focuses on using multi-hop RTSs to establish links between distant nodes, and then transmit CTS, DATA and ACK over a single hop. Results show that our directional MAC protocol can perform better than IEEE 802.11, although we find that the performance is dependent on the topology configuration and the flow patterns in the system.

This paper presents a power control MAC protocol based on the IEEE 802.11 standard. Several researchers have proposed a simple modification of IEEE 802.11 to incorporate power control. The main idea of these power control schemes is to use different power levels for RTS-CTS and DATA-ACK. Specifically, maximum transmit power is used for RTS-CTS, and the minimum required transmit power is used for DATA-ACK transmissions in order to save energy. However, we show that this scheme can degrade network throughput and can result in higher energy consumption than using IEEE 802.11 without power control. We propose an improved power control protocol which does not degrade throughput and yields energy saving.

Auto-configuration is a desirable goal in implementing mobile ad hoc networks. Specifically, automated dynamic assignment (without manual intervention) of IP addresses is desirable. In traditional networks, such dynamic address assignment is often performed using the Dynamic Host Configuration Protocol (DHCP). Implementing DHCP, however, requires access to a DHCP server. In mobile ad hoc networks, it is difficult to guarantee access to a DHCP server, since ad hoc networks can become partitioned due to host mobility. Therefore, alternative mechanisms must be employed. One plausible approach is to allow a node to pick a tentative address randomly (or using some locally available information), and then use a "duplicate address detection" (DAD) procedure to detect duplicate addresses. The previously proposed DAD procedures make use of timeouts and do not always perform correctly in presence of partitions. In networks where message delays cannot be bounded, use of timeouts can lead to unreliability. Therefore, we propose an alternative approach (which can be used in conjunction with previously proposed schemes). We refer to the proposed approach as "weak" duplicate address detection. The goal of weak DAD is to prevent a packet from being routed to the "wrong" destination node, even if two nodes in the network happen to have chosen the same IP address. We also propose an enhanced version of the weak DAD scheme, which removes a potential shortcoming of the weak DAD approach.

Ad hoc networks formed without the aid of any established infrastructure are typically multi-hop networks. Location dependent contention and "hidden terminal" problem make priority scheduling in multi-hop networks significantly different from that in wireless LANs. Most of the prior work related to priority scheduling addresses issues in wireless LANs. In this paper, priority scheduling in multi-hop networks is discussed. We propose a scheme using two narrow-band busy tone signals to ensure medium access for high priority source stations. The simulation results demonstrate the effectiveness of the proposed scheme.

Abstract Since a TCP sender cannot distinguish between packet losses arising from transmission errors from those due to congestion, TCP tends to perform poorly on wireless links that are prone to transmission errors. Several techniques have previously been proposed to improve TCP performance over wireless links. Existing schemes typically require an intermediate node (typically, a base station) to be TCP‐aware. For instance, the Snoop scheme requires the base station to interpret TCP headers and take appropriate action to help improve TCP performance. This paper proposes an alternativeTCP‐unawaretechnique that attempts to mimic the behavior of the Snoop protocol. Performance evaluation shows that the proposed Delayed Dupacks scheme performs quite well. Copyright © 2001 John Wiley & Sons, Ltd.

This paper presents several distributed algorithms that cause a token to continually circulate through all the nodes of a mobile ad hoc network. An important application of such algorithms is to ensure total order of message delivery in a group communication service. Some of the proposed algorithms are aware of, and adapt to changes in, the ad hoc network topology. When using a token circulation algorithm, a round is, said to complete when every node has been visited at least once. Criteria for comparing the algorithms include the average time required to complete a round, number of bytes sent per round, and number of nodes visited per round. Comparison between the proposed algorithms is performed using simulation results obtained from a detailed simulation model (with ns-2 simulator).

Wireless local area networks (W-LANs) have become increasingly popular due to the recent availability of affordable devices that are capable of communicating at high data rates. These high rates are possible, in part, through new modulation schemes that are optimized for the channel conditions bringing about a dramatic increase in bandwidth efficiency. Since the choice of which modulation scheme to use depends on the current state of the transmission channel, newer wireless devices often support multiple modulation schemes, and hence multiple datarates, with mechanisms to switch between them Users are given the option to either select an operational datarate manually or to let the device automatically choose the appropriate modulation scheme (data rate) to match the prevailing conditions. Automatic rate selection protocols have been studied for cellular networks but there have been relatively few proposals for W-LANs. In this paper we present a rate adaptive MAC protocol called the Receiver-Based AutoRate (RBAR) protocol. The novelty of RBAR is that its rate adaptation mechanism is in the receiver instead of in the sender. This is in contrast to existing schemes in devices like the WaveLAN II [15]. We show that RBAR is better because it results in a more efficient channel quality estimation which is then reflected in a higher overall throughput Our protocol is based on the RTS/CTS mechanism and consequently it can be incorporated into many medium access control protocols including the widely popular IEEE 802.11 protocol. Simulation results of an implementation of RBAR inside IEEE 802.11 show that RBAR performs consistently well.

This paper considers the problem of providing a geocast service in mobile ad hoc networks and presents a novel geocasting algorithm combining unicasting and flooding. Geocast is useful for sending messages to everyone in a specified geographical region. The proposed protocol is named GeoTORA, because it is derived from the TORA (unicast) routing protocol. Flooding is also incorporated in GeoTORA, but it is limited to nodes within a small region. This integration of TORA and flooding can significantly reduce the overhead of geocast delivery while maintaining reasonably high accuracy.

Using directional antennas can be beneficial for wireless ad hoc networks consisting of a collection of wireless hosts. To best utilize directional antennas, a suitable medium access control (MAC) protocol must be designed. Current MAC protocols, such as the IEEE 802.11 standard, do not benefit when using directional antennas, because these protocols have been designed for omnidirectional antennas. In this paper, we attempt to design new MAC protocols suitable for ad hoc networks based on directional antennas.

Fairness is an important issue when accessing a shared wireless channel. With fair scheduling, it is possible to allocate bandwidth in proportion to weightsof the packet flows sharing the channel. This paper presents a fully distributed algorithm for fair scheduling in a wireless LAN. The algorithm can be implemented without using a centralized coordinator to arbitrate medium access. The proposed protocol is derived from the Distributed Coordination Function in the IEEE 802.11 standard. Simulation results show that the proposed algorithm is able to schedule transmission such that the bandwidth allocated to different flows is proportional to their weights. An attractive feature of the proposed approach is that it can be implemented with simple modifications to the IEEE 802.11 standard.

Our research is focused on the performance of TCP over mobile ad hoc networks.

Mobile ad hoc networks have attracted attention lately as a means of providing continuous network connectivity to mobile computing devices, regardless of physical location. To date, a large amount of research has focused on the routing protocols needed in such an environment. In this paper, we investigate the effects that the routing and link layers have on TCP performance. In particular, we show how the route cache management strategy in an on-demand ad hoc routing protocol can significantly affect TCP performance. We also take a brief look at the impact of link layer retransmissions on TCP throughput in a fixed, wireless multihop network.

A consistent checkpointing algorithm saves a consistent view of a distributed application's state on stable storage. The traditional consistent checkpointing algorithms require different processes to save their state at about the same time. This causes contention for the stable storage, potentially resulting in large overheads. Staggering the checkpoints taken by various processes can reduce checkpoint overhead. This paper presents a simple approach to arbitrarily stagger the checkpoints. Our approach requires that the processes take consistent logical checkpoints, as compared to consistent physical checkpoints enforced by existing algorithms. Experimental results on nCube-2 are presented.

The TCP is a popular transport protocol used in the present-day Internet. When packet losses occur the TCP assumes that the packet losses are due to congestion, and responds by reducing its congestion window. When a TCP connection traverses a wireless link, a significant fraction of packet losses may occur due to transmission errors. The TCP responds to such losses also by reducing the congestion window. This results in unnecessary degradation in the TCP performance. We define a class of functions named loss predictors which may be used by a TCP sender to guess the actual cause of a packet loss (congestion or transmission error) and take appropriate actions. These loss predictors use simple statistics on round-trip times and/or throughput, to determine the cause of a packet loss. We investigate their ability to determine the cause of a packet loss. Unfortunately, our simulation measurements suggest that the three loss predictors do not perform too well.

A mobile ad hoc network consists of wireless hosts that may move often. Movement of hosts results in a change in routes, requiring some mechanism for determining new routes. Several routing protocols have already been proposed for ad hoc networks. This paper suggests an approach to utilize location information (for instance, obtained using the global positioning system) to improve performance of routing protocols for ad hoc networks. By using location information, the proposed Location-Aided Routing (LAR) protocols limit the search for a new route to a smaller "request zone" of the ad hoc network. This results in a significant reduction in the number of routing messages. We present two algorithms to determine the request zone, and also suggest potential optimizations to our algorithms. 1 Introduction Mobile ad hoc networks consist of wireless mobile hosts that communicate with each other, in the absence of a fixed infrastructure. 1 Routes between two hosts in a Mobile Ad hoc NETwork...

For mobile users who move frequently but receive relatively rare calls, a forwarding scheme has been shown to outperform the normal IS-41 location management scheme. But the forwarding scheme is more vulnerable to failure of intermediate Visitor Location Registers (VLRs) than the IS-41 scheme. We propose two simple variations to the forwarding scheme to address the fault tolerance weakness. One is based on the idea of maintaining two paths from the home location server to the last VLR. The second scheme is based on the knowledge of the neighbors of the faulty VLR. We evaluate and compare the performance of these location management schemes.

A comparison-based decoder detects the arrival of a code word by comparing the received checkbits with the checkbits computed using the received data. Implementation issues underlying comparison-based decoders for systematic delay-insensitive (DI) or unordered codes is the subject of this paper. We show that if the decoder is to be implemented using asynchronous logic, i.e., if the gate and wire delays are arbitrary (unbounded but finite), then it is impossible to design a comparison-based decoder for any code that is more efficient than a dual-rail code. In other words, the encoded word must contain at least twice as many bits as the data. In addition, the codes should satisfy two other properties, called the initial condition and the all-zero lower triangle (AZLT) property, for the realization of a delay-insensitive comparison-based decoder. The paper shows that comparison-based decoders for codes that have the requisite level of redundancy and that satisfy the two properties can be implemented using asynchronous logic.

Long-running applications are often subject to failures. Failures can result in significant loss of computation, Therefore, it is necessary to use a failure recovery scheme to minimize performance overhead in the presence of failures. In this paper, we argue that it is often advantageous to use "two-level" recovery schemes. A two-level recovery scheme tolerates the more probable failures with low performance overhead, while the less probable failures may possibly incur a higher overhead. By minimizing overhead for the more frequently occurring failure scenarios, the two-level approach can achieve lower performance overhead (on average) as compared to existing recovery schemes. The paper describes two two-level recovery schemes. Performance analysis using a Markov chain shows that, in practice, a two-level scheme can perform better than its "one-level" counterpart. While the conclusions of this paper are intuitive, the work on design of appropriate recovery schemes is lacking. The objective of this paper is to motivate research into recovery schemes that can provide multiple levels of fault tolerance and achieve better performance than existing recovery schemes. The paper presents an analytical approach for evaluating performance of two-level schemes and shows that such schemes are hard to optimize analytically.

This paper presents a new "cost" analysis model for distributed shared memory (DSM) using a competitive update protocol. The cost metric of interest is the overhead of message passing necessary to implement DSM. This approach is based on segment model proposed previously (Kim et al., 1996, 1997). The input parameter for the cost analysis model is the probability density function of the number of remote updates in a segment. This distribution can quite accurately characterize many applications. The proposed model is validated by comparing analytical results obtained using the model to experimental results. The competitive update protocol for shared memory is defined using a parameter called the "update limit" (or threshold). Using the proposed model, we compute the optimal update limit for the competitive update protocol.

Transmission Control Protocol (TCP) assumes a relatively reliable underlying network where most packet losses are due to congestion. In a wireless network, however, packet losses will occur more often due to unreliable wireless links than due to congestion. When using TCP over wireless links, each packet loss on the wireless link results in congestion control measures being invoked at the source. This causes severe performance degradation. In this paper, we study the effect of: burst errors on wireless links; packet size variation on the wired network; local error recovery by the base station; and explicit feedback by the base station, on the performance of TCP over wireless networks. It is shown that the performance of TCP is sensitive to the packet size, and that significant performance improvements are obtained if a good packet size is used. While local recovery by the base station using link-level retransmissions is found to improve performance, timeouts can still occur at the source, causing redundant packet retransmissions. We propose an explicit feedback mechanism, to prevent these timeouts during local recovery. Results indicate significant performance improvements when explicit feedback from the base station is used. A major advantage of our approaches over existing proposals is that no state maintenance is required at any intermediate host. Experiments are performed using the Network Simulator (NS) from Lawrence Berkeley Labs. The simulator has been extended to incorporate wireless link characteristics.

This paper presents an adaptive migratory scheme for software Distributed Shared Memory (DSM). On a migratory sharing, a message for sending a copy of a page to a remote node, on which a page fault occurs, is directly followed by an invalidation request from the remote node. Our adaptive migratory scheme eliminates an overhead for invalidation by self-invalidation on sending a copy of a page. Each node can independently detect migratory memory access pattern and self-invalidate local copy of a page by using the local information only. Experimental results show that the performance is improved by dynamically selecting the migratory protocol. Keywords: distributed shared memory, release memory consistency, adaptive protocol, migratory protocol, competitive update protocol, performance evaluation, cost analysis model. 1 This work is supported in part by the National Science Foundation under grant MIP-9502563. 1 Introduction This report presents an adaptive migratory DSM algorithm w...

With the increasing popularity of portable wireless computers, mechanisms to efficiently transmit information to such clients are of significant interest.The environmentunderconsideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients.It has been proposed that in such systems the server should broadcast the information periodically.A broadcastschedrale determines what is broadcast by the server and when.This paper makes the simple, yet useful, observation that the problem of broadcast scheduling is closely related to the problem of fair queueing.Based on this observation, we present a log-time algorithm for scheduling broadcast, based on an existing fair queueing algorithm.This algorithm significantly improves the time-complexity over previously proposed broadcast scheduling algorithms.Also, for environments where different users may be listening to different number of broadcast channels, we present an algorithm to coordinate broadcasts over different channels.Simulation results are presented for proposed algorithms.

Performance and reliability trade-offs depend on the recovery scheme used in any fault-tolerant system. Gain in performance, using comparable resources, typically requires sacrifice in reliability, and vice-versa. Roll-forward schemes for duplex systems achieve better performance than rollback schemes, without a significant increase in hardware resource requirements. This paper compares two roll-forward schemes with two roll-back schemes. It is shown that the roll-forward schemes improve performance with only a small loss in reliability as compared to rollback schemes.

Checkpointing reduces loss of computation in the presence of failures. Two metrics characterize a checkpointing scheme: checkpoint overhead and checkpoint latency. The paper shows that a large increase in latency is acceptable if it is accompanied by a relatively small reduction in overhead. Also, for equidistant checkpoints, optimal checkpoint interval is shown to be typically independent of checkpoint latency.

This paper defines t-proximity-detecting (t-PD) codes that can detect when a received word is within distance t from the transmitted codeword, when using a four-phase asynchronous communication protocol (or other similar protocols). Proximity-detecting codes can be used to improve the performance of asynchronous buses. A nontrivial t-proximity-detecting code must be unordered. However, not all unordered codes are t-proximity-detecting. This paper characterizes t-PD codes, and presents some properties of such codes. Designs of systematic 1-PD codes, and their generalization to t-PD codes are presented, along with a bound on the number of checkbits.

The focus of this paper is on software implementations of Dwtributed Shared Memory (DSM).In rweent yeara, many ptotoeola for implementing DSM have been proposed.Performance of these protocols depends on the memory access behavior of the applications.Some reseamhera have proposed DSMS that provide a family of consistency protocols or application-specific protocols, and the programmer is allowed to choose any one of them for each shared memory object (or page) or eaeh stage of an application, While such implementations have a potential for achieving optimal performance, they impose undue burden on the programmer.Therefore, some tiptive schemes that automatically choose the appropriate protocol have been proposed.This paper presenta a simple approach for implementing adaptive DSMS.The appmaeh is illustrated with the example of an adaptive DSM baaed on the invalidate and competitive update plVtoeols.The objective of the adaptive scheme is to minimize a predefine "cost" function.The cost functions considered here are number of messages and amount of data transfer.The proposed scheme allows each node to independently choose (at run-time) a diffenmt protocol for each page.The paper presents experimental evaluation of the adaptive DSM.Results show that the performance is improved by dynamically selecting the appropriate protocol.

This paper presents a technique to provide seamless communication in mobile wireless networks. The motivation behind this study is to find a cost effective solution for minimizing the impact of active hand-offs (hand-offs during an active connection) on connection throughput. Existing solutions either provide total guarantee for seamless communication, incurring heavy network bandwidth usage (multicast based approach), or do not provide any guarantee for seamless communication (unicast based approach). Some other solutions are tuned to give good performance for specific protocols (e.g., fast-retransmit approach). This paper proposes a novel staggered multicast approach which provides a probablistic guarantee for seamless communication independent of the communication protocol used. We present experimental results of performance improvements achieved by our scheme, for data transfer using TCP over a wireless network in the presence of active handoffs. The conclusions however, are generic in that they apply to protocols other than TCP.

A large number of choices exist when designing a reliable memory system. The choices range from simple replication to complex error control codes (ECC). An intermediate solution is to use combination of replication and simple ECC. Such a system consists of multiple memory modules, data stored in each module being encoded using an ECC. This paper compares reliability of memory systems formed using simple triplication (without ECC) with memory systems formed by duplicating memory modules that use ECC. It is shown that reliability achieved by duplication of memory modules using codes capable of only error detection or only single error correction (SEC), is always worse than simple triplication. However, it is also shown that duplication of memory modules, with codes capable of single error correction and double error detection (SEC-DED), can achieve better reliability than simple triplication when bit error probability is small.

This paper presents a token-based K-mutual exclusion algorithm. The algorithm uses K tokens and a dynamic forest structure for each token. This structure is used to forward token requests. The algorithm is expected to minimize the number of messages and also the delay in entering the critical section, at low as well as high loads. The paper presents simulation results for the proposed algorithm and compares them with three other algorithms. Unlike previous work, our simulation model assumes that a finite (non-zero) overhead is encountered when a message is sent or received. The simulation results show that, as compared to other algorithms, the proposed algorithm achieves lower delay in entering critical section as well as lower number of messages, without a significant increase in the size of the messages.

Most distributed and multiprocessor recovery schemes proposed in the literature are designed to tolerate arbitrary number of failures. In this paper, we demonstrate that, it is often advantageous to use "two-level" recovery schemes. A two-level recovery scheme tolerates the more probable failures with low performance overhead, while the less probable failures may be tolerated with a higher overhead. By minimizing the overhead for the more frequently occurring failure scenarios, our approach is expected to achieve lower performance overhead (on average) as compared to existing recovery schemes.To demonstrate the advantages of two-level recovery, we evaluate the performance of a recovery scheme that takes two different types of checkpoints, namely, 1-checkpoints and N-checkpoints. A single failure can be tolerated by rolling the system back to a 1-checkpoint, while multiple failure recovery is possible by rolling back to an N-checkpoint. For such a system, we demonstrate that to minimize the average overhead, it is often necessary to take both 1-checkpoints and N-checkpoints.While the conclusions of this paper are intuitive, the work on design of appropriate recovery schemes is lacking. The objective of this paper is to motivate research into recovery schemes that can provide multiple levels of fault tolerance.

This paper defines a new class of unidirectional errors, named t/1-unidirectional errors, which affect at most t bits confined to at most t bytes of the code word. Codes that are capable of detecting, locating and correcting t/1-unidirectional errors are presented. Lower bounds on the number of checkbits required for t/1-unidirectional error detection and location are also presented.>

In most research on checkpointing and recovery, it has been assumed that the processor halts immediately in response to any internal failure (fail-stop model). This paper presents a recovery scheme (independent checkpointing and message logging) for a multicomputer system consisting of processors having a non-zero error detection latency. Our scheme tolerates bounded error detection latencies, thus, achieving a higher fault coverage. The simulation results show that for typical detection latency values, the recovery overhead is almost independent of the detection latency.

We propose a novel architecture for a fault-tolerant multiprocessor environment. It is assumed that the multiprocessor organization consists of a pool of active processing modules and either a small number of spare modules or active modules with some spare processing capacity. A fault-tolerance scheme is developed for duplex systems using checkpoints. Our scheme, unlike traditional checkpointing schemes, requires no rollbacks for recovering from single faults. The objective is to achieve performance of a triple modular redundant system using duplex system redundancy.>

A new approach called safe system level diagnosis is proposed. With this approach, in the event of a small number of faults, all the faulty nodes can be identified; also, in the event of a large number of faults, the fault condition can be detected. Systems which achieve a specified level of safe diagnosis are characterized and a diagnosis algorithm for such systems is presented. Also, an application of safe diagnosis to adaptive diagnosis on arbitrary t-diagnosable graphs is discussed.>

The authors consider a system consisting of a sender that wants to send a value to certain receivers. Byzantine agreement protocols have previously been proposed to achieve this in the presence of arbitrary failures. The imposed requirement typically is that the fault-free receivers must all agree on the same value. An agreement protocol is proposed that achieves Lamport's Byzantine agreement (L. Lamport et al., 1982) up to a certain number of faults and a degraded form of agreement with a higher number of faults. The degraded form of agreement allows the fault-free receivers to agree on at most two different values, one of which is necessarily the default value. The proposed approach is named degradable agreement. An algorithm for degradable agreement is presented along with bounds on the number of nodes and network connectivity necessary to achieve degradable agreement.>

Several fundamental results related to reliability and safety are analyzed. Modular redundant systems consisting of multiple identical modules and an arbiter are considered. It is shown that for a given level of redundancy, a large number of implementation alternatives exist with varying degree of reliability and safety. Strategies are formulated that achieve a maximal combination of reliability and safety. The effect of increasing the number of modules on system reliability and safety is analyzed. It is shown that when one considers safety in addition to reliability, it does not necessarily help to simply add modules to the system. Specifically, increasing the number of modules by just one does not always improve both reliability and safety. To improve reliability and safety simultaneously, at least two additional modules are required when the outputs of the individual modules do not have any redundant information (e.g., coding for error detection). However, it is shown that if the modules themselves have built-in error detection capability, addition of just one module may be sufficient to improve both reliability and safety.>

Error-control codes for byte-oriented systems are presented. The proposed codes are intended for systems wherein the erroneous bits tend to be confined to a small number of bytes. Mathematical techniques are developed for the construction of codes that can detect and correct such errors. Among the various codes presented, the codes for detection and correction of errors confined to a single byte are of particular interest. A decoding algorithm for these codes is also presented.>