[[alternative]]A scheduling algorithm to provide QoS in network streaming service using the least package drop ratio

碩士[[abstract]]現行常被使用於網路傳輸的排程演算法包含了傳送期限先到者優先（Early Deadline First：EDF）、先進先出（First In First Out：FIFO）這二種主流的排程演算法服務。這些的排程演算法在推演時均是以每筆資料都是"單一封包"當作基準在探討，傳統網路上即使遇到資料源為連續串流資料（連續封包）時還是以"不可分割"的方式去傳輸資料源為概念基礎。同時在丟棄封包的判斷上是以"剩餘未傳送的封包"中的"剩餘絕對單位量"去競爭來決定是否被丟棄。例如在例如混合光纖同軸電纜（Hybrid Fiber Coaxial；HFC）網路上支援服務品質（QoS），其必需提供有效率或針對性、目的性的優先權機制。因此本文中將探討在當傳輸資料時加入一筆（組）資料源為連續串流資料（連續封包）時的狀況，並針對最小丟失率優先提出新的排程演算法Reduce Loss Ratio（RLR）。 同時，也針對網路封包可以切割傳輸的環境，例如HFC網路，將"可分割"封包與依"比例"的方式判斷丟棄優先權的這兩個概念，導入新的排程演算法RLR之中，讓排程演算法可以更有效率降低封包丟失率。 經實驗結果顯示，使用RLR排程演算法比使用FIFO排程演算法多降低8％的平均損失率，較使用EDF排程演算法多降低3.5％的平均損失率；由此可得知，我們所提出的RLR排程演算法在降低封包平均損失率上面會有比較好的表現。[[abstract]]To improve and enhance QoS performance on the Hybrid Fiber Coaxial（HFC）, we have to build an efficient and purposeful priority mechanism. In the current scheduling algorithm, it has two different methods including Early Deadline First（EDF）and First In First Out（FIFO）. However, these solution always concentrates on using single packet to be the model. So now we will propose a new scheduling algorithm. According to the situation of adding one group of data source which is continuous packet in the data transmission, utilizing the least package drop ratio optimizes QoS performance.[[tableofcontents]]第一章 簡介 1 1.1 研究背景 1 1.2 動機與目的 1 1.3 論文章節架構 2 第二章 相關技術與背景介紹 4 2.1 先進先出服務（FIRST IN FIRST OUT, FIFO） 4 2.2 傳送期限到者優先（EARLY DEADLINE FIRST, EDF） 7 2.3 探討 10 第三章 排程演算法 11 3.1 參數定義與說明 11 3.2 傳送急迫率（SEND QUICK；SQ） 13 3.3 傳送完成率(SEND FINISH, SF) 14 3.4 損失量DLOSS 16 3.5 損失率LOSS RATE 17 3.6 RLR 排程演算法流程圖 18 3.7 舉例 20 3.7.1 參數定義 20 3.7.2 舉例說明 22 3.7.3 舉例說明（Dloss+Sf） 31 3.7.4 差異比較 38 第四章 模擬結果與比較分析 41 4.1 環境設定 41 4.2 數據模擬 42 4.3 數據模擬分析 45 4.3.1 模擬資料量對系統模擬的負載影響 45 4.3.2 分割後單一封包最大迷你時槽量對損失率的影響 49 第五章 結論與未來方向 52 5.1 結論 52 5.2 未來期望 52 參考文獻 53 圖目錄 圖2. 1 FIFO中資料到達示意圖 5 圖2. 2使用FIFO排程結果 5 圖2. 3 FIFO排程演算法流程圖 6 圖2. 4使用EDF排程資料到達示意圖 7 圖2. 5使用EDF排程結果 8 圖2. 6 EDF排程演算法流程圖 9 圖3. 1 RLR 排程演算法參數示意圖 12 圖3. 2傳送急迫率比例示意圖 13 圖3. 3傳送急迫率比例舉例圖 14 圖3. 4傳送可分割資料完成率比例示意圖 15 圖3. 5傳送完成率傳送範例 16 圖3. 6損失量比例示意圖 17 圖3. 7損失量比例示意圖-1 17 圖3. 8損失率示意圖1 18 圖3. 9 RLR排程演算法流程圖 19 圖3. 10 FIFO丟棄排程演算法流程圖 21 圖3. 11 EDF丟棄排程演算法流程圖 22 圖3. 12考量遺失率圖例1 23 圖3. 13考量遺失率圖例2 24 圖3. 14考量遺失率圖例3 25 圖3. 15考量遺失率圖例4 26 圖3. 16考量遺失率圖例5 26 圖3. 17考量遺失率圖例6 27 圖3. 18考量遺失率圖例7 28 圖3. 19考量遺失率圖例8 29 圖3. 20考量遺失率圖例9 30 圖3. 21考量遺失率圖例10 31 圖3. 22舉例Dloss+Sf圖1 32 圖3. 23舉例Dloss+Sf圖2 32 圖3. 24舉例Dloss+Sf圖3 33 圖3. 25舉例Dloss+Sf圖4 33 圖3. 26舉例Dloss+Sf圖5 34 圖3. 27舉例Dloss+Sf圖6 35 圖3. 28舉例Dloss+Sf圖7 36 圖3. 29舉例Dloss+Sf圖8 37 圖3. 30舉例Dloss+Sf圖9 38 圖3. 31差異說明圖1 39 圖3. 32差異說明圖2 40 圖4. 1 UI介面圖1 41 圖4. 2舉例Dloss+Sq圖1 43 圖4. 3執行FIFO結果 43 圖4. 4執行EDF結果 44 圖4. 5執行RLR結果 44 圖4. 6 10組隨機封包損失率直條圖 46 圖4. 7 20組隨機封包損失率直條圖 47 圖4. 8 30組隨機封包損失率直條圖 48 圖4. 9 隨機組數損失率比較圖 49 圖4. 10不同最大迷你時槽量損失率比較圖 50 圖4. 11不同最大迷你時槽量損失率比較圖 51[[note]]學號: 702440107, 學年度: 10