1、A New Jitter Control Mechanism by Per-Hop Packet Scheduling Approach 指導(dǎo)教授：連耀南教授學(xué)生：林宗銘2006/10/5OutlineIntroductionRelated WorkObjective FunctionOur SolutionPerformance EvaluationConclusionOutlineIntroductionRelated WorkObjective FunctionOur SolutionPerformance EvaluationConclusionIntroduction網(wǎng)路的進(jìn)步與發(fā)展

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

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

4、roundLowNoHighIntroductionJitterlIP封包的傳遞時(shí)間起伏不定 l過於高的Jitter將對交談式以及串流式的應(yīng)用造成嚴(yán)重服務(wù)品質(zhì)下降 l對於一個(gè)資料流到達(dá)接收端之相鄰兩個(gè)封包，其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網(wǎng)路只提供best effort資料流傳送服務(wù)。近來許多研究以per-hop封包排程的方法，然而大多數(shù)的封包排程方法並未針對封包的重要性做適當(dāng)處理。 我們亦提出per-hop封包排程方法以減低接收端之Jitter。設(shè)計(jì)與封包傳遞時(shí)間相關(guān)的profit function。根據(jù)封包行程遲早以及重要性（不同類型的profit function）做傳送順序的調(diào)整。OutlineIntroductionRelated WorkObjective FunctionOur SolutionPerformance EvaluationConclusionRelated Work最簡單的消除Jitter方法

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

7、MM 99, pp. 81-94, 1999.文獻(xiàn)三：徐毅銘, 在IPv6的DiffServ網(wǎng)路上具有Credit/Deficit調(diào)整的延遲變化率減小機(jī)制, 國立中山大學(xué), 2003.文獻(xiàn)內(nèi)容Yishay Mansour, and Boaz Patt-Shamir, 2001.l提出一個(gè)簡單的on-line的Jitter Control Algorithm，每個(gè)Router的Buffer大小為2B個(gè)單位封包。當(dāng)Buffer負(fù)載達(dá)到B時(shí)，則將Buffer 前端的封包送出，之後每隔Xa時(shí)間送出一個(gè)封包，其中Xa為封包的平均間隔時(shí)間。當(dāng)Buffer負(fù)載未達(dá)到B時(shí)，則以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根據(jù)封包到達(dá)時(shí)間計(jì)算出每個(gè)封包的eligible time和deadline，進(jìn)而對封包排程。因此，作者提出Core Jitter Virtual Clock (CJVC)，使用Dynamic Packet State(DPS)的方法，只在Edge Router記載Per Flow State，當(dāng)封包進(jìn)入Edge Router時(shí)

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

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

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

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

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

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

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

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

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

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

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

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

21、le Preemptive Queue)n0：CBR-0.5MBn1：CBR-0.5MBn2：CBR-0.5MBn3：CBR-0.5MB n4：FTP實(shí)驗(yàn)結(jié)果(Single Preemptive Queue)實(shí)驗(yàn)結(jié)果(Single Preemptive Queue)n0：CBR-1MBn1：CBR-1MBn2：CBR-1MBn3：CBR-1MB n4：FTP實(shí)驗(yàn)結(jié)果(Single Preemptive Queue)實(shí)驗(yàn)結(jié)果(Single Preemptive Queue)n0：CBR-0.5MBn1：CBR-0.5MBn2：CBR-0.5MBn3：FTP n4：FTP實(shí)驗(yàn)結(jié)果(Single P

22、reemptive Queue)實(shí)驗(yàn)結(jié)果(Single Preemptive Queue)n0：CBR-1MBn1：CBR-1MBn2：CBR-1MBn3：FTP n4：FTP實(shí)驗(yàn)結(jié)果(Single Preemptive Queue)實(shí)驗(yàn)結(jié)果(Multiple FIFO Queue)n0：CBR-0.5MBn1：CBR-0.5MBn2：CBR-0.5MBn3：CBR-0.5MB n4：FTP實(shí)驗(yàn)結(jié)果(Multiple FIFO Queue)實(shí)驗(yàn)結(jié)果(Multiple FIFO Queue)n0：CBR-1MBn1：CBR-1MBn2：CBR-1MBn3：CBR-1MB n4：FTP實(shí)驗(yàn)結(jié)果(M

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

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