現今許多要求即時性資料的應用，像是交通管控系統、監視系統及醫療照護系統，都須要處理連續且龐大的資料串流。由於資料串流量過於龐大而資源卻有限，所以這類系統被設計為要能夠在過載(overload)的情形下，正常執行程式。為了滿足此要求，學者專家們提出了各種卸載(load shedding)方法。然而現存的卸載技術皆不適用於具有嚴格時效性要求的資料串流，原因是他們所採取的捨棄策略會違反應用程式的時限，而造成無法控制的後果。基於以上的理由，在本文中，利用探查資料串流語義和應用(m, k)模型，我們提出一套安全負荷卸載方法(SOSA)。SOSA將資料串流的處理分成兩種不同的模式，在其中一種模式中，我們可將負載量適當地減少而將省下的資源利用於其他較重要的部份。而為了使效用最大化，我們以SOSA為基礎，另外提出一個新的(m, k)排程演算法名為SOSA-DBP，來配合SOSA使用。透過機率模型分析和模擬實驗結果，我們可將本文中所提出的方法和現存的演算法作一比較。

Many real-time applications, such as traffic control systems, surveillance sys-tems and health monitoring systems, need to operate on continuous unbounded streams of data. Due to unbounded amount of stream and limited processing re-sources, systems designed to run such applications must be prepared to operate un-der overloaded conditions. To relief system burden, many load shedding methods have been proposed. Existing load shedding techniques are not suitable for proc-essing data streams with stringent timing constraints because their tuple dropping policies may violate application deadlines in an uncontrolled way. For the reason given above, we propose a Safe load Shedding Approach (SOSA) by exploiting the data semantic of sensor streams and application of the (m, k) deadline model. 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 demon-strate the usefulness of SOSA, a novel (m, k) scheduling algorithm called SOSA-DBP will be introduced based on the philosophy of SOSA. We present probabilistic analysis and experimental that characterizes the effectiveness of our approach compared with the existing algorithms.

[BBDMT04] B. Babcock, S. Babu, M. Datar, R. Motwani, and D. Thomas. Operator scheduling in data stream systems. In VLDB, 2004.
[BBDMW02] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In PODS, 2002.
[BBL01] G. Bernat, A. Burns, and A. Llamosi. Weakly hard real-time systems. In IEEE, 2001.
[BDM04] B. Babcock, M. Datar, and R. Motwani. Load shedding for aggregation queries over data streams. In ICDE, 2004.
[CCDF+03] S. Chandrasekaran, O. Cooper, A. Deshpande, M. Franklin, J. Hellerstein, W. Hong, S. Krishnamurthy, S. R. Madden, V. Raman, F. Reiss, and M. A. Shah. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR, 2003.
[CFPR00] C. Cortes, K. Fisher, D. Pregibon, and A. Rogers. Hancock: a language for extracting signatures from data streams. In SIGKDD, 2000.
[GWYL07] B. Gedik, K. L. Wu, P. S. Yu, and L. Liu. A load shedding framework and optimizations for m-way windowed stream joins. In ICDE, 2007.
[HR95] M. Hamdaoui and P. Ramanathan. A dynamic priority as-signment technique for streams with (m, k)-firm deadlines. In IEEE, 1995.
[HR99] M. Hamdaoui and P. Ramanathan. Overload management in real-time control applications using (m, k)-firm guarantee. In IEEE, 1999.
[OJW03] C. Olston, J. Jiang, and J. Widom. Adaptive filters for con-tinuous queries over distributed data streams. In SIGMOD, 2003.
[S96] M. Sullivan. Tribeca: A stream database manager for network traffic analysis. In VLDB, 1996.
[SAJBGP96] I. Stoica, H. Abdel-Wahab, K. Jeffay, S. Baruah, J. Gehrke, and C. Plaxton. A proportional share resource allocation algo-rithm for real-time, time-shared systems. In IEEE, 1996.
[SBL04] S. Schmidt, H. Berthold, and W. Lehner. Qstream: Determi-nistic querying of data streams. In VLDB, 2004.
[SCZ05] M. Stonebraker, U. Cetintemel, and S. B. Zdonik. The 8 re-quirements of real-time stream processing. In SIGMOD, 2005.
[SLSL05] S. Schmidt, T. Legler, D. Schaller, and W. Lehner. Real-time scheduling for data stream management systems. In ECRTS, 2005.
[TCZCS03] N. Tatbul, U. Cetintemel, S. Zdonik, M. Chemiack, M. Stone-braker. Load shedding in a data stream manager. In VLDB, 2003.
[THXPL05] Y. C. Tu, M. Hefeeda, Y. Xia, S. Prabhakar, and S. Liu. Con-trol-based quality adaptation in data stream management sys-tems. In DEXA, 2005.
[TLPY06] Y. C. Tu, S. Liu, S. Prabhakar, and B. Yao. Load shedding in stream databases: A control-based approach. In VLDB, 2006.
[TZ06] N. Tatbul, S. Zdonik. Window-aware load shedding for ag-gregation queries over data stream. In VLDB, 2006.
[WPSS06] Y. Wei, V. Prasad, S. H. Son, and J. A. Stankovic. Prediction-based qos management for real-time data streams. In RTSS, 2006.