# 講稿

## 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 的機率。

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