Competitive Analysis of Online Algorithms for Computer Systems

计算机系统在线算法的竞争分析

• 批准号: 0105498
• 负责人: Sandra Irani
• 金额: $ 16.4万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0105498&HistoricalAwards=false
• 关键词: Competitive; Analysis; Online; Algorithms; Computer

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.

项目标题：计算机系统在线算法的竞争性分析这项研究的重点是在有限信息下工作的算法。每个主题都是受计算机系统在线资源分配应用的启发，采用理论分析和经验评估相结合的方法进行研究。第一个主题是电源管理协议的设计。第二个主题是多媒体服务器的调度和负载均衡问题。第三个主题是Web代理服务器缓存连续多媒体对象时的带宽和存储平衡问题。对于电源管理主题，所解决的问题是什么时候将空闲设备移动到较低的功耗状态，以便在最大限度地减少用户延迟的同时节省功耗。研究人员通过引入延迟的概念和研究具有多层次功率使用的系统来扩展以前关于功率管理的工作。多媒体调度和负载均衡的研究主要集中在两个问题上。第一个问题是调度数据的传输，当客户端具有可以存储提前传输的数据的大缓冲区时，必须连续查看这些数据。第二个问题是当存在需要平衡的多个资源需求时，在将任务分配给服务器时执行负载平衡。对于Web代理服务器缓存连续多媒体对象的主题，挑战在于连续的数据必须以连续的顺序流传输到客户端。为了支持流媒体的实时需求，网络缓存需要为连续数据对象的每个请求预留带宽和空间，研究了平衡这两种资源的算法。