Accurate tree segmentation is a key step in extracting individual tree metrics from forest laser scans, and is essential to understanding ecosystem functions in carbon cycling and beyond. Over the past decade, tree segmentation algorithms have advanced rapidly due to developments in AI. However, existing public 3D forest datasets are not large enough to build robust tree segmentation systems. Motivated by the success of synthetic data in other domains such as self-driving, we investigate whether similar approaches can help with tree segmentation. In place of expensive field data collection and annotation, we use synthetic data during pretraining, and then require only minimal, real forest plot annotation for fine-tuning. We have developed Cambridge Arboreal Modelling Panoptic 3D (CAMP3D), a new synthetic data generation pipeline to do this for forest vision tasks, integrating advances in game engines with physics-based LiDAR simulation. Using CAMP3D, we have produced a comprehensive, diverse, annotated 3D forest dataset on an unprecedented scale. Extensive experiments with a state-of-the-art tree segmentation algorithm and a popular real dataset show that our synthetic data can substantially reduce the need for labelled real data. After fine-tuning on just a single, real, forest plot of less than 0.1 hectare, the pretrained model achieves segmentations that are competitive with a model trained on the full scale real data. We have also identified critical factors for successful use of synthetic data: physics, diversity, and scale, paving the way for more robust 3D forest vision systems in the future. Our CAMP3D pipeline and the resulting dataset are available at https://github.com/yihshe/CAMP3D.git.

Intelligent irrigation based on measurements of soil moisture levels in every pot in a greenhouse can not only improve plant productivity and quality but also save water. However, existing soil moisture sensors are too expensive to deploy in every pot. We therefore introduce GreenTag, a low-cost RFID-based soil moisture sensing system whose accuracy is comparable to that of an expensive soil moisture sensor. Our key idea is to attach two RFID tags to a plant’s container so that changes in soil moisture content are reflected in their Differential Minimum Response Threshold (DMRT) metric at the reader. We show that a low-pass filtered DMRT metric is robust to changes both in the RF environment (e.g., from human movement) and in pot locations. In addition, we propose a fast DMRT acquisition algorithm and a time-efficient tag query protocol, which can reduce the sensing latency by 90%. In a realistic setting, GreenTag achieves a 90-percentile moisture estimation errors of 5%, which is comparable to the 4% errors using expensive soil moisture sensors. Moreover, this accuracy is maintained despite changes in the RF environment and container locations. We also show the effectiveness of GreenTag in a real greenhouse.

Carbon credits purchased in the voluntary carbon market allow unavoidable emissions, such as international flights for essential travel, to be offset by an equivalent climate benefit, such as avoiding emissions from tropical deforestation. However, many concerns regarding the credibility of these offsetting claims have been raised. Moreover, the credit market is manual, therefore inefficient and unscalable, and non-fungible, therefore illiquid. To address these issues, we propose an efficient digital methodology that combines remote sensing data, modern econometric techniques, and on-chain certification and trading to create a new digital carbon asset (the PACT stablecoin) against which carbon offsetting claims can be transparently verified. PACT stablecoins are produced as outputs from a reproducible computational pipeline for estimating the climate benefits of carbon offset projects that not only quantifies the CO2 emissions involved, but also allows for similar credits to be pooled based on their co-benefits such as biodiversity and jurisdictional attributes, increasing liquidity through fungibility within pools. We implement and evaluate the PACT carbon stablecoin on the Tezos blockchain, which is designed to facilitate low-cost transactions while minimizing environmental impact. Our implementation includes a contract for a registry for tracking issuance, ownership, and retirement of credits, and a custodian contract to bridge on-chain and off-chain transactions. Our work brings scale and trust to the voluntary carbon market by providing a transparent, scalable, and efficient framework for high-integrity carbon credit transactions.

Radio-Frequency IDentification (RFID) technology permits a reader to wirelessly query a tag for its embedded globally unique identifier. Passive RFID tags, which are small, low-cost (a few cents each), and batteryless, can be reliably read only when they are within a few meters of the reader since the tag must power up itself by harvesting energy from the reader. Past work attempts to increase the RFID range by providing them with more energy, such as by synchronizing multiple custom design RFID readers and performing beamforming. However, we demonstrate that a passive tag's range is limited not only by the need for the tag to harvest energy but also by the need for the tag to decode the reader's transmission, and vice versa. Thus, instead of modifying readers, we ask if a tag's manufacturer can increase passive RFIDs' range by lowering the data rate. Our results show that the working range can be increased by a factor of about 10 by simply using a low data rate. Our real-world experiments using customized tag prototypes have a range of ~40 m, with an SNR exceeding 12 dB.

We study the problem of optimally and simultaneously sizing solar photovoltaic (PV) and storage capacity in order to partly or completely offset grid usage. While prior work offers some insights, researchers typically consider only a single sizing approach. In contrast, we use a firm theoretical foundation to compare and contrast sizing approaches based on robust simulation, robust optimization, and stochastic network calculus. We evaluate the robustness and computational complexity of these approaches in a realistic setting to provide practical, robust advice on system sizing.

Tree trunk diameter, currently measured during manual forest inventories, is a key input to tree carbon storage calculations. We designan app running on a smartphone equipped with a time-of-flight sensor that allows efficient, low-cost, and accurate measurement of trunk diameter, even in the face of natural leaf and branch occlusion. The algorithm runs in near real-time on the phone, allowing user interaction to improve the quality of the results. We evaluate the app in realistic settings and find that in a corpus of 55 sample tree images, it estimates trunk diameter with mean error of 7.8%.

Intelligent irrigation based on measurements of soil moisture levels in every pot in a greenhouse can not only improve plant productivity and quality but also save water. However, existing soil moisture sensors are too expensive to deploy in every pot. We therefore introduce GreenTag, a low-cost RFID-based soil moisture sensing system whose accuracy is comparable to that of an expensive soil moisture sensor. Our key idea is to attach two RFID tags to a plant's container so that changes in soil moisture content are reflected in their Differential Minimum Response Threshold (DMRT) metric at the reader. We show that a low-pass filtered DMRT metric is robust to changes both in the RF environment (e.g., from human movement) and in pot locations. In a realistic setting, GreenTag achieves a 90-percentile moisture estimation errors of 5%, which is comparable to the 4% errors using expensive soil moisture sensors. Moreover, this accuracy is maintained despite changes in the RF environment and container locations. We also show the effectiveness of GreenTag in a real greenhouse.

Passive Radio Frequency IDentification (RFID) tags are commonly used to provide Radio Frequency (RF) accessible unique identifiers for physical objects due to their low-cost, lack of battery, and small size. Besides this basic function, many novel RFID-based sensing applications have been proposed in the last decade, including localization, gesture sensing, and touch sensing, among others. Nevertheless, none of these systems are in widespread use today. We hypothesize that this is because the accuracy of these systems does not meet application requirements when there are even minor changes in the RF environment or in tag geometry, i.e., changes in a tag's orientation or flexing. This paper uses both theoretical analysis and real-world experiments to test this hypothesis. Our theoretical analysis shows that even a small phase or RSS noise level can result in significant estimation errors. Our extensive real-world experiments find that both the absolute and differential values of phase and RSS readings of an RFID tag's signal can vary as much as by π radians and 10 dB, respectively, due to small changes in the tag's orientation or flexing. Because of these large variations, RFID-based application systems relying on the signal phase or RSS cannot meet application requirements, confirming our hypothesis. In addition to this strong negative result, we also present some insights into designing robust RFID systems that are suitable for use in the real world.

Passive radio frequency identification (RFID) tags are ubiquitous today due to their low cost (a few cents), relatively long communication range ($\sim$7-11~m), ease of deployment, lack of battery, and small form factor. Hence, they are an attractive foundation for environmental sensing. Although RFID-based sensors have been studied in the research literature and are also available commercially, manufacturing them has been a technically-challenging task that is typically undertaken only by experienced researchers. In this paper, we show how even hobbyists can transform commodity RFID tags into sensors by physically altering (`hacking') them using COTS sensors, a pair of scissors, and clear adhesive tape. Importantly, this requires no change to commercial RFID readers. We also propose a new legacy-compatible tag reading protocol called Differential Minimum Response Threshold (DMRT) that is robust to the changes in an RF environment. To validate our vision, we develop RFID-based sensors for illuminance, temperature, touch, and gestures. We believe that our approach has the potential to open up the field of batteryless backscatter-based RFID sensing to the research community, making it an exciting area for future work.

In shared bike-and-ride transit systems, commuters use shared bicycles for last-mile transport between transit stations and home, and between transit stations and work locations. This requires pools of bicycles to be located near each transit stop where commuters can drop off and pick up shared bikes. We study the optimal sizing of such bicycle pools. While various problems related to vehicle pool sizing have been studied before, to the best of our knowledge this is the first paper that considers a multimodal transportation system with a regularly scheduled public transportation backbone and shared bicycles for the first and last mile. We present two solutions that guarantee bicycle availability with high probability, and we empirically verify their effectiveness using Monte Carlo simulations. Compared to a baseline solution, our techniques reduce the size of the bikeshare pool at the public transit station from 39% to 75% in the tested scenarios.

Achieving consensus among a set of distributed entities (or participants) is a fundamental problem at the heart of many distributed systems. A critical problem with most consensus protocols is that they do not scale well. As the number of participants trying to achieve consensus increases, increasing network traffic can quickly overwhelm the network from topology-oblivious broadcasts, or a central coordinator for centralized consensus protocols. Thus, either achieving strong consensus is restricted to a handful of participants, or developers must resort to weaker models of consensus.

We present insights on data management resulting from a field deployment of approximately 30 sensor-equipped electric bicycles (e-bikes) at the University of Waterloo. The trial has been in operation for the last two-and-a-half years, and we have collected and analyzed more than 150 gigabytes of data. We discuss best practices for the entire data management process, spanning data collection, extract-transform-load, data cleaning, and choosing a suitable data management ecosystem. We also comment on how our experiences will inform the design of a future large-scale field trial involving several thousand fully-instrumented e-bikes.

The wide range of performance characteristics of storage technologies motivates the use of a hybrid energy storage system (HESS) that combines the best features of multiple technologies. However, HESS design is complex, in that it involves the choice of storage technologies, the sizing of each storage element, and deciding when to charge and discharge each underlying storage element (operating strategy). We formulate the problem of jointly optimizing the sizing and the operating strategy of an HESS that can be used for a large class of applications and storage technologies. Instead of a single set of storage element sizes, our approach determines the Pareto-optimal frontier of the sizes of the storage elements along with the corresponding optimal operating strategy. Thus, as long as the performance objective of a storage application (such as an off-grid microgrid) can be expressed as a linear combination of the underlying storage sizes, the optimal vector of storage sizes falls somewhere on this frontier. We present two case studies to illustrate our approach, demonstrating that a single storage technology is sometimes inadequate to meet application requirements, unlike an HESS designed using our approach. We also find simple, near-optimal, and practical operating strategies for these case studies, which allows us to gain several new engineering insights.

Typical VM consolidation approaches re-pack VMs into fewer physical machines, resulting in energy and cost savings [13, 19, 23, 40]. Recent work has explored a just-in time approach to VM consolidation by transitioning VMsto an inactive state when idle and activating them on the arrival of client requests[17, 21]. This leads to increased VM density at the cost of an increase in client request latency (called miss penalty). The VM density so obtained, although greater, is still limited by the number of VMs that can be hosted in the one inactive state. If idle VMs were hosted in multiple inactive states, VM density can be increased further while ensuring small miss penalties. However, VMs in different inactive states have different capacities, activation times, and resource requirements.

Most datacenter network (DCN) designs focus on maximizing bisection bandwidth rather than minimizing server-to-server latency. We explore architectural approaches to building low-latency DCNs and introduce Quartz, a design element consisting of a full mesh of switches. Quartz can be used to replace portions of either a hierarchical network or a random network. Our analysis shows that replacing high port-count core switches with Quartz can significantly reduce switching delays, and replacing groups of top-of-rack and aggregation switches with Quartz can significantly reduce congestion-related delays from cross-traffic. We overcome the complexity of wiring a complete mesh using low-cost optical multiplexers that enable us to efficiently implement a logical mesh as a physical ring. We evaluate our performance using both simulations and a small working prototype. Our evaluation results confirm our analysis, and demonstrate that it is possible to build low-latency DCNs using inexpensive commodity elements without significant concessions to cost, scalability, or wiring complexity.

We refer to a vehicle pool as a number of vehicles at a single location used for the same purpose. We focus on the problem of sizing vehicle pools for a finite set of subscribers who can use the pool. Our goal is to minimize the number of vehicles in the pool while still meeting nearly all subscriber requests. Formally, we propose three analytical techniques to size a vehicle pool for a finite population of subscribers, according to the pools' busy period demand to guarantee all requests are served with probability 1 - ε, i.e., a quality-of-service (QOS) guarantee. Moreover, we propose an additional heuristic sizing method, which requires no prior data about pool demand. Although this method does not provide probabilistic bounds on QOS, we show in practice that it still achieves a high QOS. We evaluate our sizing methodologies using seven years of data from a local car share, using three performance metrics: availability (percentage of requests served), utilization (the percentage of time that vehicles in the pool are used) and member-to-vehicle ratio (the size of the pool relative to the size of its user population). We show that our methods perform well with respect to these metrics.

The high variability of solar power due to intrinsic diurnal variability, as well as additional stochastic variations due to cloud cover, have made it difficult for solar farms to participate in electricity markets that require pre-committed constant power generation. We study the use of battery storage to 'firm' solar power, that is, to remove variability so that such a pre-commitment can be made. Due to the high cost of storage, it is necessary to size the battery parsimoniously, choosing the minimum size to meet a certain reliability guarantee. Inspired by recent work that identifies an isomorphism between batteries and network buffers, we introduce a new model for solar power generation that models it as a stochastic traffic source. This permits us to use techniques from the stochastic network calculus to both size storage and to maximize the revenue that a solar farm owner can make from the day-ahead power market. Using a 10-year of recorded solar irradiance, we show that our approach attains 93% of the maximum revenue in a summer day that would have been achieved in daily market had the entire solar irradiance trace been known ahead of time.

Despite the many proposals for data center network (DCN) architectures, designing a DCN remains challenging. DCN design is especially difficult when expanding an existing network, because traditional DCN design places strict constraints on the topology (e.g., a fat-tree). Recent advances in routing protocols allow data center servers to fully utilize arbitrary networks, so there is no need to require restricted, regular topologies in the data center. Therefore, we propose a data center network design framework, that we call REWIRE, to design networks using an optimization algorithm. Our algorithm finds a network with maximal bisection bandwidth and minimal end-to-end latency while meeting user-defined constraints and accurately modeling the predicted cost of the network. We evaluate REWIRE on a wide range of inputs and find that it significantly outperforms previous solutions-its network designs have up to 100-500% more bisection bandwidth and less end-to-end network latency than equivalent-cost DCNs built with best practices.

Large-scale Internet applications, such as content distribution networks, are deployed across multiple datacenters and consume massive amounts of electricity. To provide uniformly low access latencies, these datacenters are geographically distributed and the deployment size at each location reflects the regional demand for the application. Consequently, an application's environmental impact can vary significantly depending on the geographical distribution of end-users, as electricity cost and carbon footprint per watt is location specific. In this paper, we describe FORTE: Flow Optimization based framework for request-Routing and Traffic Engineering. FORTE dynamically controls the fraction of user traffic directed to each datacenter in response to changes in both request workload and carbon footprint. It allows an operator to navigate the three-way tradeoff between access latency, carbon footprint, and electricity costs and to determine an optimal datacenter upgrade plan in response to increases in traffic load. We use FORTE to show that carbon taxes or credits are impractical in incentivizing carbon output reduction by providers of large-scale Internet applications. However, they can reduce carbon emissions by 10% without increasing the mean latency nor the electricity bill.

We conduct a large-scale user study to measure the energy consumption characteristics of 20,100 BlackBerry smartphone users. Our dataset is several orders of magnitude larger than any previous work. We use this dataset to build the Energy Emulation Toolkit (EET) that allows developers to evaluate the energy consumption requirements of their applications against real users' energy traces. The EET computes the successful execution rate of energy-intensive applications across all users, specific devices, and specific smartphone user types. We also consider active adaptation to energy constraints. By classifying smartphone users based on their charging characteristics we demonstrate that energy level can be predicted within 72% accuracy a full day in advance, and through an Energy Management Oracle energy intensive applications can adapt their execution to achieve a near optimal successful execution rate.

We consider the problem of providing mobility support for Voice-over-IP (VoIP) traffic in small-scale enterprises. There is considerable interest in providing on-the-go support for VoIP through the use of WiFi-enabled smart phones. However, existing solutions either do not support client mobility or require client modifications, making them difficult to deploy in practice.

Fundamental limitations of traditional data center network architectures have led to the development of architectures that provide enormous bisection bandwidth for up to hundreds of thousands of servers. Because these architectures rely on homogeneous switches, implementing one in a legacy data center usually requires replacing most existing switches. Such forklift upgrades are typically prohibitively expensive; instead, a data center manager should be able to selectively add switches to boost bisection bandwidth. Doing so adds heterogeneity to the network's switches and heterogeneous high-performance interconnection topologies are not well understood. Therefore, we develop the theory of heterogeneous Clos networks. We show that our construction needs only as much link capacity as the classic Clos network to route the same traffic matrices and this bound is the optimal. Placing additional equipment in a highly constrained data center is challenging in practice, however. We propose LEGUP to design the topology and physical arrangement of such network upgrades or expansions. Compared to current solutions, we show that LEGUP finds network upgrades with more bisection bandwidth for half the cost. And when expanding a data center iteratively, LEGUP's network has 265% more bisection bandwidth than an iteratively upgraded fat-tree.

Enterprise WLANs have made a dramatic shift towards centralized architectures in the recent past. The reasons for such a change have been ease of management and better design of various control and security functions. The data path of WLANs, however, continues to use the distributed, random-access model, as defined by the popular DCF mechanism of the 802.11 standard. While theoretical results indicate that a centrally scheduled data path can achieve higher efficiency than its distributed counterpart, the likely complexity of such a solution has inhibited practical consideration. In this paper, we take a fresh, implementation and deployment oriented, view in understanding data path choices in enterprise WLANs. We perform extensive measurements to characterize the impact of various design choices, like scheduling granularity on the performance of a centralized scheduler, and identify regions where such a centralized scheduler can provide the best gains.Our detailed evaluation with scheduling prototypes deployed on two different wireless testbeds indicates that DCF is quite robust in many scenarios, but centralization can play a unique role in 1) mitigating hidden terminals - scenarios which may occur infrequently, but become pain points when they do and 2) exploiting exposed terminals - scenarios which occur more frequently, and limit the potential of successful concurrent transmissions. Motivated by these results, we design and implement CENTAUR - a hybrid data path for enterprise WLANs, that combines the simplicity and ease of DCF with a limited amount of centralized scheduling from a unique vantage point. Our mechanisms do not require client cooperation and can support legacy 802.11 clients.

Increased AP density in enterprise WLANs leads to increasing RF interference and decreasing performance. An important step towards mitigating this problem is to construct precise RF maps in the form of a conflict graph. Prior work on conflict graph construction, mostly using bandwidth tests [17], suffers from two problems: a) It is limited to static settings and cannot support mobility, and b) It incurs significant measurement overhead and must be performed offline (e.g. overnight). An alternative to bandwidth tests is "micro-probing" [4] that operates on millisecond-level time scales. Micro-probing rapidly constructs the conflict graph even while the network is in use (i.e. online). While interesting in principle, micro-probing has only been evaluated in simulation. In this work, we empirically study micro-probing on a 40-node wireless testbed. In doing so, we not only show that micro-probing is in fact practically realizable, but also present key insights that drive the design choices for our implementation. We benchmark micro-probing against bandwidth tests and find that micro-probing is just as accurate but with up to a 400 times reduction in overhead. Finally, we argue that a successful implementation of micro-probing opens up the space for further innovations in real-time WLAN adaptation and optimization.

Abstract We present GAB, a search algorithm for hybrid peer‐to‐peer networks, that is, networks that search using both flooding and a distributed hash table (DHT). GAB uses a gossip‐style algorithm to collect global statistics about document popularity to allow each peer to make intelligent decisions about which search style to use for a given query. Moreover, GAB automatically adapts to changes in the operating environment. Synthetic and trace‐driven simulations show that compared to a simple hybrid approach that always floods first, trying a DHT if too few results are found, GAB reduces the response time by 25–50% and the average query bandwidth cost by 45%, with no loss in recall. GAB scales well, with only a 7% degradation in performance despite a tripling in system size. Copyright © 2007 John Wiley & Sons, Ltd.

Data-ferrying disconnection-tolerant networks allow remote rural areas to access the Internet at very low cost, making them viable alternatives to more expensive access technologies such as DSL, CDMA, and dial-up. In such a network, an Internet-based proxy gathers data from the Internet and sends it to a set of edge nodes called "gateways", from which data ferries, such as buses and cars, opportunistically pick up the data using short-range WiFi as they drive past, and deliver it wirelessly to kiosks in remote villages. In this context, we pose the following question: assuming knowledge of ferry schedules, when and to which gateway should the proxy send each data bundle so that the overall delay is minimized and the bandwidth is shared fairly among competing kiosks? We show that a well-known schedule-aware routing scheme proposed in the literature, i.e., EDLQ [11] is far from optimal. Moreover, EDLQ does not provide means to enforce bandwidth allocations. To remedy these problems, we employ a token bucket mechanism to decouple fairness and delay minimization concerns. We also describe a utility-maximizing scheduler based on the classical minimum-cost network flow problem, that finds optimal schedules. Through simulations, we show that our scheme performs at least as well as EDLQ in scenarios that favour EDLQ, yet achieves up to 40% reduction in delay in those that do not.

Rural Internet kiosks in developing countries can cost-effectively provide communication and e-governance services to the poorest sections of society. Unfortunately, a variety of technical and non-technical issues have caused most kiosk deployments to be unsustainable [1]. KioskNet addresses the key technical problems underlying kiosk failure by using robust ‘mechanical backhaul’ for connectivity [2], and by using low-cost and reliable kiosk controllers to support services delivered from one or more recycled PCs. KioskNet also addresses related issues such as security, user management, and log collection. In this paper, we describe the KioskNet system and outline its hardware, software, and security architectures. We describe a pilot deployment, and how we used lessons from this deployment to re-design our initial prototype.

Wireless LANs are commonplace installations in enterprise environments. Their ease of use and deployment, however, are accompanied by a difficulty in their management and security. Proposed solutions to these problems are based on centralization; in the control plane through centralized authentication and allocation of channels and power levels, and in the data plane through time slotted medium access using centralized scheduling for interference mitigation. While centralization of some control plane tasks has been shown to be feasible, centralization on the data plane is significantly harder to realize. This is because it needs to take into account the inherent variability of the wireless medium while offering bounds on delay and jitter on the control paths. In this work, we present a study of the various problems that arise in centralization of the data plane in an enterprise WLAN. We believe that a pragmatic solution for data plane centralization is the key approachto provisioning an enterprise WLAN consisting of a dense deployment of APs.

We consider the problem of providing vehicular Internet access using roadside 802.11 access points. We build on previous work in this area [18, 8, 5, 11] with an extensive experimental analysis of protocol operation at a level of detail not previously explored. We report on data gathered with four capture devices from nearly 50 experimental runs conducted with vehicles on a rural highway. Our three primary contributions are: (1) We experimentally demonstrate that, on average, current protocols only achieve 50% of the overall throughput possible in this scenario. In particular, even with a streamlined connection setup procedure that does not use DHCP, high losses early in a vehicular connection are responsible for the loss of nearly 25% of overall throughput, 15% of the time. (2) We quantify the effects of ten problems caused by the mechanics of existing protocols that are responsible for this throughput loss; and (3) We recommend best practices for using vehicular opportunistic connections. Moreover, we show that overall throughput could be significantly improved if environmental information was made available to the 802.11 MAC and to TCP. The central messagein this paper is that wireless conditions in the vicinity of a roadside access point are predictable, and by exploiting this information, vehicular opportunistic access can be greatly improved.

No abstract available.

The de facto service architecture of today's communication networks, in particular the Internet, is heterogeneous, complex, ad hoc, and not particularly well understood. With layering as the only means for functional abstraction, and even this violated by middle-boxes, the diversity of current technologies can barely be expressed, let alone analyzed. As a first step to remedying this problem, we present an axiomatic formulation of fundamental forwarding mechanisms in communication networks. This formulation allows us to express precisely and abstractly the concepts of naming and addressing and to specify a consistent set of control patterns and operational primitives, from which a variety of communication services can be composed. Importantly, this framework can be used to (1) formally analyze network protocols based on structural properties, and also to (2) derive working prototype implementations of these protocols. The prototype is implemented as a universal forwarding engine, a general framework and runtime environment based on the Click router.

Optimally choosing operating parameters for access points in an enterprise wireless LAN environment is a difficult and well-studied problem. Unlike past work, the SMARTA self-managing wireless LAN architecture dynamically adjusts both access point channel assignments and power levels in response to measured changes in the wireless environment to optimize arbitrary objective functions, while taking into account the irregular nature of RF propagation, and working with unmodified legacy clients. We evaluate the SMARTA architecture through simulation and show that our solution is not only feasible, but also provides significant improvements over existing approaches. For example, in a realistic scenario, SMARTA can provide 50% more throughput and 40% lower mean per-packet delay than a hand-optimized configuration. Moreover, SMARTA can automatically reconfigure channels and power levels in response to both small and large changes in the RF environment due to client movement.

Rural kiosks in developing countries provide a variety of services such as birth, marriage, and death certificates, electricity bill collection, land records, email services, and consulting on medical and agricultural problems. Fundamental to a kiosk's operation is its connection to the Internet. Network connectivity today is primarily provided by dialup telephone, although Very Small Aperture Terminals (VSAT) or long-distance wireless links are also being deployed. These solutions tend to be both expensive and failure prone. Instead, we propose the use of buses and cars as "mechanical backhaul" devices to carry data to and from a village and an internet gateway. Building on the pioneering lead of Daknet [15], and extending the Delay Tolerant Networking Research Group architecture [24], we describe a comprehensive solution, encompassing naming, addressing, forwarding, routing, identity management, application support, and security. We believe that this architecture not only meets the top-level goals of low cost and robustness, but also exposes fundamental architectural principles necessary for any such design. We also describe our experiences in implementing a prototype of this architecture.

There has been a recent proliferation in wireless infrastructure network deployments. In a typical deployment, an installer uses either a one-time site survey or rules of thumb to place wireless access points and allocate them with channels and power levels. Because the access point location problem is inherently complex and one that requires tradeoffs among competing requirements, these approaches can result in either dead spots or significant unintended interference among wireless access points. This degrades network performance for end clients, with throughput reduction factors of 4x found in field measurements. In this paper, we take a first step towards improving client performance by coordinating choices of channels and power levels at wireless access points using a successive refinement approach. Our contributions are two-fold: first, we develop a mathematical model that crisply defines the solution space and identifies the characteristics of an optimal channel and power-level configuration. Second, we present heuristics that, under some simplifying assumptions, yield near-optimal configurations. We use Monte Carlo simulations to evaluate the performance of our heuristics. We find that the choice of heuristics for transmit power control impacts performance more than the channel allocation strategy, especially at high densities. Also, surprisingly, randomly assigning channels to access points appears to be an effective strategy at higher deployment densities. Taken together, we believe that this study paves the way to designing rapidly deployable real-world infrastructure networks that also have good performance

In large-scale infrastructure wireless networks several access points (APs) may be unusable at any given moment in time. Unlike completely failed APs, whose failure can be detected by probes to their wired interface, an AP with a faulty wireless interface or whose antenna has been accidentally shielded can only be diagnosed by the actual use of the wireless interface for data communication. We present several algorithms that detect such failed access points by online analysis of AP usage logs. In particular, we demonstrate that we can exploit device mobility to detect faulty APs. We also present efficient heuristics to select a path for a technician to repair failed access points. We evaluate our algorithms using actual log files from an infrastructure network at Dartmouth College. We find that our best algorithm is able to detect nearly 90% of failed access points simply by processing log files. Compared to a naive approach, our algorithm has more than six times fewer false positives. We are also able to construct tours that are up to an order of magnitude more effective that a straightforward greedy approach. Our algorithms require no modifications to either APs or devices. We believe that these properties make our work immediately applicable to real-world scenarios

As the Internet infrastructure evolves to include quality of service (QoS), a lot of work has been done on how to allocate network resources to satisfy the QoS requirements of IP flows. Less attention is being paid to mapping the network QoS specifications, e.g., network delay and loss rate, to the (perceived) end-to-end performance of user applications, e.g., the latency of retrieving a Web page. We study the impact of the network QoS on the perceived end-to-end performance of user applications. We first propose a generic testbed using a combination of simulation and emulation techniques. It can be used to evaluate the end-to-end performance of user applications in different network environments. Next, we use this testbed to study the effect of network QoS metrics on the perceptual quality of various user applications. We focus on estimating the latency of Web retrieval under given packet delay and loss rate and derive an accurate and efficient TCP short connection performance model.

Most current schemes for multicast routing assume that multicast routers participate both in forwarding multicast packets and in control algorithms for routing, resource reservation, and group management. By separating data and control flow, and by centralizing control in distinct control elements, we have designed a simple and scalable approach to IP multicast that we call Centralized Multicast. We present the details of our approach, a proof of its correctness, analysis of its performance, and a discussion of its advantages over current schemes.

/sup A/s the most widely used reliable transport in today's Internet, TCP has been extensively studied in the past. However previous research usually only considers a small or medium number of concurrent TCP flows. The TCP behavior under many competing TCP flows has not been sufficiently explored. In this paper we use extensive simulations to investigate the individual and aggregate TCP performance for a large number of concurrent TCP flows. First, we develop a simple yet realistic network model to abstract an Internet connection. Based on the model, we study the performance of a single TCP flow with many competing TCP flows by evaluating the best-known analytical model proposed in the literature. Finally, we examine the aggregate TCP behavior and derive general conclusions about overall throughput, goodput, and loss probability.

As Internet services rapidly become an essential part of the global infrastructure, it is necessary for the protocols underlying these services to be robust and fail-safe. To achieve this goal, protocol developers should be able to design, implement, simulate, visualize, and validate their work in a protocol development environment before deployment in the field. We describe the ENTRAPID protocol development environment, outline its implementation, and present a performance evaluation.

The Internet is increasingly being called upon to provide different levels of service to different applications and users. A practical problem in doing so is that although Ethernet is one of the hops for nearby all communication in the Internet, it does not provide any QoS guarantees. A natural question, therefore, is the effect of offered load on Ethernet throughput and delay. In this paper, we present several techniques for accurately and efficiently modeling the behavior of a heavily loaded Ethernet link. We propose an efficient distributed simulation model, called Fast Ethernet Simulation, that empirically models an Ethernet link to quickly and accurately simulate it. By eliminating the implementation of the CSMA/CD protocol, our approach reduces computational complexity drastically while still maintaining desirable accuracy. Performance results show that our techniques not only add very little overhead (less than 5% in our tests) to the basic cost of simulating an Ethernet link, but also closely match real-world measurements. We also present efficient techniques for compressing cumulative distributions using hyperbolic curves and for monitoring the load on a heavily loaded link. Finally, we show applications to illustrate the potential usage of the Fast Ethernet Simulation.

Feedback flow control, in conjunction with limited buffering in the network, inevitably leads to packet loss. Effective congestion control requires not only effective flow control but also a good retransmission strategy. We present a new retransmission strategy called SMART that combines the best features of the traditional go-back-n and selective-retransmit strategies. We show, first, that go-back-n retransmission with static window flow control leads to congestion collapse when the nominal load exceeds the link capacity. Second, we can avert congestion collapse by replacing go-back-n with SMART retransmission, even with static window flow control. Third, SMART retransmission, when combined with packet-pair rate-based flow control, performs extremely well, both when losses are due to buffer overflows and when losses are random.

Variable bit-rate (VBR) compressed video traffic is expected to be a significant component of the traffic mix in integrated services networks. This traffic is hard to manage because it has strict delay and loss requirements while simultaneously exhibiting burstiness at multiple time scales. We show that burstiness over long time scales, in conjunction with resource reservation using one-shot traffic descriptors, can substantially degrade the loss rate, end-to-end delay, and statistical multiplexing gain of a connection. We use large-deviation theory to model the performance of multiple time-scale traffic and to motivate the design of renegotiated constant bit rate (RCBR) service. Sources using RCBR service are presented with an abstraction of a fixed-size buffer which is drained at a constant rate. They may renegotiate the drain rate to match their workload. Because all traffic entering the network is constant bit-rate (CBR), RCBR requires minimal buffering and scheduling support in switches. We show that the service is suitable for both stored and online video sources. An RCBR source must decide when to renegotiate its service rate and what the new service rate should be. We present: (1) an algorithm to compute the optimal renegotiation schedule for stored (offline) traffic and (2) a heuristic to approximate the optimal schedule for online traffic. We also discuss measurement-based admission control (MBAC) for RCBR traffic. Simulation experiments show that RCBR is able to extract almost all of the statistical multiplexing gain available by exploiting slow time-scale variations in traffic. Moreover, simple admission control schemes are sufficient to keep the renegotiation failure probability below a small threshold while still offering high link utilization. Thus, we believe that RCBR is a simple, practical, and effective service for carrying multiple time-scale traffic.

This paper is a retrospective on the design of Xunet 2, one of the earliest functional wide-area asynchronous transfer mode (ATM) networks. Work on Xunet 2 began in 1989 and the network, consisting of experimental ATM switches, IP routers, and 45 Mb/s transmission lines, has been operational since October 1991. The network serves as a "laboratory without walls" for eight research groups across the United States. While Xunet 2 has only a small number of nodes, it was designed as a prototype of a nationwide ATM network. This paper reviews some of the design decisions and lessons learned in the project and points out the research directions motivated by this work, focusing on the areas of traffic management, ATM switch design, network control, and the implementation of an IP router.

We describe the design, implementation, and performance tuning of a transport layer targeted specifically for ATM networks. The layer has been built from scratch to minimize overhead in the critical path and take advantage of ATM adaptation layer 5 functionality. It provides reliable or unreliable data delivery with feedback or leaky-bucket flow control. These services can be combined to create a customized transport service. Our work is novel in that it is the first end-to-end ATM transport service to provide reliable, flow controlled data transfer. We describe the mechanisms and the operating system support needed to provide these services. A detailed performance measurement allows us to determine the bottlenecks in our system and do tune our implementation. With this tuning, we are able to achieve a user-to-user throughput of 55 Mbps between two 66 MHz Intel 80486 personal computers with Fore Systems' HPA-200 EISA-bus host adaptors. The user-to-user latency for small messages is around 720 /spl mu/s. These figures compare favorably with the performance from far more expensive workstations and validate the correctness of our design choices.

We investigate the performance of CBR traffic in the context of large-scale networks, where many connections and switches coexist and interact. We develop a framework for simulating such networks, decoupling the influence of breadth and depth. Our results are briefly as follows: we found that a Poisson stream is a good approximation to a superposition of many CBR streams with differing phases and bandwidths. Delays incurred by a reference stream with cross traffic composed of many CBR streams with different bandwidths and phases do not exceed a few cell times even under heavy load, which means that buildout buffers of 10 to 20 cells seem to be sufficient after traversing 20 switches. CBR traffic can be efficiently served by the first come first served (FCFS) scheduling discipline, which has the least implementation cost. Surprisingly, the round robin (RR) and weighted round robin (WRR) disciplines perform worse than the FCFS, despite their greater implementation complexity. We also compare an analytical approximation method based on the multiclass parametric decomposition method, with the simulation results and found it to be suitable for estimating the end-to-end delays for the FCFS discipline.

We describe the design, implementation, and performance measurement of a transport layer targeted specifically for asynchronous transfer mode (ATM) networks. The layer has been built from scratch to minimize overhead in the critical path, provide per-virtual circuit quality of service (QoS) guarantees, and take advantage of ATM adaptation layer 5 functionality. It provides reliable and unreliable data delivery with a choice of feedback and leaky-bucket flow control. These services can be combined to create per-virtual-circuit customized transport services. Our work is novel in that it provides high-performance, reliable, flow-controlled transport service using cheap personal computers (PCs). We describe the mechanisms and the operating system support needed to provide these services in detail. An extensive performance measurement allows us to pinpoint and eliminate inefficiencies in our implementation. With this tuning, we are able to achieve a user-to-user throughput of 55 Mb/s between two 66 MHz Intel 80486 personal computers with FORE Systems' HPA-200 EISA-bus host adaptors. The user-to-user latency for small messages is around 720 /spl mu/s. These figures compare favorably with the performance of far more expensive workstations and validate the correctness of our design choices.

Compressed video traffic is expected to be a significant component of the traffic mix in integrated services networks. This traffic is hard to manage, since it has strict delay and loss requirements, but at the same time, exhibits burstiness at multiple time-scales. In this paper, we observe that slow time-scale variations can cause sustained peaks in the source rate, substantially degrading performance. We use large deviation theory to study this problem and to motivate the design of Renegotiated Constant Bit Rate Service (RCBR), that adds renegotiation and buffer monitoring to traditional CBR service. We argue the the load placed on signalling by RCBR can be handled by current technology. We present a) an algorithm to compute the optimal renegotiation schedule for stored (off-line) traffic, and b) a heuristic to approximate the optimal schedule for online traffic. Simulation experiments show that RCBR is able to extract almost all of the statistical multiplexing gain available by exploiting slow time-scale variations in traffic. In more general terms, we believe that a clean system design must match control time-scales to the time scales over which the workload varies. RCBR works well because it makes intelligent use of this time-scale separation.

When carrying Internet protocol (IP) traffic over an asynchronous transfer mode (ATM) network, the ATM adaptation layer must determine how long to hold a virtual circuit opened to carry an IP datagram. We present a formal statement of the problem and carry out a detailed empirical examination of various holding time policies taking into account the issue of network pricing. We offer solutions for two natural pricing models, the first being a likely pricing model of future ATM networks, while the second is based on characteristics of current networks. For each pricing model, we study a variety of simple nonadaptive policies as well as easy to implement policies that adapt to the characteristics of the IP traffic. We simulate our policies on actual network traffic, and find that policies based on least recently used (LRU) perform well, although the best adaptive policies provide a significant improvement over LRU.>

When carrying Internet Protocol (IP) traffic over an asynchronous transfer mode (ATM) network, the ATM adaptation layer must determine how long to hold a virtual circuit opened to carry an IP datagram. The authors present a formal statement of the problem and an empirical study of holding time policies taking network pricing into account. They find that IP traffic shows temporal locality of reference and so least recently used (LRU)-based policies perform well. A system-wide timeout, which is a special case of an LRU policy, is quite effective when the timeout value is chosen correctly. The policies proposed are easy to implement and solve the problem satisfactorily.>

Applications communicating over connectionless networks, such as IP, cannot obtain per-connection Quality of Service (QoS) guarantees. In contrast, the connection-oriented nature of the ATM layer and its per-virtual-circuit QoS guarantees are visible to a native-mode ATM application. We describe the design and implementation of operating system and signaling support for native-mode applications, independent of the semantics of the protocol layers or of the signaling protocol. The work was done in the context of a Unix-like operating system and the Xunet 2 wide-area high-speed ATM network. The IPC-based interface between an application and the signaling entity allows processes to request parameterized virtual circuits, and the signaling-kernel interface allows resources to be reclaimed from prematurely terminating processes. We also built a simple encapsulation layer over raw IP that allows any host with IP access to send AAL frames into the wide-area network with little performance degradation. Our design makes it simple to port existing TCP/IP socket applications to a native-mode ATM protocol stack and also enables interoperation of existing IP networks with our ATM network. Our experience has been positive - the design is robust, easily extendible and scales well with the number of open connections.

The problem of finding the worst-case end-to-end delay and buffer occupancy bounds in asynchronous transfer mode (ATM) networks with rate-controlled, non-work-conserving servers is addressed. A theoretical framework is constructed to analyze such servers in isolation and in tandem. The analysis is based on a simple fluid model, but care is taken so that the computed delay and buffer occupancy values are upper bounds on actual values. A single algorithm is presented to perform these calculations in linear time. Simulation results are given in order to compare the computed worst-case delays with the actual delays obtained on some simple network topologies. The algorithm is found to predict node delays well for bursty input traffic, but poorly for smooth input traffic. Buffer requirements are predicted well in both cases.>

This paper presents a control-theoretic approach to reactive flow control in networks that do not reserve bandwidth.We assume a round-robin-like queue service discipline in the output queues of the network's switches, and propose deterministic and stochastic models for a single conversation in a network of such switches.These models motivate the Packet-Pair rate probing technique, and a provably stable rate-based flow control scheme.A Kalman state estimator is derived from d~crete-time state space analysis, but there are difficulties in using the estimator in practice.These difficulties are overcome by a novel estimation scheme based on fuzzy logic.We then present a technique to extract and use additional information horn the system to develop a continuous-time system model.This is used to design a wuisnt of the control law that is also provably stable, and, in addition, takes control action as rapidly as possible.Finally, practical issues such as correcting parameter drift and cmmlination with window flow control are described.

This paper compares six new queue service disciplines that can be implemented at the output queues of switches in a connection-oriented packet switched data network. These are Virtual Clock, Fair Queueing, Delay-Earliest-DueDate, Jitter-Earliest-Due-Date, Stop-and-Go and Hierarchical Round Robin. We describe their mechanisms, their similarities and differences, and some implementation strategies. In particular, we show why each discipline can or cannot provide bandwidth, delay and delay jitter guarantees. This leads to some interesting conclusions about the relative strengths and weaknesses of each approach. 1 Introduction High speed networking introduces opportunities for new applications that have stringent performance requirements in terms of throughput, delay, delay jitter 1 and loss rate [3]. Conventional packet switching data networks with windowbased flow control and first-come-first-served service discipline cannot provide services with strict performance guarantees. Thus, n...

We discuss gateway queueing algorithms and their role in controlling congestion in datagram networks. A fair queueing algorithm, based on an earlier suggestion by Nagle, is proposed. Analysis and simulations are used to compare this algorithm to other congestion control schemes. We find that fair queueing provides several important advantages over the usual first-come-first-serve queueing algorithm: fair allocation of bandwidth, lower delay for sources using less than their full share of bandwidth, and protection from ill-behaved sources.