טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentElazar Raviv
SubjectAlgorithms for Two-Tier Scalable Data Upload
DepartmentDepartment of Computer Science
Supervisor Professor Hadas Shachnai
Full Thesis textFull thesis text - English Version


Abstract


The many-to-one upload problem arises when a set of users needs to upload data to a single server. Uploads correspond to an important class of applications, many of which are limited by a deadline. This includes, e.g., electronic submissions of income tax forms, online shopping for limited-time bargain products, and gathering data from sensor networks. Such services create hot spots, which is a major hurdle in achieving scalability in network-based applications.

Two-tier protocols attempt to relieve hot spots in many-to-one applications. In this model, clients upload their data to intermediaries (also called bistros), to reduce the traffic to the destination around a deadline. The destination server then computes a schedule for pulling the data from bistros after the deadline. Bistros have limited storage capacity, and each bistro j may fail with some probability 0 < pj < 1.

Previous works on reliable data upload report on experimental results. Our main contribution is a theoretical study of several algorithms for the many-to-one upload problem in two-tier protocols. The proposed algorithms achieve reliability through file replication, or by using Forward-error- correcting codes (FEC). Our results show that FEC-based algorithms out- perform replication-based algorithms in space complexity as well as in reliable data transmission. We also show that a distributed FEC-based algorithm achieves higher reliability compared to a centralized algorithm, at the cost of higher message complexity.