{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/88185"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/88185","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Power of d choices for large-scale bin packing: a loss model","abstract":"A system with N parallel servers is considered in our thesis. Each server consists of B units of a resource and jobs arrive at this system according to a Poisson process. Each job stays in the system for an exponentially distributed amount of time. Moreover, each job may request different units of the resource from the system. Our goal is to understand how to route arriving jobs to the servers to minimize the probability that an arriving job does not find the required amount of resource at the server, i.e., the goal is to minimize blocking probability. Our motivation arises from the design of cloud computing systems in which the jobs are virtual machines (VMs) that request resources such as memory from a large pool of servers. In our thesis, we consider power-of-d-choices routing, where a job is routed to the server with the largest amount of available resources among d 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity, and use numerical methods to approximate the blocking probability. Moreover, we also show the simulation for the system.","abstract_html":"A system with N parallel servers is considered in our thesis. Each server consists of B units of a resource and jobs arrive at this system according to a Poisson process. Each job stays in the system for an exponentially distributed amount of time. Moreover, each job may request different units of the resource from the system. Our goal is to understand how to route arriving jobs to the servers to minimize the probability that an arriving job does not find the required amount of resource at the server, i.e., the goal is to minimize blocking probability. Our motivation arises from the design of cloud computing systems in which the jobs are virtual machines (VMs) that request resources such as memory from a large pool of servers. In our thesis, we consider power-of-d-choices routing, where a job is routed to the server with the largest amount of available resources among d 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity, and use numerical methods to approximate the blocking probability. Moreover, we also show the simulation for the system.","abstract_has_math":false,"creators":["Dong, Xiaobo"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engineering","degree_department":null,"school":null,"contributors":["Srikant, R."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-29T20:49:54Z","date_published":"2015-09-29T20:49:54Z","updated_at":"2026-07-22T22:26:31Z","subjects":["Resource allocation","Markov process","Cloud computing","Queueing"],"languages":["en"],"rights":["Copyright 2015 Xiaobo Dong"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/88185","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srikant, R."]},{"key":"dc:creator","label":"Author","values":["Dong, Xiaobo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-29T20:49:54Z","2017-09-30T09:15:32Z","2015-08","2015-07-14","2015-8"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engineering"]},{"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":["Resource allocation","Markov process","Cloud computing","Queueing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2015 Xiaobo Dong"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/88185"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["A system with N parallel servers is considered in our thesis. Each server consists of B units of a resource and jobs arrive at this system according to a Poisson process. Each job stays in the system for an exponentially distributed amount of time. Moreover, each job may request different units of the resource from the system. Our goal is to understand how to route arriving jobs to the servers to minimize the probability that an arriving job does not find the required amount of resource at the server, i.e., the goal is to minimize blocking probability. Our motivation arises from the design of cloud computing systems in which the jobs are virtual machines (VMs) that request resources such as memory from a large pool of servers. In our thesis, we consider power-of-d-choices routing, where a job is routed to the server with the largest amount of available resources among d 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity, and use numerical methods to approximate the blocking probability. Moreover, we also show the simulation for the system.","Submission published under a 24 month embargo labeled 'U of I only', the embargo will last until 2017-08-01","The student, Xiaobo Dong, accepted the attached license on 2015-07-13 at 13:40.","The student, Xiaobo Dong, submitted this Thesis for approval on 2015-07-13 at 13:47.","This Thesis was approved for publication on 2015-07-14 at 11:27.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8427 on 2015-09-29 at 14:59:26","Made available in DSpace on 2015-09-29T20:49:54Z (GMT). No. of bitstreams: 2 DONG-THESIS-2015.pdf: 476231 bytes, checksum: 3170c3daadc769b8e199a90081ec53ef (MD5) LICENSE.txt: 4208 bytes, checksum: 85e602e1abe63554caf585499afaeff8 (MD5) Previous issue date: 2015-07-14","Embargo set by: Seth Robbins for item 89465 Lift date: 2017-09-29T20:50:34Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 89465 on 2017-09-30T09:15:32Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Power of d choices for large-scale bin packing: a loss model"]}]}],"canonical_facts":{"dc:contributor":["Srikant, R."],"dc:creator":["Dong, Xiaobo"],"dc:date":["2015-09-29T20:49:54Z","2017-09-30T09:15:32Z","2015-08","2015-07-14","2015-8"],"dc:description":["A system with N parallel servers is considered in our thesis. Each server consists of B units of a resource and jobs arrive at this system according to a Poisson process. Each job stays in the system for an exponentially distributed amount of time. Moreover, each job may request different units of the resource from the system. Our goal is to understand how to route arriving jobs to the servers to minimize the probability that an arriving job does not find the required amount of resource at the server, i.e., the goal is to minimize blocking probability. Our motivation arises from the design of cloud computing systems in which the jobs are virtual machines (VMs) that request resources such as memory from a large pool of servers. In our thesis, we consider power-of-d-choices routing, where a job is routed to the server with the largest amount of available resources among d 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity, and use numerical methods to approximate the blocking probability. Moreover, we also show the simulation for the system.","Submission published under a 24 month embargo labeled 'U of I only', the embargo will last until 2017-08-01","The student, Xiaobo Dong, accepted the attached license on 2015-07-13 at 13:40.","The student, Xiaobo Dong, submitted this Thesis for approval on 2015-07-13 at 13:47.","This Thesis was approved for publication on 2015-07-14 at 11:27.","DSpace SAF Submission Ingestion Package generated from Vireo submission #8427 on 2015-09-29 at 14:59:26","Made available in DSpace on 2015-09-29T20:49:54Z (GMT). No. of bitstreams: 2 DONG-THESIS-2015.pdf: 476231 bytes, checksum: 3170c3daadc769b8e199a90081ec53ef (MD5) LICENSE.txt: 4208 bytes, checksum: 85e602e1abe63554caf585499afaeff8 (MD5) Previous issue date: 2015-07-14","Embargo set by: Seth Robbins for item 89465 Lift date: 2017-09-29T20:50:34Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 89465 on 2017-09-30T09:15:32Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/88185"],"dc:language":["en"],"dc:rights":["Copyright 2015 Xiaobo Dong"],"dc:subject":["Resource allocation","Markov process","Cloud computing","Queueing"],"dc:title":["Power of d choices for large-scale bin packing: a loss model"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:31Z"}