中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Randomized oblivious integral routing for minimizing power cost

文献类型：期刊论文

作者Shi, Yangguang1,5; Zhang, Fa2; Wu, Jie3; Liu, Zhiyong4,5
刊名THEORETICAL COMPUTER SCIENCE
出版日期2015-11-23
卷号607页码:221-246
关键词Oblivious routing Integral routing Randomized algorithm Competitive ratio Energy efficiency
ISSN号0304-3975
DOI10.1016/j.tcs.2015.07.007
英文摘要Given an undirected network G(V, E) and a set of traffic requests R, the minimum power-cost routing problem requires that each R-k is an element of R, be routed along a single path to minimize Sigma(e is an element of E)(l(e))(alpha), where l(e) is the traffic load on edge e and alpha is a constant greater than 1. Typically, alpha is an element of (1,3]. This problem is important in optimizing the energy consumption of networks. To address this problem, we propose a randomized oblivious routing algorithm. An oblivious routing algorithm makes decisions independently of the current traffic in the network. This feature enables the efficient implementation of our algorithm in a distributed manner, which is desirable for large-scale high-capacity networks. An important feature of our work is that our algorithm can satisfy the integral constraint, which requires that each traffic request Rk should follow a single path. We prove that, given this constraint, no randomized oblivious routing algorithm can guarantee a competitive ratio bounded by o(vertical bar E vertical bar(alpha-1/alpha+1)). By contrast, our approach provides a competitive ratio of O(vertical bar E vertical bar(alpha-1/alpha+1) log(2 alpha/alpha+1) vertical bar V vertical bar . log(alpha-1) D), where D is the maximum demand of traffic requests. Furthermore, our results also hold for a more general case where the objective is to minimize Sigma(e)(l(e))(p), where p >= I is an arbitrary unknown parameter with a given upper bound alpha >1. The theoretical results established in proving these bounds can be further generalized to a framework of designing and analyzing oblivious integral routing algorithms, which is significant for research on minimizing Sigma(e)(l(e))(alpha) in specific scenarios with simplified problem settings. For instance, we prove that this framework can generate an oblivious integral routing algorithm whose competitive ratio can be bounded by O(log(alpha) vertical bar V vertical bar . log(alpha-1) D and O(log(3 alpha) vertical bar V vertical bar . log(alpha-1) D) on expanders and hypercubes, respectively. (C) 2015 Elsevier B.V. All rights reserved.
资助项目China National Natural Science Foundation (NSFC) ; Hong Kong RGC Joint Project[61161160566] ; NSFC International Coordination Project[61020106002] ; NSFC Project for Innovation Groups[61221062] ; NSFC Project[61202059] ; National Science Foundation (NSF) grants Computer and Network Systems (CNS)[149860] ; National Science Foundation (NSF) grants Computer and Network Systems (CNS)[CNS 1461932] ; National Science Foundation (NSF) grants Computer and Network Systems (CNS)[CNS 1460971] ; National Science Foundation (NSF) grants Computer and Network Systems (CNS)[CNS 1439672]
WOS研究方向Computer Science
语种英语
WOS记录号WOS:000366767500009
出版者ELSEVIER SCIENCE BV
源URL[http://119.78.100.204/handle/2XEOYT63/9037]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Liu, Zhiyong
作者单位1.Univ Chinese Acad Sci, Beijing, Peoples R China
2.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, Beijing, Peoples R China
3.Temple Univ, Coll Sci & Technol, Dept Comp & Informat Sci, Philadelphia, PA 19122 USA
4.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing, Peoples R China
5.Chinese Acad Sci, Inst Comp Technol, Beijing Key Lab Mobile Comp & Pervas Device, Beijing, Peoples R China
推荐引用方式
GB/T 7714		 Shi, Yangguang,Zhang, Fa,Wu, Jie,et al. Randomized oblivious integral routing for minimizing power cost[J]. THEORETICAL COMPUTER SCIENCE,2015,607:221-246.
APA Shi, Yangguang,Zhang, Fa,Wu, Jie,&Liu, Zhiyong.(2015).Randomized oblivious integral routing for minimizing power cost.THEORETICAL COMPUTER SCIENCE,607,221-246.
MLA Shi, Yangguang,et al."Randomized oblivious integral routing for minimizing power cost".THEORETICAL COMPUTER SCIENCE 607(2015):221-246.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。