Load shedding and distributed resource control of stream processing networks

被引:8
作者
Feng, Hanhua
Liu, Zhen
Xia, Cathy H. [1 ]
Zhang, Li
机构
[1] IBM Corp, Thomas J Watson Res Ctr, Yorktown Hts, NY 10598 USA
[2] Columbia Univ, Dept Comp Sci, New York, NY 10027 USA
基金
美国国家科学基金会;
关键词
resource allocation; admission control; distributed control; utility maximization; stream processing network;
D O I
10.1016/j.peva.2007.06.023
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Recent advances in networking and information technology boost the development of new and advanced services offered over communication systems that integrate a widely heterogeneous mix of applications and computer devices. Without careful traffic control and resource management, the implied dramatic increase in the demand for networking resources and remote application services may lead to substantial degradation of the Quality of Service as experienced by the end users. In this paper, we consider the problem of joint admission control and dynamic resource allocation in a stream processing network so as to optimize the overall system utility. With a primal-dual-based optimization approach, we show that the resource allocation problem and the admission control problem can be decomposed. We then present a distributed algorithm which incorporates a push-and-pull-based admission control mechanism, and a pressure-based c mu rule for resource allocation. We show that the algorithm guarantees the stability of the network and converges to the optimal solution. Various numerical experiments are then presented to demonstrate the quality of the solution and the speed of convergence. (c) 2007 Published by Elsevier B.V.
引用
收藏
页码:1102 / 1120
页数:19
相关论文
共 28 条
[1]  
Abadi D. J., 2005, CIDR, V5, P277
[2]  
[Anonymous], 2006, VLDB
[3]  
[Anonymous], 2013, P 29 INT C VERY LARG
[4]  
[Anonymous], 2003, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data-SIGMOD'03
[5]  
Awerbuch B., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P459, DOI 10.1109/SFCS.1993.366841
[6]  
BABCOCK B, 2004, P ICDE C
[7]  
BAZARAAMS, 1977, LINEAR PROGRAMMING N
[8]  
BROBERGJA, 2006, P SIGMETRICS
[9]  
BUI L, 2006, P INFOCOM
[10]  
CHANDRASEKARAN S, 2004, P 30 VLDB C