Private WANs are increasingly important to the operation of enterprises, telecoms, and cloud providers. For example, B4, Google's private software-defined WAN, is larger and growing faster than our connectivity to the public Internet. In this paper, we present the five-year evolution of B4. We describe the techniques we employed to incrementally move from offering best-effort content-copy services to carrier-grade availability, while concurrently scaling B4 to accommodate 100x more traffic. Our key challenge is balancing the tension introduced by hierarchy required for scalability, the partitioning required for availability, and the capacity asymmetry inherent to the construction and operation of any large-scale network. We discuss our approach to managing this tension: i) we design a custom hierarchical network topology for both horizontal and vertical software scaling, ii) we manage inherent capacity asymmetry in hierarchical topologies using a novel traffic engineering algorithm without packet encapsulation, and iii) we re-architect switch forwarding rules via two-stage matching/hashing to deal with asymmetric network failures at scale.

Wireless devices provide flexible solutions for industrial instrumentation applications, such as quality control of manufacture of jet engines. In this context, the dominant issues are providing high-throughput, and reliability in the sense of not losing samples due to buffer overflow at the wireless devices. A random medium access control (MAC) scheme, such as the IEEE 802.15.4, is unlikely to perform well along those metrics. CSMA/CA, the foundation of IEEE 802.15.4, is inefficient at the high-throughput regime. The polling mode of IEEE 802.15.4, on the other hand, ignores the buffer constraints, thereby increasing the risk of buffer overflow. In this paper, we propose SAMPLER, a scheduled MAC protocol that is optimal, in the sense of minimizing sample losses while maximizing throughput, in the typical scenario where a sophisticated access point forms a star topology with the wireless sensors. We describe SAMPLER, its properties and demonstrate its superior performance compared to random-access MAC through simulations.

Today a growing number of applications that operate in dynamic environments use distributed systems. Often, one or more constrained resources need to be allocated across such systems. In addition, for a number of important applications, the resources to be allocated are discrete quantities and the demand profile is intrinsically location and time dependent (thus pre-computating the resource allocation problem off-line is inadequate). We model such systems using graphs - vertices representing the sites and edges capturing locality - where each vertex is associated with the a pair of (integer) numbers representing the current and the required level of a resource. We seek on-the-fly reallocation of resources that satisfy the demand at each node, if it is feasible to do so, while minimizing a given metric of interest, such as the total distance traveled, maximum disruption time, etc. Due to integrality constraints, one expects such a problem to be NP-hard. However, we show that the matrix representing constraints of the problem satisfies the Total Unimodularity property and hence the problem is solvable in polynomial time. We propose a distributed algorithm that employs only local communications. We characterize the proposed algorithm and by numerical performance evaluation, show that it significantly outperforms known heuristic algorithms.

Ethernet's plug-&-play feature is built on its use of flat (location independent) addresses and use of broadcasts to resolve unknown MAC addresses. While plug-&-play is one of Ethernet's most attractive features, it also affects its scalability. As the number of active MAC addresses in the network grows beyond the capacity of forwarding caches in bridges, the odds of "cache-misses," each triggering a broadcast, grow as well. The resulting increase in broadcast bandwidth consumption affects scalability. To address this problem, we propose a simple address resolution scheme based on an adaptation of distributed hash tables where a single query suffices in the steady state. The new scheme is implemented on advanced bridges maintaining backward compatibility with legacy bridges and eliminating reliance on broadcasts for address discovery. Comparisons with a legacy, broadcast-based scheme are carried out along several metrics that demonstrate the new scheme's robustness and ability to improve scalability.

The paper develops a systematic framework for designing a stochastic location detection system with associated performance guarantees using a wireless sensor network. To detect the location of a mobile sensor, the system relies on RF-characteristics of the signal transmitted by the mobile sensor, as it is received by stationary sensors (clusterheads). Location detection is posed as a hypothesis testing problem over a discretized space. Large deviations results enable the characterization of the probability of error leading to a placement problem that maximizes an information-theoretic distance (Chernoff distance) among all pairs of probability distributions of observations conditional on the sensor locations. The placement problem is shown to be NP-hard and is formulated as a linear integer programming problem; yet, large instances can be solved efficiently by leveraging special-purpose algorithms from the theory of discrete facility location. The resultant optimal placement is shown to provide asymptotic guarantees on the probability of error in location detection under quite general conditions by minimizing an upper bound of the error-exponent. Numerical results show that the proposed framework is computationally feasible and the resultant clusterhead placement performs near-optimal even with a small number of observation samples in a simulation environment.

We propose a systematic framework for designing a stochastic indoor location detection system with associated performance guarantees using a hierarchical wireless sensor network. To detect the location of a mobile sensor, we rely on RF-characteristics of the signal transmitted by the mobile sensor, as it is received by the clusterheads. The problem of location detection is posed as a hypothesis testing problem over a discretized space. We leverage large deviations and decision theory results to characterize the probability of error and use this characterization to optimally place clusterheads. The placement problem is NP-hard and we formulate it as a linear integer programming problem. We leverage special-purpose algorithms from the theory of discrete facility location to solve large problem instances efficiently. For the resultant placement we provide asymptotic guarantees on the probability of error in location detection under quite general conditions. Numerical and simulation results show that our proposed framework is computationally feasible and the resultant clusterhead placement performs near-optimum even with a small number of observation samples.

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

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

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

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