Accessing Multiple Mirror Sites in Parallel:
Using Tornado Codes to Speed up Downloads
Byers, Luby, Mitzenmacher

The authors argue that web clients could more efficiently download
mirrored files if each file could be spliced into forward
error-correction encoded blocks which would be downloaded in
parallel.  The two ideas, downloading in parallel and applying FEC to
mirrored files, are fairly distinct and each has its own advantages.
Mirrored files could be cut up and downloaded from several locations
using the current TCP-based point-to-point scheme and FEC could be
applied to sets of files to be downloaded to reduce the amount of
feedback to the server due to dropped packets.  The authors suggest
combining these two ideas so that several mirrors would be accessed in
parallel and that when any length n bytes of a file whose total length
was n had been received from any of them, a client ideally would be
able to reconstruct the entire file.  Parallel downloading without FEC
would work and is an interesting idea in itself but would require much
more client feedback than with a FEC scheme.  A client would need to
negotiate with each server what part of the file to send and could not
just "listen" to a fountain as with the Tornado scheme.

LT codes work like Tornado codes but allow for better on-the-fly
encoding of different stretch factors.  Whether LT codes would work
better would depend on the context of usage, on which the paper is
somewhat vague.  "Mirrored download" could refer to (1) an Akamai-like
structure where usually small files are geographically distributed,
(2) it could be a Perl CPAN, Tucows, or similar open-source structure
where a user tends to download a few, large files, or (3) it could be
a collection of geographically-close servers each of which has exactly
the same content (like nytimes.com, where a dozen servers sit in the
same room feeding the same files).  Also, on-the-fly encoding can be
emulated by pre-encoding different levels of service, so speed can be
balanced with space consumption.  In my opinion, LT codes would work
better in the few, large files case where it may not be
space-efficient to keep around multiple Tornado-encoded versions of
the same file.  Relatedly, I do not think that accessing several
mirrors is worthwhile in the Akamai model to read parts of the same
file, when usually these files are small.

Another item I found confusing in the paper was that the FEC encoded
packets seem to be transported with over TCP and not UDP.  Thus, this
scheme which exists to limit the amount of feedback rides on one which
has lots of feedback.  Phrases like "connection set-up and connection
teardown" imply TCP and it appears that FEC and multicast-based
digital fountains would offer more of their potential over unreliable
transport.


Improved Low-Density Parity-Check Codes Using Irregular Graphs
Luby, Mitzenmacher, Shokrollahi, Spielman

Regular code constructions build codes out of bipartite graphs that
have nodes of approximately the same degree; in irregular codes, nodes
have varying degrees.  Graphs where nodes have the same degree are
simpler to look at mathematically, but the authors show that irregular
codes offer better performance in the percentage of errors than
regular.  The authors offer a clear intuition at the beginning of the
paper into why nodes with differing degrees might be valuable: message
nodes (pictorially on the left) want to have high degree because
then they are more accurate (they have more redundancy) while check
nodes ideally will have low degree so their state will be known
earlier and this state can be used to check message nodes sooner.
When low degree and high degree nodes can be placed in the same graph,
a wave effect leads to low degree check nodes' values being discovered
and these values leading to the discovery of higher degree message
nodes values.

Belief Propagation "deals with fusing and propagating the impact of
new evidence and beliefs through Bayesian networks so that each
proposition eventually will be assigned a certainty measure consistent
with the axioms of probability theory." (Pearl, 1998)  It applies to
coding in that the arrival of new information, like the value of a
message or check node, propagates through the system when we look at
the decoding algorithm as a tree (like we did in class last Tuesday).