Maelstrom: Network-sync Implementation

The network-sync implementation used in our work is based on Forward Error Correction (FEC). FEC is a generic term for a broad collection of techniques aimed at proactively recovering from packet loss or corruption. FEC implementations for data generated in real-time are typically parameterized by a rate $(r,c)$ : for every $r$ data packets, $c$ error correction packets are introduced into the stream. Of importance here is the fact that FEC performance is independent of link length (except to the extent that loss rates may be length-dependent).

The specific FEC protocol we worked with is called Maelstrom [10], and is designed to match the observed loss properties of multi-hop wide-area networks such as TeraGrid. Maelstrom is a symmetric network appliance that resides between the datacenter and the wide-area link, much like a NAT box. The solution is completely transparent to applications using it, and employs a mixture of technologies: routing tricks to conceal itself from the endpoints, a link-layer reliability protocol (currently TCP), and a novel FEC encoding called layered interleaving, designed for data transfer over long-haul links with potentially bursty loss patterns. To minimize the rate-sensitivity of traditional FEC solutions, Maelstrom aggregates all data flowing between the primary and backup sites an operates on the resulting high-speed stream. See Balakrishnan et al. [10] for a detailed description of layered interleaving and analysis of its performance tolerance to random and bursty loss.

Maelstrom also adds feedback notification callbacks. Every time Maelstrom transmits a FEC packet, it also issues a callback. The local storage system then employs a redundancy model to infer the level of safety associated with in-flight data packets. For this purpose, a local storage system needs to know the underlying network's properties -- loss rate, burst length, etc. It uses these to model the behavior of Maelstrom mathematically [10], and then makes worst-case assumptions about network loss to arrive at the needed estimate of the risk of data loss. We expect system operators monitor network behavior and periodically adjust Maelstrom parameters to adapt to any changes in the network characteristics.

There are cases in which the Maelstrom FEC protocol is unable to repair the loss (this can only occur if several packets are lost, and in specific patterns that prevent us from using FEC packets for recovery). To address such loss patterns, we run our mirroring solution over TCP, which in turn runs over Maelstrom: if Maelstrom fails to recover a lost packet, the end-to-end TCP protocol will recover it from the sender.