{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/97349"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/97349","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Near-data scheduling for data centers with multiple levels of data locality","abstract":"Data locality is a fundamental issue for data-parallel applications. Considering MapReduce in Hadoop, the map task scheduling part requires an efficient algorithm which takes data locality into consideration; otherwise, the system may become unstable under loads inside the system's capacity region and jobs may experience longer completion times which are not of interest. The data chunk needed for any map task can be in memory, on a local disk, in a local rack, in the same cluster or even in another data center. Hence, unless there has been much work on improving the speed of data center networks, different levels of service rates still exist for a task depending on where its data chunk is saved and from which server it receives service. Most of the theoretical work on load balancing is for systems with two levels of data locality including the Pandas algorithm by Xie et al. and the JSQ-MW algorithm by Wang et al., where the former is both throughput and heavy-traffic optimal, while the latter is only throughput optimal, but heavy-traffic optimal in only a special traffic load. We show that an extension of the JSQ-MW algorithm for a system with thee levels of data locality is throughput optimal, but not heavy-traffic optimal for all loads, only for a special traffic scenario. Furthermore, we show that the Pandas algorithm is not even throughput optimal for a system with three levels of data locality. We then propose a novel algorithm, Balanced-Pandas, which is both throughput and heavy-traffic optimal. To the best of our knowledge, this is the first theoretical work on load balancing for a system with more than two levels of data locality. This is more challenging than two levels of data locality as a dilemma between performance and throughput emerges.","abstract_html":"Data locality is a fundamental issue for data-parallel applications. Considering MapReduce in Hadoop, the map task scheduling part requires an efficient algorithm which takes data locality into consideration; otherwise, the system may become unstable under loads inside the system's capacity region and jobs may experience longer completion times which are not of interest. The data chunk needed for any map task can be in memory, on a local disk, in a local rack, in the same cluster or even in another data center. Hence, unless there has been much work on improving the speed of data center networks, different levels of service rates still exist for a task depending on where its data chunk is saved and from which server it receives service. Most of the theoretical work on load balancing is for systems with two levels of data locality including the Pandas algorithm by Xie et al. and the JSQ-MW algorithm by Wang et al., where the former is both throughput and heavy-traffic optimal, while the latter is only throughput optimal, but heavy-traffic optimal in only a special traffic load. We show that an extension of the JSQ-MW algorithm for a system with thee levels of data locality is throughput optimal, but not heavy-traffic optimal for all loads, only for a special traffic scenario. Furthermore, we show that the Pandas algorithm is not even throughput optimal for a system with three levels of data locality. We then propose a novel algorithm, Balanced-Pandas, which is both throughput and heavy-traffic optimal. To the best of our knowledge, this is the first theoretical work on load balancing for a system with more than two levels of data locality. This is more challenging than two levels of data locality as a dilemma between performance and throughput emerges.","abstract_has_math":false,"creators":["Yekkehkhany, Ali"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Lu, Yi"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-08-10T19:14:59Z","date_published":"2017-08-10T19:14:59Z","updated_at":"2026-07-22T22:24:32Z","subjects":["Queueing theory","Load balancing","Scheduling","Routing","Near-data scheduling","Data locality","Data center"],"languages":["en"],"rights":["Copyright 2017 Ali Yekkehkhany"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/97349","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lu, Yi"]},{"key":"dc:creator","label":"Author","values":["Yekkehkhany, Ali"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-08-10T19:14:59Z","2017-04-19","2017-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Queueing theory","Load balancing","Scheduling","Routing","Near-data scheduling","Data locality","Data center"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Ali Yekkehkhany"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/97349"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Data locality is a fundamental issue for data-parallel applications. Considering MapReduce in Hadoop, the map task scheduling part requires an efficient algorithm which takes data locality into consideration; otherwise, the system may become unstable under loads inside the system's capacity region and jobs may experience longer completion times which are not of interest. The data chunk needed for any map task can be in memory, on a local disk, in a local rack, in the same cluster or even in another data center. Hence, unless there has been much work on improving the speed of data center networks, different levels of service rates still exist for a task depending on where its data chunk is saved and from which server it receives service. Most of the theoretical work on load balancing is for systems with two levels of data locality including the Pandas algorithm by Xie et al. and the JSQ-MW algorithm by Wang et al., where the former is both throughput and heavy-traffic optimal, while the latter is only throughput optimal, but heavy-traffic optimal in only a special traffic load. We show that an extension of the JSQ-MW algorithm for a system with thee levels of data locality is throughput optimal, but not heavy-traffic optimal for all loads, only for a special traffic scenario. Furthermore, we show that the Pandas algorithm is not even throughput optimal for a system with three levels of data locality. We then propose a novel algorithm, Balanced-Pandas, which is both throughput and heavy-traffic optimal. To the best of our knowledge, this is the first theoretical work on load balancing for a system with more than two levels of data locality. This is more challenging than two levels of data locality as a dilemma between performance and throughput emerges.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Ali Yekkehkhany, accepted the attached license on 2017-04-13 at 11:48.","The student, Ali Yekkehkhany, submitted this Thesis for approval on 2017-04-13 at 12:07.","This Thesis was approved for publication on 2017-04-19 at 12:33.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10739 on 2017-08-10 at 13:39:46","Made available in DSpace on 2017-08-10T19:14:59Z (GMT). No. of bitstreams: 2 YEKKEHKHANY-THESIS-2017.pdf: 1297084 bytes, checksum: 152c7d4806da0d60025ea30fc9dc3823 (MD5) LICENSE.txt: 4212 bytes, checksum: bfc540a20f94e149050b295a0627e60d (MD5) Previous issue date: 2017-04-19"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Near-data scheduling for data centers with multiple levels of data locality"]}]}],"canonical_facts":{"dc:contributor":["Lu, Yi"],"dc:creator":["Yekkehkhany, Ali"],"dc:date":["2017-08-10T19:14:59Z","2017-04-19","2017-05"],"dc:description":["Data locality is a fundamental issue for data-parallel applications. Considering MapReduce in Hadoop, the map task scheduling part requires an efficient algorithm which takes data locality into consideration; otherwise, the system may become unstable under loads inside the system's capacity region and jobs may experience longer completion times which are not of interest. The data chunk needed for any map task can be in memory, on a local disk, in a local rack, in the same cluster or even in another data center. Hence, unless there has been much work on improving the speed of data center networks, different levels of service rates still exist for a task depending on where its data chunk is saved and from which server it receives service. Most of the theoretical work on load balancing is for systems with two levels of data locality including the Pandas algorithm by Xie et al. and the JSQ-MW algorithm by Wang et al., where the former is both throughput and heavy-traffic optimal, while the latter is only throughput optimal, but heavy-traffic optimal in only a special traffic load. We show that an extension of the JSQ-MW algorithm for a system with thee levels of data locality is throughput optimal, but not heavy-traffic optimal for all loads, only for a special traffic scenario. Furthermore, we show that the Pandas algorithm is not even throughput optimal for a system with three levels of data locality. We then propose a novel algorithm, Balanced-Pandas, which is both throughput and heavy-traffic optimal. To the best of our knowledge, this is the first theoretical work on load balancing for a system with more than two levels of data locality. This is more challenging than two levels of data locality as a dilemma between performance and throughput emerges.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-08-10 without embargo terms","The student, Ali Yekkehkhany, accepted the attached license on 2017-04-13 at 11:48.","The student, Ali Yekkehkhany, submitted this Thesis for approval on 2017-04-13 at 12:07.","This Thesis was approved for publication on 2017-04-19 at 12:33.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10739 on 2017-08-10 at 13:39:46","Made available in DSpace on 2017-08-10T19:14:59Z (GMT). No. of bitstreams: 2 YEKKEHKHANY-THESIS-2017.pdf: 1297084 bytes, checksum: 152c7d4806da0d60025ea30fc9dc3823 (MD5) LICENSE.txt: 4212 bytes, checksum: bfc540a20f94e149050b295a0627e60d (MD5) Previous issue date: 2017-04-19"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/97349"],"dc:language":["en"],"dc:rights":["Copyright 2017 Ali Yekkehkhany"],"dc:subject":["Queueing theory","Load balancing","Scheduling","Routing","Near-data scheduling","Data locality","Data center"],"dc:title":["Near-data scheduling for data centers with multiple levels of data locality"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:32Z"}