Randomized oblivious integral routing for minimizing power cost

doi:10.1016/j.tcs.2015.07.007

	Randomized oblivious integral routing for minimizing power cost
	Shi, Yangguang 1,2; Zhang, Fa 3; Wu, Jie 4; Liu, Zhiyong 1,5
	2015-11-23
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	607 页码:221-246
摘要	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.
关键词	Oblivious routing Integral routing Randomized algorithm Competitive ratio Energy efficiency
DOI	10.1016/j.tcs.2015.07.007
收录类别	SCI
语种	英语
资助项目	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类目	Computer Science, Theory & Methods
WOS记录号	WOS:000366767500009
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：5[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/9038
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Zhiyong
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing Key Lab Mobile Comp & Pervas Device, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Beijing, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, Beijing, Peoples R China 4.Temple Univ, Coll Sci & Technol, Dept Comp & Informat Sci, Philadelphia, PA 19122 USA 5.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, 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.