ANewJitterControlMechanismbyPer-HopPacket

1、A New Jitter Control Mechanism by Per-Hop Packet Scheduling Approach 指導教授：連耀南教授學生：林宗銘2006/10/5OutlineIntroductionRelated WorkObjective FunctionOur SolutionPerformance EvaluationConclusionOutlineIntroductionRelated WorkObjective FunctionOur SolutionPerformance EvaluationConclusionIntroduction網路的進步與發展

2、，使得更多新型的網路服務迅速應運而生，在使用者越來越多的情況下，對網路的QoS (Quality of Service)也更加要求。All-IP網路受限於 Packet Switching 原有的特性，有三大品質問題有待克服lLong Delay TimelHigh JitterlHigh Packet LossIntroduction3GPP在1999年初所開始制訂的UMTS中依應用服務類型提出QoS分類架構，其中包含對Real-Time Traffic的服務考量。UMTS將網路上風行的主要應用依時效與品質需求概略分為四大類。類別應用之例Conversational (交談式 )VoIP(V

3、oice over IP)Streaming (串流式 )VoD(Video on Demand)Interactive (互動式 )TelnetBackground (背景式 )E-MailIntroduction即時性的應用服務，像是VoIP以及VoD，對於封包的Delay 以及Jitter具有嚴格的要求。各個類別的品質要求。Delay SensitivityJitter SensitivityPacket Loss SensitivityConversationalHighHighLowStreamingMediumHighLowInteractiveMediumLowHighBackg

4、roundLowNoHighIntroductionJitterlIP封包的傳遞時間起伏不定 l過於高的Jitter將對交談式以及串流式的應用造成嚴重服務品質下降 l對於一個資料流到達接收端之相鄰兩個封包，其Jitter的定義如下：Si = the sending time of packet iRi = the arrival time of packet iSj = the sending time of packet jRj = the arrival time of packet j Jitter ( Rj - Sj ) - ( Ri - Si )其中 jiIntroduction目前

5、IP網路只提供best effort資料流傳送服務。近來許多研究以per-hop封包排程的方法，然而大多數的封包排程方法並未針對封包的重要性做適當處理。 我們亦提出per-hop封包排程方法以減低接收端之Jitter。設計與封包傳遞時間相關的profit function。根據封包行程遲早以及重要性（不同類型的profit function）做傳送順序的調整。OutlineIntroductionRelated WorkObjective FunctionOur SolutionPerformance EvaluationConclusionRelated Work最簡單的消除Jitter方法

6、是使用DeJitter buffer 。l接收端設定一個較大的buffer。l方法簡單 但是可能會有相當長的Delay Time。文獻集文獻一： Yishay Mansour, and Boaz Patt-Shamir, “Jitter Control in QoS Networks,” IEEE/ACM Transactions on Networking, Aug. 2001. 文獻二： Ion Stoica, and Hui Zhang, “Providing Guaranteed Services Without Per Flow Management,” Proc. of SIGCO

7、MM 99, pp. 81-94, 1999.文獻三：徐毅銘, 在IPv6的DiffServ網路上具有Credit/Deficit調整的延遲變化率減小機制, 國立中山大學, 2003.文獻內容Yishay Mansour, and Boaz Patt-Shamir, 2001.l提出一個簡單的on-line的Jitter Control Algorithm，每個Router的Buffer大小為2B個單位封包。當Buffer負載達到B時，則將Buffer 前端的封包送出，之後每隔Xa時間送出一個封包，其中Xa為封包的平均間隔時間。當Buffer負載未達到B時，則以First Come First

8、 Serve為原則送出封包。Ion Stoica, and Hui Zhang, 1999.l由於Jitter Virtual Clock(Jitter-VC) 必須在Edge Router以及Core Router都記載著Per Flow State，以讓Router根據封包到達時間計算出每個封包的eligible time和deadline，進而對封包排程。因此，作者提出Core Jitter Virtual Clock (CJVC)，使用Dynamic Packet State(DPS)的方法，只在Edge Router記載Per Flow State，當封包進入Edge Router時

9、，預先在封包表頭加入eligible time和deadline的資訊。徐毅銘, 2003.l將每一個Hop的Queueing Delay用一個值代表，每個封包都有其預設的Per-Hop Queueing Delay。封包若是在預設時間內送出，表示封包提早送出（具有Credit），反之，則表示封包太晚送出（具有Deficit）。將Credit/ Deficit隨著封包傳輸夾帶在封包表頭中，調整封包傳送順序，將累積的Credit/ Deficit消除。文獻討論Yishay Mansour, and Boaz Patt-Shamir, 2001.l當最好的off-line方法的Buffer使用量為

10、B個單位封包，作者設計的on-line方法Buffer使用量最多為2B個單位封包。l作者此研究並無改變封包送出順序，無法針對封包屬於何種的應用類型作處理，可能會導致real-time traffic的Jitter變動過於劇烈以及Delay Time過長。Ion Stoica, and Hui Zhang, 1999.lCJVC可和Jitter-VC達到同樣的效果。l封包表頭夾帶的資訊會隨著經過的Router個數而增加，會面臨scalability的問題。l此研究是在IntServ架構下，因此會面臨scalability的問題，然而在All-IP網路下，使用DiffServ架構較為恰當。徐毅銘,

11、 2003.l作者所使用的CDWFQ相較於WFQ對Jitter有一定程度的改善。l並未針對封包的重要性做不同的處理。OutlineIntroductionRelated WorkObjective FunctionOur SolutionPerformance EvaluationConclusionObjective Function (single class)目標：利用在router對封包的排程，期望能使所有即時性訊務連結在接收端計算出的Jitter絕對值總和能最小。Work conserving service discipline。No de-jitter buffer in rec

12、eiver。假設共有N條即時性訊務連結C1、C2、Cn，分別送出N1、N2、Nn個封包，以TCa代表C連結第a個封包的End to End Delay Time。期望使最小。Objective Function (multiple class)Work conserving service discipline。No de-jitter buffer in receiver。使加權的各類別Jitter倒數和最大。分析為了最小化Jitter，每個router對封包排程時必須取得整個網路的資訊。如此作法複雜度太高。因此，每個router各自做排程的決定，在此我們利用與封包傳遞時間相關的profit

13、 function配合排程演算法來決定封包排程順序。不同的封包排程演算法以及profit function將會影響控制Jitter的效果。因此，我們將研究重點放在profit function及排程演算法的設計。This is a sub-optimal solution。OutlineIntroductionRelated WorkObjective FunctionOur SolutionPerformance EvaluationConclusionPacket SchedulingOur Approach 假設每個packet在每個router都有事先預估的停留時間， 因此， 每個封包

14、到達每個router都有預定送出的時間。在封包所經過的每一個router，根據其行程的遲早及重要性調整其傳送的先後次序，以期達到減小在接收端之Jitter絕對值總和。研究環境下Queue之分類FIFO queue：l處理進入的封包時，會將封包插入queue的尾端；而送出封包時，會將queue內的封包從前端依序送出。 Preemptive queue ：l處理進入的封包時，可將封包插入queue的任意位置；而送出封包時，會將queue內的封包從前端依序送出。 簡化Router示意圖Output queue1.Single preemptive queue2.Multiple FIFO queue

15、Single Preemptive QueueRouter任一output queue由單一個preemptive queue所組成。供作基準比較之用，因過於理想不實際。實際網路中的router為了加快交換速度不會採取preemptive queue 作法，且硬體實作花費也會過高。Single Preemptive QueueMultiple FIFO QueueRouter任一output queue由數個FIFO queue所組成。封包僅可插入其中一個queue的尾端。設計前端排程器pre-scheduler與後端排程器 post-scheduler ，搭配Multiple FIFO qu

16、eue。較為實際可行。Multiple FIFO QueueProfit Function 1Profit Function 2Profit Function 3Profit Function 4Profit Function 5Single Preemptive Queue封包排程問題描述：output queue為single preemptive queue。假設每個封包的大小都一樣。每一個封包有與傳遞時間相關的profit function。將所有的封包排程，使封包送出的順序所得到的總獲利值能最大，最終達到減小在接收端之Jitter絕對值總和。Single Preemptive Que

17、ue封包排程使用Jensens benefit functions，並以得到最大獲利為目標，則non-preemptive的封包排程問題是為一個NP-Hard的問題 。由於preemptive的封包排程問題比non-preemptive的封包排程問題更為複雜。因此，若是我們處理preemptive的封包排程問題時，則為一個NP-Hard的問題。 參考文獻：Jinggang Wang and Binoy Ravindran, BPA: A Fast Packet Scheduling Algorithm for Real-Time Switched Ethernet Networks, Proc

18、. of ICPP02.Single Preemptive Queue封包排程定義參數：在output queue裡目前正有N-1個已經排定好順序的封包，分別為pk1、pk2、pk3pkn-3、pkn-2、pkn-1，而有一個正要進入output queue的封包為pkn。Single Preemptive Queue封包排程演算法：output queue內原有N-1個封包順序維持不變，但進入的封包pkn可以插入queue任意位置之中，在此N個位置中，選取其中總獲利和最大的位置插入。Multiple FIFO Queue封包排程問題描述：output queue為M個FIFO queue。假

19、設每個封包的大小都一樣。每一個封包有與傳遞時間相關的profit function。設計前端排程器與後端排程器，使封包送出的順序所得到的總獲利值能最大，最終達到減小在接收端之Jitter絕對值總和。Multiple FIFO Queue封包排程演算法：我們排程演算法將採取輪詢（Round Robin）的方式送出封包，對每個queue都服務過一次為一次輪詢，將queue裡的封包依序全部送出稱為對queue服務一次。在處理進入的封包時，在M個插入位置中，選取總獲利值最大的位置。OutlineIntroductionRelated WorkObjective FunctionOur Solution

20、Performance EvaluationConclusion實驗一實驗目的real-time traffic為single class的情況下，觀察控制Jitter的效果 。觀察指標：所有即時性訊務接收端之Jitter絕對值總和與封包平均延遲時間Average Delay Time。實驗工具：NS2。實驗變因：即時性訊務個數、即時性訊務傳送速率、profit function類型、router的buffer size大小、 不同的output queue類型。實驗拓墣Sender：n0、n1、n2、n3、n4。Receiver：n9。Router：n5、n6、n7、n8。實驗結果(Sing

21、le Preemptive Queue)n0：CBR-0.5MBn1：CBR-0.5MBn2：CBR-0.5MBn3：CBR-0.5MB n4：FTP實驗結果(Single Preemptive Queue)實驗結果(Single Preemptive Queue)n0：CBR-1MBn1：CBR-1MBn2：CBR-1MBn3：CBR-1MB n4：FTP實驗結果(Single Preemptive Queue)實驗結果(Single Preemptive Queue)n0：CBR-0.5MBn1：CBR-0.5MBn2：CBR-0.5MBn3：FTP n4：FTP實驗結果(Single P

22、reemptive Queue)實驗結果(Single Preemptive Queue)n0：CBR-1MBn1：CBR-1MBn2：CBR-1MBn3：FTP n4：FTP實驗結果(Single Preemptive Queue)實驗結果(Multiple FIFO Queue)n0：CBR-0.5MBn1：CBR-0.5MBn2：CBR-0.5MBn3：CBR-0.5MB n4：FTP實驗結果(Multiple FIFO Queue)實驗結果(Multiple FIFO Queue)n0：CBR-1MBn1：CBR-1MBn2：CBR-1MBn3：CBR-1MB n4：FTP實驗結果(M

23、ultiple FIFO Queue)實驗結果(Multiple FIFO Queue)n0：CBR-0.5MBn1：CBR-0.5MBn2：CBR-0.5MBn3：FTP n4：FTP實驗結果(Multiple FIFO Queue)實驗結果(Multiple FIFO Queue)n0：CBR-1MBn1：CBR-1MBn2：CBR-1MBn3：FTP n4：FTP實驗結果(Multiple FIFO Queue)實驗總結(single preemptive queue)當router buffer size小於等於20KB時，使用profit function 1及profit func

24、tion 2對Jitter並無改善。當router buffer size大於20KB時，使用profit function 1及profit function 2，Jitter有明顯的改善。使用profit function 3及profit function 4Jitter有明顯的改善。當router buffer size小於等於20KB時，使用profit function 5對Jitter的改善時好時壞。當router buffer size大於20KB時，使用profit function 5，Jitter有明顯的改善。實驗總結(multiple FIFO queue)當route