57 %
43 %
Information about INFOCOM99

Published on October 5, 2007

Author: Techy_Guy



Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads :  Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads John Byers, Boston University Michael Luby, Digital Fountain, Inc. Michael Mitzenmacher, Harvard INFOCOM 99 The Problem:  The Problem Multicast: to save bandwidth. Sender Receivers Senders Receiver Parallel download: to improve speed. Many-to-many Distribution:  Many-to-many Distribution Heterogeneous environment of senders and receivers. Senders broadcast. Receivers gather data as fast as possible from as many sources as possible. Senders Receivers Results:  Results A simple, robust, scalable solution for parallel downloads and many-to-many distribution using Forward Error Correction. Examination of tradeoffs Speed vs. Goodput Applications:  Applications Internet Connect to many mirror sites simultaneously. Multiple access media ISDN and modem simultaneously. Mobile clients Multiple access points. Listen to multiple frequencies. Satellite networks Ground user receives from many satellites. Assumptions:  Assumptions Possible to create bottleneck-disjoint paths. Otherwise wasted bandwidth, more congestion. Receiver should not be the bottleneck. For people with big pipes. Senders Receiver Senders Receiver dropped Bottleneck Disjoint Shared Bottleneck Solutions without Coding:  Solutions without Coding A protocol without codes: Initially receiver tells each of s senders to send disjoint 1/s parts of the file. If one sender finishes early, re-negotiate packets to be sent. Continue until all packets arrive. Problems Significant feedback. Unsuitable for many-to-many. Complexity. No protection against losses. Wait for last packet. Forward Error Correction (FEC):  Forward Error Correction (FEC) Message of n packets encoded as cn packets. A receiver decodes once enough packets arrive. FEC codes improve multicast scalability Encoding packets can correct different losses for different receivers. Reduces feedback, to even feedback-free solutions. Tornado Codes:  Tornado Codes Tornado Codes are FEC codes that are Very fast (linear time). Better for large files. Information-theoretically slightly suboptimal. Requires 1.055n packets to decode n packet message. Ideal Solution: Digital Fountain:  Ideal Solution: Digital Fountain Reconstruct file from any n packets, from any source. Feedback free: no need for receivers to acknowledge specific packets. Fountain metaphor: drink when the cup is full. Approximate digital fountain solution using Tornado codes. Reception inefficiency due to overhead of Tornado codes, duplicate packets. Feedback Free Solution:  Feedback Free Solution Senders encode message the same way. Senders cycle through permutation of encoding When receiver obtain any 211 distinct packets, it can decode to obtain the message. 1 - 200 1 - 600 Original Message Encoded Message 17 485 238 12 311 411 512... 216 156 7 128 415 238 333... 397 188 25 315 275 499 12... Performance Metrics:  Performance Metrics Speedup: Stretch factor (c): message of n packets encoded as cn packets. Reception inefficiency (z): zn packets arrive before decoding. Code overhead Duplicates Download time now Download time using single fastest sender Tradeoffs:  Tradeoffs Increasing stretch c: Lessens duplicates: senders have more packets to send, so random collisions less likely Increases encoding/decoding time, memory requirements, and complexity. (Grow linearly in c.) 17 485 238 12 311 411 512... 216 156 7 128 415 238 333... 397 188 25 315 275 499 12... Feedback Free Solution:  Feedback Free Solution Pros Simple Loss protection Good download speedups No feedback, coordination Solves many-to-many Cons Extra bandwidth for Tornado codes (5.5%) Extra bandwidth from packet duplicates depends on c, number of senders, variation in rates additional 5-25+ % Rare Feedback:  Rare Feedback Senders use same permutation of encoding. Receivers tell each of s senders to send 1/s of the encoding. If c > s, each sender has 1 file worth of data. In rare cases, re-negotiate, or have senders send the rest in random order. Rare Feedback:  Rare Feedback Pros Simple Loss protection Rare feedback, minimal coordination Extra bandwidth for Tornado codes only Cons Does not solve multi-multi Extra bandwidth for Tornado Codes Conclusions:  Conclusions Fast parallel download and many-to-many distributions are practical. Trade goodput for speed. FEC improves protocols. Simpler. Less feedback. Loss protection. Deployment issues (fairness, bottleneck disjoint paths) still open.

Add a comment

Related presentations

Related pages

Preemption in Multi-Class Networks

Connection Preemption in Multi-Class Networks Fahad Rafique Dogar Carnegie Mellon University, USA Collaborators: Laeeq Aslam and Zartash Uzmi (LUMS, Pakistan)
Read more

Quick Installation Guide Gdc-600be -

Quick Installation Guide of GDC-600BE. Notice : Install the GDC-600BE in indoor place protected from the environmental effect such as a surge, very low ...
Read more

srds98 - Ace Recommendation Platform - 8

for a time interval, they can be used to exchange stateinformation between the disjoint groups. Such a bridgehas a single span: (p,q). However, multi-span ...
Read more

SelfSimilarity-GustavSerena - Ace Recommendation Platform - 8

8Measures of Burstiness: Peak to Mean• Any possible peak to mean ratio is possible depending on the length of the measurement interval.• The ...
Read more


Architectures and wireless access methods in Personal Communication Networks 1. S. Papavassiliou, L. Tassiulas, P. Tandon ``Meeting QOS requirements in a ...
Read more

Scalability & Stability of the Internet Infrastructure ...

2 Context Network Infrastructure Network Attacks S/H Failures Operational Faults Windmill Probes Netflow Statistics Protocol Scrubbers Event Aggregation ...
Read more

PPT - Atomicity for Today's Programming Languages ...

Atomicity for Today's Programming Languages. Dan Grossman University of Washington 24 March 2005. Atomic. An easier-to-use and harder-to-implement ...
Read more

References A-H -

References A-H: References A-H [3Com 2004] 3Com Corporation, “Network Interface Cards,” [3GPP 2004] Third ...
Read more

Patent US7818775 - System and method for recording and ...

Various embodiments of the disclosed subject matter provide methods and systems to record broadcast programming for at least one television channel for a ...
Read more

1MA189_3e -

TETRA Measurements Application NoteProducts: | | | | | | | R&S®SMU200A R&S®SMATE200 R&S®AMU200A R&S®SMJ100A R&S...
Read more