284 Gates Hall, Stanford University, Stanford, CA 94305
raejoon at stanford dot edu
Large scale storage systems use erasure coding to recover from data unavailability. A system repairs an unavailable data block by reading in and processing multiple coded blocks. A request for a lost block requires a node to read blocks across many nodes in the network. This greatly impacts tail latency of read requests.
We propose DRED, an algorithm that reduces repair time for distributed, encoded data. DRED dynamically constructs a repair tree based on which nodes store encoded blocks and their available network capacity. DRED handles cases where different nodes have different available capacity (e.g., due to cluster manager allocation in the cloud) as well as when uplink and downlink capacities differ (as is common for residential last mile links).
LoRa is a prominent radio technology for large-area Internet of Things (IoT) applications. LoRa can transmit small packets over a range of miles with extremely low power. The combination of long range and low bitrate means packet collisions are common. Normally, when two LoRa transmissions collide, one or both packets are lost, wasting energy.
We present two novel cross-layer techniques that enable LoRa receivers to successfully receive colliding packets with high probability. The first, called symbol querying (SQ), changes the interface between the LoRa demodulator and decoder. Symbol querying greatly improves the ability of a LoRa receiver to successfully receive the stronger frame in a collision. It does so by elevating the error detection capabilities of channel coding into error correction. For instance, a receiver using (8,4)-extended Hamming codes can correct two, instead of only one, bit error per codeword. The second technique, called symbol successive interference cancellation (SSIC), uses the unique discrete properties of LoRa symbols to be able to efficiently receive the weaker frame in a collision. SSIC subtracts the stronger frame’s peaks in the frequency domain.
Many wireless protocols send periodic beacons. To improve performance and avoid contention, protocols use a variety of ad-hoc mechanisms to desynchronize and separate these beacons in time. We propose Solo Timers, an efficient, general, and simple, distributed desynchronization algorithm. The design is partly based on the pulse-coupled oscillator, a control system that prior work has shown can theoretically desynchronize a single hop network. Solo Timers refine the pulse-coupled oscillator to be able to desynchronize multihop networks and remain stable despite hardware and software time jitter. A path vector-based algorithm allows Solo Timers to detect and repair unstable configurations that can occur in multihop networks.