We present an economical and fault-tolerant load balancing strategy (EFTLBS) based on an operator replication mechanism and a load shedding method, that fully utilizes the network resources to realize continuous and highly-available data stream processing without dynamic operator migration over wide area networks. In this paper, we first design an economical operator distribution (EOD) plan based on a bin-packing model under the constraints of each stream bandwidth as well as each server's CPU capacity. Next, we devise super-operator (SO) that load balances multi-degree operator replicas. Moreover, for improving the fault-tolerance of the system, we color the SOs based on a coloring bin-packing (CBP) model that assigns peer operator replicas to different servers. To minimize the effects of input rate bursts upon the system, we take advantage of a load shedding method while keeping the QoS guarantees made by the system based on the SO scheme and the CBP model. Finally, we substantiate the utility of our work through experiments on ns-3.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Fuyuan XIAO, Teruaki KITASUKA, Masayoshi ARITSUGI, "Economical and Fault-Tolerant Load Balancing in Distributed Stream Processing Systems" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 4, pp. 1062-1073, April 2012, doi: 10.1587/transinf.E95.D.1062.
Abstract: We present an economical and fault-tolerant load balancing strategy (EFTLBS) based on an operator replication mechanism and a load shedding method, that fully utilizes the network resources to realize continuous and highly-available data stream processing without dynamic operator migration over wide area networks. In this paper, we first design an economical operator distribution (EOD) plan based on a bin-packing model under the constraints of each stream bandwidth as well as each server's CPU capacity. Next, we devise super-operator (SO) that load balances multi-degree operator replicas. Moreover, for improving the fault-tolerance of the system, we color the SOs based on a coloring bin-packing (CBP) model that assigns peer operator replicas to different servers. To minimize the effects of input rate bursts upon the system, we take advantage of a load shedding method while keeping the QoS guarantees made by the system based on the SO scheme and the CBP model. Finally, we substantiate the utility of our work through experiments on ns-3.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.1062/_p
Copy
@ARTICLE{e95-d_4_1062,
author={Fuyuan XIAO, Teruaki KITASUKA, Masayoshi ARITSUGI, },
journal={IEICE TRANSACTIONS on Information},
title={Economical and Fault-Tolerant Load Balancing in Distributed Stream Processing Systems},
year={2012},
volume={E95-D},
number={4},
pages={1062-1073},
abstract={We present an economical and fault-tolerant load balancing strategy (EFTLBS) based on an operator replication mechanism and a load shedding method, that fully utilizes the network resources to realize continuous and highly-available data stream processing without dynamic operator migration over wide area networks. In this paper, we first design an economical operator distribution (EOD) plan based on a bin-packing model under the constraints of each stream bandwidth as well as each server's CPU capacity. Next, we devise super-operator (SO) that load balances multi-degree operator replicas. Moreover, for improving the fault-tolerance of the system, we color the SOs based on a coloring bin-packing (CBP) model that assigns peer operator replicas to different servers. To minimize the effects of input rate bursts upon the system, we take advantage of a load shedding method while keeping the QoS guarantees made by the system based on the SO scheme and the CBP model. Finally, we substantiate the utility of our work through experiments on ns-3.},
keywords={},
doi={10.1587/transinf.E95.D.1062},
ISSN={1745-1361},
month={April},}
Copy
TY - JOUR
TI - Economical and Fault-Tolerant Load Balancing in Distributed Stream Processing Systems
T2 - IEICE TRANSACTIONS on Information
SP - 1062
EP - 1073
AU - Fuyuan XIAO
AU - Teruaki KITASUKA
AU - Masayoshi ARITSUGI
PY - 2012
DO - 10.1587/transinf.E95.D.1062
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2012
AB - We present an economical and fault-tolerant load balancing strategy (EFTLBS) based on an operator replication mechanism and a load shedding method, that fully utilizes the network resources to realize continuous and highly-available data stream processing without dynamic operator migration over wide area networks. In this paper, we first design an economical operator distribution (EOD) plan based on a bin-packing model under the constraints of each stream bandwidth as well as each server's CPU capacity. Next, we devise super-operator (SO) that load balances multi-degree operator replicas. Moreover, for improving the fault-tolerance of the system, we color the SOs based on a coloring bin-packing (CBP) model that assigns peer operator replicas to different servers. To minimize the effects of input rate bursts upon the system, we take advantage of a load shedding method while keeping the QoS guarantees made by the system based on the SO scheme and the CBP model. Finally, we substantiate the utility of our work through experiments on ns-3.
ER -