Check out the new USENIX Web site. next up previous
Next: Reliable Storage & Recovery Up: Related Work Previous: Mirroring modes

Error correcting codes

Packet level forward error correcting (FEC) schemes typically transmit $ c$ repair packets for every $ r$ data packets, using coding schemes with which all data packets can be reconstructed if at least $ r$ out of $ r+c$ data and repair packets are received [18]. In contrast, convolution codes work on bit or symbol streams of arbitrary length, and are most often decoded with the Viterbi algorithm [38]. Our work favors FEC: FEC schemes have the benefit of being highly tunable - trading off overhead and timeliness, and are very stable under stress - provided that the recovery does not result in high levels of traffic.

FEC techniques are increasingly popular. Recent applications include FEC for multicasting data to large groups [34], where FEC can be employed either by receivers [9] or senders [18,28]. In general, fast, efficient encodings like Tornado codes [11] make sender-based FEC schemes very attractive in scenarios where dedicated senders distribute bulk data to a large number of receivers.

Likewise, FEC can be used when connections experience long transmission delays, in which case the use of redundancy helps bound the delivery delays within some acceptable limits, even in the presence of errors [18,33]. For example, deep space satellite communications [43] have been using error correcting codes for decades both for achieving maximal information transfer over a restricted bandwidth communication link and in the presence of data corruption.

SMFS is not the first system to propose exposing network state to higher level storage systems [32]. The difference, however, is that network-sync can be implemented with gateway routers under the control of site operators and does not require change to wide-area Internet routers.

next up previous
Next: Reliable Storage & Recovery Up: Related Work Previous: Mirroring modes
Hakim Weatherspoon 2009-01-14