Towards load shedding and scheduling schemes for data streams that maintain quality and timing requirements of query results

Guo Qin Ning, Hongya Wang, Lih-Chyun Shu, Guang Rew Yeh

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Real-time stream processing is essential for many real-life stream-based applications. Systems designed to run such applications must be prepared to operate under overloaded conditions. In this paper, the load shedding problem is studied for an important class of real-time data stream monitoring applications. In particular, we adopt the (Formula presented.) deadline model, instead of the commonly used random dropping policy, to capture the QoS requirements of such applications. Based on this model, we propose a Safe lOad Shedding Approach (SOSA) that aims to reduce the workload imposed on the system while at the same time preserve system timing constraints by exploiting data stream semantics. SOSA categorizes stream processing into two different modes and allows one to place provably lighter loads on streams that operate in one particular mode. To demonstrate the usefulness of SOSA, we introduce a concrete (Formula presented.) scheduling algorithm called SOSA-DBP by combining SOSA with DBP, a well-known (Formula presented.) scheduling algorithm. Probabilistic analysis and experimental results show that SOSA-DBP has significant performance gain over DBP.

Original languageEnglish
Pages (from-to)1961-1976
Number of pages16
JournalSoft Computing
Volume20
Issue number5
DOIs
Publication statusPublished - 2016 May 1

Fingerprint

Data Streams
Timing
Scheduling
Query
Requirements
Scheduling algorithms
Stream Processing
Processing
Scheduling Algorithm
Quality of service
Semantics
Concretes
Real-time
Probabilistic Analysis
Monitoring
Deadline
Workload
Experimental Results
Model
Demonstrate

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Geometry and Topology

Cite this

@article{7db6fe616cc74da1b9b309e68da1ccef,
title = "Towards load shedding and scheduling schemes for data streams that maintain quality and timing requirements of query results",
abstract = "Real-time stream processing is essential for many real-life stream-based applications. Systems designed to run such applications must be prepared to operate under overloaded conditions. In this paper, the load shedding problem is studied for an important class of real-time data stream monitoring applications. In particular, we adopt the (Formula presented.) deadline model, instead of the commonly used random dropping policy, to capture the QoS requirements of such applications. Based on this model, we propose a Safe lOad Shedding Approach (SOSA) that aims to reduce the workload imposed on the system while at the same time preserve system timing constraints by exploiting data stream semantics. SOSA categorizes stream processing into two different modes and allows one to place provably lighter loads on streams that operate in one particular mode. To demonstrate the usefulness of SOSA, we introduce a concrete (Formula presented.) scheduling algorithm called SOSA-DBP by combining SOSA with DBP, a well-known (Formula presented.) scheduling algorithm. Probabilistic analysis and experimental results show that SOSA-DBP has significant performance gain over DBP.",
author = "Ning, {Guo Qin} and Hongya Wang and Lih-Chyun Shu and Yeh, {Guang Rew}",
year = "2016",
month = "5",
day = "1",
doi = "10.1007/s00500-015-1617-5",
language = "English",
volume = "20",
pages = "1961--1976",
journal = "Soft Computing",
issn = "1432-7643",
publisher = "Springer Verlag",
number = "5",

}

Towards load shedding and scheduling schemes for data streams that maintain quality and timing requirements of query results. / Ning, Guo Qin; Wang, Hongya; Shu, Lih-Chyun; Yeh, Guang Rew.

In: Soft Computing, Vol. 20, No. 5, 01.05.2016, p. 1961-1976.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Towards load shedding and scheduling schemes for data streams that maintain quality and timing requirements of query results

AU - Ning, Guo Qin

AU - Wang, Hongya

AU - Shu, Lih-Chyun

AU - Yeh, Guang Rew

PY - 2016/5/1

Y1 - 2016/5/1

N2 - Real-time stream processing is essential for many real-life stream-based applications. Systems designed to run such applications must be prepared to operate under overloaded conditions. In this paper, the load shedding problem is studied for an important class of real-time data stream monitoring applications. In particular, we adopt the (Formula presented.) deadline model, instead of the commonly used random dropping policy, to capture the QoS requirements of such applications. Based on this model, we propose a Safe lOad Shedding Approach (SOSA) that aims to reduce the workload imposed on the system while at the same time preserve system timing constraints by exploiting data stream semantics. SOSA categorizes stream processing into two different modes and allows one to place provably lighter loads on streams that operate in one particular mode. To demonstrate the usefulness of SOSA, we introduce a concrete (Formula presented.) scheduling algorithm called SOSA-DBP by combining SOSA with DBP, a well-known (Formula presented.) scheduling algorithm. Probabilistic analysis and experimental results show that SOSA-DBP has significant performance gain over DBP.

AB - Real-time stream processing is essential for many real-life stream-based applications. Systems designed to run such applications must be prepared to operate under overloaded conditions. In this paper, the load shedding problem is studied for an important class of real-time data stream monitoring applications. In particular, we adopt the (Formula presented.) deadline model, instead of the commonly used random dropping policy, to capture the QoS requirements of such applications. Based on this model, we propose a Safe lOad Shedding Approach (SOSA) that aims to reduce the workload imposed on the system while at the same time preserve system timing constraints by exploiting data stream semantics. SOSA categorizes stream processing into two different modes and allows one to place provably lighter loads on streams that operate in one particular mode. To demonstrate the usefulness of SOSA, we introduce a concrete (Formula presented.) scheduling algorithm called SOSA-DBP by combining SOSA with DBP, a well-known (Formula presented.) scheduling algorithm. Probabilistic analysis and experimental results show that SOSA-DBP has significant performance gain over DBP.

UR - http://www.scopus.com/inward/record.url?scp=84923370673&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84923370673&partnerID=8YFLogxK

U2 - 10.1007/s00500-015-1617-5

DO - 10.1007/s00500-015-1617-5

M3 - Article

AN - SCOPUS:84923370673

VL - 20

SP - 1961

EP - 1976

JO - Soft Computing

JF - Soft Computing

SN - 1432-7643

IS - 5

ER -