講稿

3

傳統上我們用 maximum allowable loss percentage 來表達 deadline miss 的容忍度，例如在影片串流允許 10% 的 maximum allowable loss percentage。我們對 maximum allowable loss percentage 的期待是這些發生 deadline miss 的事件是均勻分散的，但是我們僅用整體的 loss percentage 去評估往往不符合我們的期待。拿影片串流為例，如果連續好幾幀都丟失，就算整部影片的 loss percentage 為 10%，視覺上就會發現影片掉幀。為了解決上述的問題，我們可以用另一個方法來表達容忍度：在任意 k 個連續 frame 的 window 中至少有 m 個 frame meet deadline，即 (m, k)-firm deadline。

4

在 (m, k)-firm deadlines 的 stream 中，如果在任意 k 個連續 customer 少於 m 個 customer meet deadline，則稱此 stream 遇到 dynamic failure。customer 與 stream 的定義稍後會講解。

本論文想解決的問題就是將 customer schedule 在單個 server 上，以降低平均 dynamic failure 的機率。

5

過去已經有很多研究提出一個可以達到 maximum allowable loss percentage 的 model，像是以下 paper，然而，這些研究著重的點是在整體的 loss percentage，但不會去在意連續 customers miss 的問題。

6

有另一些研究會專門針對類的 (m, k)-firm deadline，提出 imprecise computation model。在這一類的 model 中，會將 customers 分成 mandatory 和 optional 兩類。其中， optional customers 採用的是 best-effort basis，也就是當系統有餘裕時才會 service 這類的 customers。而這 model 應用在 (m, k)-firm deadline 就是將一個 window 內 k 個 customers 分配只少 m 個 mandatory customers。這種 model 的方式雖然可以減少 dynamic failure，但是會讓整體的 deadline miss rate 更高。

7

考慮一個 real-time customer stream，其中 customer 可以是 task、message 等在 real time application 中的 schedulable entity。如果 customer 可以在 deadline 前被 fully serviced，則稱這個 customer meet the deadline。反之則為 miss the deadline。

8

9

而我們可以 generally 得用 (m, k)-firm deadline 來表示各個 case。如果這個 stream 的每個 customer 都必須 meet the deadline，可以用 (1, 1)-firm deadlines 表示。如果這個系統要求不能有連續兩個 customer miss the deadline，則是 (1, 2)-firm deadlines。而 (4, 6)-firm deadline 隱含的是不會有三個以上連續的 customers miss the deadline，不僅如此，還確保在 6 個 customers 的 window size 裡至少 4 個 customer meet the deadline。

10

(m, k)-firm 也隱含了一個概念，就是這個 stream 有 (k - m)/k maximum allowable loss rate。(4, 5)-firm 代表 20% 的 maximum allowable loss rate。(8, 10)-firm 比 (4, 5)-firm 來得不嚴格一點，依然表示 20% 的 maximum allowable loss rate。

我們考慮到一個由 N 個 stream 組的系統，每個 stream 編號從 R1 到 RN。Stream Rj 有 (mj, kj)-firm deadline。而本篇論文所要討論的就是一個 server 或是說一個 system，我們要如何去 schedule 這些 customers 來降低 average probability of dynamic failure。

11

也解決這個議題，最直觀的方式就是去降低各個 customer miss the deadline 的機率。以下介紹的是過往的 scheduling policies。

每個 stream 都有一個 FIFO queue，確保一個 stream 的各個 customer 的順序是依照它的 arrival order。另外會有一個 service queue 從這些 stream queue 的端點中選擇 customer 執行，如下圖

12

這邊舉兩種常見的例子說明 service queue 挑選的 policy。第一種是 FIFO policy，如果一個 stream 的最前面的 customer 它的 arrival 時間最早，那我們就將它拉進 service queue 裡。另一種方式是 EDF policy，挑選的方式是根據各個 customer 的 deadline，deadline 最早的會最先被挑選。

13

而本篇研究提出的方式也可以套用這種 service queue model，我們會挑選各個 stream 中 priority 最高的 customer 放進 service queue，若 priority 相同，因為過往研究發現 EDF policy 會有更好的表現，會採用 EDF policy。

14

而這章節會詳細討論論文提出的 DBP 的策略。在 DBP policy 裡，我們會根據各個 stream miss 或是 meet 的歷史紀錄來 assign 給 customer priority。

對於每個 stream，系統會有一個 state 用來記錄歷史。每個 customer 有可能會被 service 或是被 drop 掉，而一個 serviced customer 有可能 miss 或是 meet the deadline。而這裡所有被 dropped 的 customer 也被視為是 miss the deadline。

15

這邊介紹一些符號定義。\(\delta_i^j\) 用來表示 stream Rj 中第 i 個 customer 的 status， i 大於等於 1。

我們用一個 kj tuple 表示一個給定時間點 stream Rj 的 state。其中最右邊的代表 arrivel time 最早。

如果 Rj 這個 stream 的 state 少於 mj 個 meet，則稱這個 state 是 failing state。

我們分別用 M 和 m 或是 1 和 0 來表示 customer 的 status 是 meet 還是 miss the deadline。
舉例來說，這個 stream 最近三次 customer 的 status 分別為 miss、meet、meet。

16

我們的目標是要防止 stream 進入 failing state。

如果 stream 越接近 failing state，我們就給他越高的 priority。

在本篇論文提出的方法中，是用這個 stream 在 current state 時，距離 failing state 還需多少個連續的 miss 來決定其 priority value，當一個 stream priority value 越低，代表這個 stream 距離 failing state 越近，priority 越高。

17

我們可以將 DBP scheme 畫成 FSM。以下是 (2, 3)-firm deadlines 的圖。圖中的圓圈代表各個 state，而灰斜線的 state 代表 failing state，我們可以看到 failing state 中，3 個連續的 status 中有兩個以上的 miss。圖中的箭頭則表示這個 state 根據下個 customer 是 miss 或是 meet 會到下個 state。

各個 state 的 priority value 我用紅字標示在 state 的右上方，可以看到 priority value 為 0 的 state 代表 failing state，需要給他更高的 priority，priority value 為 1 的 state 代表再一個 miss 就會進入 failing state，priority value 為 2 的 state 則是連續兩個 miss 才會進入 failing state

18

我們採用 DBP 這個 scheme 在一個有不同 deadline firm 的 stream 的系統中也有好處。比方說有一個系統有兩個 stream，分別為 (3, 5)-firm deadlines 和 (9, 10)-firm deadlines

第一個 stream 在連續 5 個 customers 中可以容忍 2 misses，40% loss rate。第二個 stream 在連續 10 個 customers 種只可以容忍 1 miss，10% loss rate。在傳統的 single priority scheme 中，不會考慮到不同 streams 的 timing requirements，導致整個系統，也就是兩個 streams 有一樣的 loss rate。但要注意的是，DBP scheme 跟 static 得給 deadline requirement 高的 stream 比較高的優先度也不一樣。在後者的方式中，因為 (9, 10)-firm deadlines 的 requirement 更高，會固定給其比較高的 priority。而在 DBP scheme，是看跟 failing state 的距離決定 priority，因此，若 (3, 5)-firm 距離 failing state 更近，會拿到比 (9, 10)-firm 更高的 priority。

19

而這個方法可以用硬體或軟體來實作，我們可以將 stream Rj 的 state 存放在 k-j bit 的 register 中，用 0 和 1 分別代表 miss 和 meet the deadline。當下一個 customer 被 serviced 時，我們可以根據該 customer 是 miss 或是 meet 分別 shift in 0 或是 1。

20

而這裡我們定義 lj(n, s)，用來表示 register 中，從右邊數來第 n 個 meet 的位置，s 則是代表當前時間點 stream Rj 的 state。若 register 中少於 n 個 1，則我們將 lj(n, s) 設為 kj + 1。

這邊舉一個例子作說明，

21

我們透過模擬器評估 DBP 與 single priority (簡稱為 SP) 的 dynamic failure 機率，在 DBP 與 SP 中，如果 customer 的 priority 都相同則採用 earliest-deadline-first 來 schedule。

使用兩種模式來生成 customer，分別為 Poisson 與 bursty。在 Poisson stream 中，customer 的 inter-arrival time 為指數分布；bursty stream 則分為 ON 與 OFF 兩種狀態，狀態為 ON 時會定期產生 customer，OFF 時則不產生 customer，ON 與 OFF 的時長為指數分布。bursty 模式常常被用來模擬人談話的聲音，人在交談時為 ON，安靜時為 OFF。

22

在這個部分有 A 到 F 六個實驗，現在這張圖是實驗 A 的圖表。首先在 A、B 實驗中，我們考慮系統中所有 stream 有一樣的 (m,k)-firm，我們也假定只有 meet deadline 的 customer 能夠獲得 service。

Fig. 3 展示了 (1, 2)-firm 和 (3, 4)-firm 在兩個一樣的系統中的 dynamic failure 機率。系統中有 5 個 Poisson stream、所有 customer 的 service time 固定不變且期限為 service time 的 5 倍、customer 的 interarrival time 為指數分布，透過調整 interarrival time 來讓系統的 average load 介於 0.2 至 0.9。

Fig 3a 和 3b 唯一的差異在於對 miss deadline 的容忍度，3a 允許任 2 個連續 customer 中 1 個 miss deadline，而 3b 比較嚴格，只允許任 4 個中 1 個 miss deadline，也因此 3b 的 dynamic failure 機率比較高，在 3a 中 DBP 至少降低了 60% 的 dynamic failure，在 3b 中至少降低 40%。

23

Fig. 4 跟 Fig 3. 類似，展示了 (1, 2)-firm 和 (3-4)-firm 在兩個一樣的系統中的 dynamic failure 機率。系統中有 5 個 bursty stream，\(ON\) 的平均時間為 50 微秒、\(OFF\) 的平均時間為 100 微秒，因此可以得到 ON 的狀態下 load 為 average load 的三倍。在 ON 狀態下，每個 stream 每 5 微秒會生成一個 customer、每個 customer 的 deadline 是 10 微秒、透過拉長 service time 來把 average load 調整在 0.2 和 0.9 之間。同樣的，實驗結果表明 DBP 較 SP 優。

在 4a DBP 的 dynamic failure 機率大致少了 95%、在 4b 減少幅度則較小。

比較實驗 A 與實驗 B，也可以發現 bursty stream 的 dynamic failure 率要比 Poisson stream 高，這是因為 bursty 在此實驗中尖峰時段 load 接近 average load 的 3 倍)，尖峰時段 load 時常大於 1，意味著系統常常 overload，所以在相同的 average load 下，bursty 的 dynamic failure 機率比較高。

24

在 A、B 實驗中，我們都假設系統已知每個 customer 的 service time，所以在 service 前把必定 miss deadline 的 customer drop 掉，然而不是每一種系統都能預先知道 service time，在實驗 C 使用這種必須 serve 所有 customer 的系統，不允許 drop 掉。

Fig 5. 展示了基於實驗 A，也就是 Poisson stream 的系統，但是不允許 drop customer。因為這次實驗中，實質上獲得 service 的 customer 更多了， dynamic failure 機率也提高，雖然 DBP 相較 SP 減少超過 80% 的 dynamic failure 機率，但機率的數值仍然比 Fig 3. 高。

25

在前面 A、B、C 實驗中，每個 stream 的 (m,k)-firm 都相同。本實驗將每個 stream 設為不同的 (m, k)-firm。分別為 (9, 10)-firm、(3, 4)-firm、(1, 2)-firm、(1, 3)-firm、(1, 4)-firm，其餘條件則同實驗 A。

在 Fig 6. 中，我們單獨挑出 average load 為 0.5、0.7、0.9 觀察，分別對應 6a、6b、6c。本次實驗除了 SP、DBP 外，還測試了另一種 policy 叫做 fixed priority (FP)，在 FP 方案中，mk-firm 越緊迫的 stream 會被分配越高的優先度，也就是 (9, 10)-firm stream 的 customer 會被固定為最高 priority，最優先被執行，其次 (3, 4)-firm 依此類推，(1, 4)-firm stream 的 customer 為最低 priority。在 Fig 6. 中黑色是 SP、灰色是 FP、白色是 DBP。

觀察 Fig 6.，在 SP 中，mk-firm 越緊迫則 dynamic failure 率越高；相反的，在 FP 中，mk-firm 越緊迫則 dynamic faliure 則通常偏低。這表明了 (m, k)-firm deadline 的嚴格程度與 priority 的高低是影響 dynamic failure 的兩個因素，dynamic failure 的高低取決於這兩者的平衡。

最後觀察 DBP 擁有最低的 dynamic faliure 率，而且在緊迫的 (m, k)-firm 下表現遠超 SP，但是在 average load 偏低以及 (m, k)-firm 較不嚴格的 mk-firm stream 表現較差。另一方面，DBP 在 (m, k)-firm 較不嚴格的 stream 表現較 FP 好，反之 FP 則表現的比 DBP 好。最後綜觀 5a 5b 5c，DBP 在各種不同的 (m, k)-firm deadline 下，是較為平衡的方案。

26

實驗 E 是將實驗 C 中的 No-drop policy 的實驗結果與 impresice model 進行比較，我們前面有介紹過 Imprecise model 的定義，所有 customer 被區分為 mandatory 與 optional。mandatory customer 必須獲得 service，optional customer 則是拿來優化 mandotary customer，在整個系統 load 過高時可以被 drop。

在本實驗中，將 (m, k)-firm 結合 imprecise model，令 stream 中，連續 k 個 customer 裡要至少有 m 個 mandotary customer。本次實驗的系統基於 Fig 5b 的 (3, 4)-firm stream 組成的系統，並將 customer 掛上 mandotary 和 optional 的標籤。接著我們定義一個臨界點 \(T\)，當在 service queue 中等候的 customer 數量超過 \(T\) 時，之後到達的 optional customer 會直接被丟掉。當 \(T = 0\) 所有 optional customer 都會被 drop；當 \(T = \infty\) 則所有 optional customer 都會獲得 service，也就是排程邏輯等同於 SP。

在 Fig 7. 中，x 軸為臨界點 \(T\) 的值，介於 0 到 8，左圖 y 軸為 dynamic failure 機率，右圖 y 軸為 customer miss deadline 的機率，Fig 7. 只抓 average load 為 0.3、0.6、0.8 來觀察。

透過觀察，只有 IMPRECISE 會與臨界點 \(T\) 有關，而 SP 與 DBP 並不會使用到 \(T\)，因此我們可以看到不管 \(T\) 的值為何，SP 與 DBP 的 dynamic failure 機率都不變，為兩條水平線。imprecise model 在合適的臨界點 \(T\) 下，dynamic failure 機率與 DBP 差不多低，例如在 average load 較高且 \(T=0\) 時，左圖 dynamic failure 機率低。然而隨之而來的是右圖 customer miss deadline 機率大幅提升，因為當 \(T=0\) 時，所有 optional customer 都會被 drop 掉，而因為系統中所有 stream 都是 (3, 4)-firm，所以每四個 customer 必定會丟掉 1 個，導致 IMPRESICE model 中 customer miss deadline 的機率大於等於 0.25。反觀 DBP 則可以在不拉高 miss deadline 機率的情況下保持較低的 dynamic failure 機率。

imprecise model 還有一個問題，臨界點 \(T\) 的值需要依據 average load 來調整，我們可以看到在 load 為 0.3 時，\(T=0\) 反而對 imprecise model 造成很差的效果。綜觀以上，DBP 的效果優於 IMPRECISE model。

27

從前面的實驗，我們已經確定 DBP 相較於其他 policy，像 SP、FP、Impresice model 有較低的 dynamic failure 機率。在這個實驗 F 中則是研究 stream 數量對 DBP 的影響，固定 stream 的 mk-firm，我們逐次增加 stream 的數量，並且調整 customer 的 arrival rate 讓整個系統的 average load 保持相同。

在 Fig 8. 中，系統的 average load 為 0.7、所有 stream 都是 Poisson stream，stream 是 (1, 2)-firm deadline。8a 中所有 customer 都會獲得 service (也就是實驗 C 中的 No-drop policy)、8b 中只有 meet deadline 的 customer 會得到 service。

綜觀 8a 與 8b，當 stream 數量為 1，SP 與 DBP 的 dynamic failure 機率是一樣的，隨著 stream 數量越多，DBP 的 dynamic failure 機率以顯著的幅度下降，在 8a 中，3 個 stream 的狀況下 DBP 較 SP 少了 70% 的 dynamic failure 機率。

28

DBP 中可供分配的優限度是基於 (m, k)-firm，當 stream \(R_j\) 為 \((m_j, k_j)\rm{-firm}\)，則總共有 0,1,…到 \(k_j-m_j+1\)，總共 \(k_j-m_j+2\) 個不同的 priority level。因此，在多個不同 (m, k)-firm stream 的系統，必須支援所有 Stream 中，擁有最多 Priority level 的，如中間的公式：

\(P=\rm{max}\{k_j-m_j+2:j=1,2,...,N\}\)

但是現實中，一個系統通常會限制 priority level 的數量，例如 linux 系統中，priority 的值介於 -20 到 +19。我們將系統最大的 priority 記為 \(P_{max}\)，在這個章節我們將討論 \(P_{max}<P\) 的狀況。

29

簡單來說，當系統的當一個 stream 與 failing state 的距離大於 \(P_{max}-1\)，就還是分配 \(P_{max}-1\) 給它的 customer。我們用以下式子表達 stream \(R_j\) 的第 \(i+1\) 個 customer 將會分配到的 priority：

\(\mbox{priority }^j_{i+1}=\rm{min}\{k_j-l_j(m_j,s)+1,P_{max}-1\}\)

其中 s 和 \(l_j\) 的定義我們在前面提到過，s 是 \(R_j\) 目前的 state ， \(l_j\) 是從右邊數來第 \(m_j\) 個 meet deadline 的 customer 的位置。

30

Fig 9. 系統中全為 (2,5)-firm deadline 的 Poisson stream，系統 average load 固定為 0.8。在理想情況下，\(P=5\) 且共有 0, 1, 2, 3, 4 五種 priority，但是我們透過調整 \(P_{max}\) 觀察不同 priority level 對 dynamic failure 機率的影響。9a 所有 customer 都會獲得 service (No-drop policy)；9b 只有期限內可以完成的 customer 可以獲得 service，其餘則被 drop 掉。

當 \(P_{max}=1\) 時，只有一種 priority，等同於 SP。觀察 Fig 9. 可以發現其實 \(P_{max}=3\) 時，DBP 的效果就足夠好了，再提高 Priority level 降低 dynamic failure 的機率有限。當 \(P_{max}=3\) 時，failing state stream 的 customer 會被分配 priority 0、近期只有 1 個 customer miss deadline 的 stream priority 為 1、其餘 priority 為 2。

31

Fig 10. 則展示 \(P_{max}\) 對 hetrogeneous system 的影響，五個 stream 分別為 (9, 10)-firm、(3, 4)-firm、(1, 2)-firm、(1, 3)-firm、(1, 4)-firm，其餘條件與前一張投影片的實驗相同。這裡我們一樣可以發現當 \(P_{max}=3\) 時，DBP 就已經展現可觀的效果了。

32

最後講本篇論文的結論。本論文介紹了 (m,k)-firm deadline model ，它概括了 hard 和 soft deadline 的概念，在 mk-firm model 裡每個 stream 有兩個參數 m 和 k，如果 k 個連續 customer 中少於 m 個 meet deadline，就會發生 dynamic failure，相較於傳統上常用的 maxium allowable loss rate，mk-firm 更精確地表達 real-time application 對於 customer meet deadline 的要求。

接著本論文提出基於 Distance-Based Priority (DBP) policy，較接近 failing state 的 stream 會被分配更高的 priority，以提高它的 customer meet deadline 的機會。本方法與 single priority、fixed priority 與 imprecise computation model 進行比較，實驗結果表明，我們所提出的方法大大降低了 dynamic failure 的機率，同時不會大幅影響 customer miss deadline 的機率。

我們的報告到此結束，謝謝大家。