Competitive Analysis of Online Algorithms for Computer Systems

点击翻译按钮获取中文摘要

Project Title: Competitive Analysis of Online Algorithms for Computer SystemsThis research focuses on algorithms that workwith limited information. Each topic is motivated by an applicationin on-line resource allocation in computer systems and is studiedusing theoretical analysis as well as empirical evaluation.The first topic is focuses ondesigning protocols for power management.The second topic of this research addresses problemsthat arise in scheduling and load balancing for multimedia servers.The third topic focuses on the problem of balancing the use ofbandwidth and storage in caching continuous multi-media objectsfor Web proxy servers.For the power management topic, the question addressed is when to movean idle device to a lower power consumption state so as toconserve power usage while minimizing the latency experienced by theuser. The investigator expands upon previous work on power management byintroducing the notion of latency and by studying systems with multiplelevels of power usage. The work on multimedia scheduling and loadbalancing focuses on two problems. The first is scheduling transmissionof data that must be viewed continuously when clients have largebuffers that can store data transmitted ahead of time.The second problem is to perform load balancing in assigningtasks to servers when there are multiple resource requirementsthat need to be balanced. For the topic of caching continuousmulti-media objects for Web proxy servers, the challengeis that continuous data must be transmitted to the client in acontinuous sequential stream. To support the real time requirementsof streaming, web caches need to reserve bandwidth as well as spacefor each request for a continuous data object.This research investigates algorithms for balancing thesetwo resources.