第33講QoS綜述和調(diào)度策略方案

1、數(shù)據(jù)通信與計算機網(wǎng)絡(luò)（第二版） 電子教案 笫三十三講笫三十三講 QoS概述與調(diào)度策略概述與調(diào)度策略 第33講QoS綜述和調(diào)度策略方案 本講內(nèi)容 第12章 服務(wù)質(zhì)量控制QoS 12.1 QoS概述 12.1.1 實時和非實時應(yīng)用 12.1.2 QoS的定義 12.1.3 QoS模型和QoS機制 12.2 調(diào)度策略和隊列管理 12.2.1 調(diào)度策略概述 12.2.2 FIFO 12.2.3 優(yōu)先級隊列 12.2.4 輪轉(zhuǎn)調(diào)度 第33講QoS綜述和調(diào)度策略方案 12.1.1 實時和非實時應(yīng)用 u問題的提出： 傳統(tǒng)的Internet采用一種盡力遞交的服務(wù)模 型，它并不確保會及時正確地遞交。隨著多 媒體

2、技術(shù)和網(wǎng)絡(luò)帶寬的進一步提高，包括音 頻和視頻等在內(nèi)的多媒體信息也開始在 Internet上進行傳輸，但是除了要求比較高 的帶寬外，也具有一些新的特性，也就是說 要求音頻數(shù)據(jù)能夠及時地遞交。 第33講QoS綜述和調(diào)度策略方案 12.1.1 實時和非實時應(yīng)用（續(xù)） u冗余尺寸網(wǎng)絡(luò) 實時應(yīng)用的一個最主要的特性是它要求數(shù)據(jù) 能夠及時到達。 非實時應(yīng)用一般可以通過一個端到端的重傳 機制來保證數(shù)據(jù)能夠正確地到達。 在盡力遞交的服務(wù)模型下面提供好的服務(wù)質(zhì) 量的一種方法是網(wǎng)絡(luò)提供大量的緩沖區(qū)和帶 寬等資源，保證分組快速地轉(zhuǎn)發(fā)，不出現(xiàn)擁 塞，分組的延時和延時抖動非常小，也不會 出現(xiàn)分組的丟失，這種方法稱為冗余尺

3、寸冗余尺寸 （over-dimensioning）。 第33講QoS綜述和調(diào)度策略方案 12.1.1 實時和非實時應(yīng)用（續(xù)） Over-dimensioning雖然非常簡單，但是代價 也非常高，由于用戶通過網(wǎng)絡(luò)傳輸?shù)呢撦d可 動態(tài)變化，嚴格的over-dimensioning技術(shù)要 求在任何時候都有充足的網(wǎng)絡(luò)資源，這也意 味著必須按照峰值負載來進行網(wǎng)絡(luò)的配置。 在冗余尺寸網(wǎng)絡(luò)中，網(wǎng)絡(luò)可以通過和用戶之 間進行協(xié)商以限制用戶發(fā)送的平均負載以及 允許的突發(fā)程度，但是這種方法并沒有最優(yōu) 地利用網(wǎng)絡(luò)的容量，因為用戶的服務(wù)質(zhì)量要 求可能會各不相同。 第33講QoS綜述和調(diào)度策略方案 12.1.1 實時和非實

4、時應(yīng)用（續(xù)） 另外一種方法是對于不同服務(wù)質(zhì)量要求的數(shù) 據(jù)分別通過不同的物理鏈路進行傳輸。 盡力遞交再加上冗余尺寸技術(shù)雖然可以提供 分組的及時遞交，但是由于需要大量的網(wǎng)絡(luò) 資源，一般只在某些特殊的環(huán)境下才使用。 傳統(tǒng)的Internet應(yīng)用只需要網(wǎng)絡(luò)提供盡力遞 交服務(wù)， 而實時的應(yīng)用則希望網(wǎng)絡(luò)能夠提供 數(shù)據(jù)的及時遞交。 網(wǎng)絡(luò)應(yīng)該對這些要求不同服務(wù)的應(yīng)用的分組 進行區(qū)別對待，一個網(wǎng)絡(luò)如果能夠提供不同 類型的服務(wù)，我們經(jīng)常說它支持QoS。 第33講QoS綜述和調(diào)度策略方案 u根據(jù)是否要求數(shù)據(jù)的及時遞交，可以把 應(yīng)用分為兩大類：實時應(yīng)用和非實時應(yīng) 用。 應(yīng)用 非實時 交互式 交互式批量 異步 實時 容錯

5、 不容錯 自適應(yīng) 非自適應(yīng) 速率自適應(yīng) 延遲自適應(yīng) 速率自適應(yīng) 非自適應(yīng) 應(yīng)用分類 第33講QoS綜述和調(diào)度策略方案 12.1.1 實時和非實時應(yīng)用（續(xù)） u非實時應(yīng)用 非實時應(yīng)用又被稱為彈性應(yīng)用（Elastic Application），因為它允許數(shù)據(jù)經(jīng)歷相對大 一點的延遲抖動。 基本要求是能夠得到一個可靠的、有序的端 到端的數(shù)據(jù)遞交服務(wù)。 交互式非實時應(yīng)用要求幾乎實時的交互，理 想的延遲是在200毫秒之內(nèi)，但是也可以容 忍一個稍長的延時。 第33講QoS綜述和調(diào)度策略方案 12.1.1 實時和非實時應(yīng)用（續(xù)） 交互式批量應(yīng)用（Interactive bulk applications）對于

6、延遲的要求和交互式應(yīng)用 類似，但是可能有較高的吞吐量要求。 異步應(yīng)用允許相對大的延遲，因為它一般是 采用存儲轉(zhuǎn)發(fā)方式來工作，用戶并不需要實 時的交互，這個方面的例子是E-mail。 u實時應(yīng)用 實時應(yīng)用又被稱為無彈性應(yīng)用（Inelastic Application），一般對于延時、延時抖動、 吞吐量的變化等相對敏感一些。 第33講QoS綜述和調(diào)度策略方案 12.1.1 實時和非實時應(yīng)用（續(xù)） 按照是否能夠容忍分組的“丟失”，實時應(yīng) 用進一步又可以分為容錯（Tolerant）應(yīng)用 和不容錯（Intolerant）應(yīng)用。 實時容錯應(yīng)用可以根據(jù)是否能夠?qū)W(wǎng)絡(luò)的當(dāng) 前情況進行響應(yīng)而進一步分為自適應(yīng)和非

7、自 適應(yīng)兩種。 通過改變播放延遲而對分組延遲的變化進行 自適應(yīng)的機制稱為延遲自適應(yīng)（Delay- adaptive）。 第33講QoS綜述和調(diào)度策略方案 12.1.1 實時和非實時應(yīng)用（續(xù)） 另外一種自適應(yīng)方式被稱為速率自適應(yīng) （Rate-adaptive），比如一個視頻應(yīng)用可以 在網(wǎng)絡(luò)的帶寬足夠的情況下采用更好的視頻 編碼而達到更高的畫面質(zhì)量，而在網(wǎng)絡(luò)帶寬 下降時采用一個相對低速的視頻編碼。 不容錯的實時應(yīng)用無法接受分組丟失，有些 應(yīng)用也可以通過檢測吞吐率的變化而進行動 態(tài)地響應(yīng)，而大多數(shù)應(yīng)用則屬于非自適應(yīng)的。 第33講QoS綜述和調(diào)度策略方案 12.1.2 QoS的定義 u什么是QoS 對

8、于通信網(wǎng)絡(luò)來說，QoS指的是網(wǎng)絡(luò)提供給 用戶或者應(yīng)用的服務(wù)的等級或者質(zhì)量描述； 而對于應(yīng)用程序來說QoS指的是用戶感受到 的應(yīng)用質(zhì)量 u問題的提出 基于網(wǎng)絡(luò)的QoS策略提供各種不同的服務(wù)質(zhì) 量支持，但它并不能完全取代基于應(yīng)用的 QoS控制策略。網(wǎng)絡(luò)的狀況會動態(tài)改變，在 這種環(huán)境下進行端到端的自適應(yīng)QoS控制就 顯得尤其重要。 第33講QoS綜述和調(diào)度策略方案 12.1.2 QoS的定義（續(xù)） u服務(wù) 服務(wù)指的是分組在通過網(wǎng)絡(luò)傳遞過程中所獲 得的預(yù)先定義好的對待，一般說來服務(wù)質(zhì)量 可以通過定性或者定量的方法進行描述。 定量方法： 通過一些具體的QoS參數(shù)的定量來描述的， 常用的QoS參數(shù)包括延遲

9、、延遲抖動、丟失 率和帶寬等。 定性方法： 第33講QoS綜述和調(diào)度策略方案 12.1.2 QoS的定義（續(xù)） 采用定性的方法來描述QoS的原因有很多， 比如某些應(yīng)用很難把它要求的服務(wù)質(zhì)量進行 量化，或者它只是要求能夠獲得比別的應(yīng)用 更好的服務(wù)等。 u延遲 延遲指的是分組在傳輸過程中所花的時間。 分組在網(wǎng)絡(luò)中4種不同類型的延遲的： 傳輸延遲 傳播延遲 第33講QoS綜述和調(diào)度策略方案 12.1.2 QoS的定義（續(xù)） 處理延遲 排隊延遲 延遲抖動 延遲抖動指的是網(wǎng)絡(luò)延遲的變化。 端到端的延遲可能會動態(tài)變化。 u分組丟失 分組丟失的三個原因： 網(wǎng)絡(luò)擁塞； 分組太遲到達； 第33講QoS綜述和調(diào)度

10、策略方案 12.1.2 QoS的定義（續(xù)） 分組在通過通信鏈路傳輸時出現(xiàn)錯誤。 u吞吐率 吞吐率指的是通過網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)速率，一 般用每秒傳輸多少比特來描述，又被稱為比 特率或者帶寬。 固定速率（Constant Bit Rate，CBR）應(yīng)用按 照恒定的數(shù)據(jù)速率產(chǎn)生負載； 可變速率（Variable Bit Rate，VBR）應(yīng)用有 最低的帶寬要求以保證應(yīng)用可以正常進行。 第33講QoS綜述和調(diào)度策略方案 12.1.2 QoS的定義（續(xù)） u服務(wù)類型（Type-of-Service，ToS） ToS是IPv4中IP頭部的一個字段，目的是為了使 得根據(jù)ToS字段的取值來對分組進行不同的處理。

11、0 優(yōu)先級T 1234567 DR00 IPv4 ToS字段 第33講QoS綜述和調(diào)度策略方案 12.1.2 QoS的定義（續(xù)） u服務(wù)類（Class of Service，CoS） CoS允許根據(jù)流的QoS把不同的流匯集在一起， 匯集在一起的各個流有不同的延遲、帶寬等 QoS參數(shù)，類的劃分不是通過定量的東西，而 是定性地確定。 第33講QoS綜述和調(diào)度策略方案 12.1.3 QoS模型和QoS機制 uQoS服務(wù)的劃分： 根據(jù)網(wǎng)絡(luò)提供的服務(wù)類型：這包括通過定量 地描述QoS參數(shù)的取值的定量服務(wù)、通過定 性描述的定性服務(wù)和盡力遞交服務(wù)等； 根據(jù)網(wǎng)絡(luò)提供服務(wù)的實體是什么？是對于每 個負載流提供服務(wù)

12、？還是對于每個負載類型 提供服務(wù)？ 應(yīng)用根據(jù)QoS要求、應(yīng)用類型等可以分成不 同的類，基于類的服務(wù)為每個類提供定性或 者定量的服務(wù)。 第33講QoS綜述和調(diào)度策略方案 12.1.3 QoS模型和QoS機制（續(xù)） uIP QoS的兩種主要體系結(jié)構(gòu)： 集成服務(wù)（Integrated Services，IntServ） IntServ模型提供的是基于流的服務(wù)，它通過 預(yù)留相應(yīng)的網(wǎng)絡(luò)資源來提供QoS支持，RSVP 協(xié)議用于傳遞相應(yīng)的信令信息來進行資源的 預(yù)留，是IntServ模型的核心部分。 集成服務(wù)為每個流提供相應(yīng)的服務(wù)質(zhì)量保障。 QoS要求一般包括兩個負載描述字： 第33講QoS綜述和調(diào)度策略方案

13、 12.1.3 QoS模型和QoS機制（續(xù)） TSpec：描述了用戶發(fā)送的負載的特性。 RSpec：則描述了用戶希望的服務(wù)質(zhì)量。 區(qū)分服務(wù)（Differentiated Services， Diffserv） 區(qū)分服務(wù)利用IP分組頭部中的字段把IP分組 映射成相應(yīng)的服務(wù)類。 那個IP頭部的字段被稱為DSCP，DSCP在IPv4 中通過ToS字段來表示，而IPv6中則通過負載 類型來表示。 第33講QoS綜述和調(diào)度策略方案 12.1.3 QoS模型和QoS機制（續(xù)） uQoS機制的分類 負載處理機制 帶寬管理機制 u通信量控制機制 了防止其占用過多的網(wǎng)絡(luò)資源，路由器一般 要對于用戶的負載進行監(jiān)控

14、，如果發(fā)送的負 載超過了協(xié)商值，則路由器可能丟棄這些額 外的分組或者降級處理，這種機制被稱為通 信量控制機制。 第33講QoS綜述和調(diào)度策略方案 12.1.3 QoS模型和QoS機制（續(xù)） uQoS機制與擁塞控制機制的關(guān)系 擁塞控制的目的是防止網(wǎng)絡(luò)來不及處理用戶 的負載，并且在出現(xiàn)擁塞的情況下將擁塞的 影響減至最少，并且盡可能快地從擁塞恢復(fù)。 QoS機制則是為不同的用戶提供不同的服務(wù) 質(zhì)量保證，通過對于不同用戶的分組進行區(qū) 別對待來完成。 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述 u一條重要的設(shè)計原則是網(wǎng)絡(luò)層盡可能地簡單， 而將許多包括流量控制、可靠遞交、擁塞控制 等復(fù)雜的

15、功能交給高層來處理。 u由于采用數(shù)據(jù)報服務(wù)，分組可能會采用不同的 路徑到達目的地，因此分組經(jīng)歷的延遲可能會 各不相同，到達也可能會不按序到達。 u而當(dāng)鏈路出現(xiàn)擁塞時候，排隊延遲會顯著增加， 從而分組經(jīng)歷的延遲會增大，當(dāng)隊列滿時分組 將被丟棄。 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） u排隊機制 排隊機制包括對帶寬和緩沖區(qū)這兩種資源的 合理分配。 帶寬的分配指的是選擇那個分組來傳輸，一 般被稱為調(diào)度機制。 分配指的是何時丟棄隊列中的分組，丟棄哪 個分組，一般被稱為隊列管理機制。 路由器包括的功能單元： 轉(zhuǎn)發(fā)/路由策略：由網(wǎng)絡(luò)管理人員設(shè)置的策 略控制； 第33講QoS綜

16、述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） 轉(zhuǎn)發(fā)/路由表：通過路由協(xié)議來構(gòu)建； 輸入隊列：一般假設(shè)分組按照線速到達； 分組分類器：基于相應(yīng)的策略控制來對分組 進行分類； 交換結(jié)構(gòu)：分組從輸入隊列轉(zhuǎn)移到相應(yīng)的輸 出隊列； 輸出隊列：等待傳輸?shù)姆纸M在此排隊； 調(diào)度器：決定為哪個輸出隊列進行服務(wù)。 下圖給出了一個簡單的路由器模型 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） 轉(zhuǎn)發(fā)/路由策略 分組分類器交換結(jié)構(gòu)輸出隊列 路由表調(diào)度器 一個簡單的路由器模型 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） u調(diào)度算法 算法的特點： 靈活性：不同的用戶具有不

17、同的服務(wù)質(zhì)量要 求； 公平性：不能因為某幾個用戶的不當(dāng)行為而 導(dǎo)致別的用戶的服務(wù)質(zhì)量得不到保障； 有效性：有效地利用包括鏈路帶寬和緩沖區(qū) 在內(nèi)的空閑的網(wǎng)絡(luò)資源。 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） 調(diào)度器 工作原理 有N個流等待調(diào)度，每個流n( )的帶寬 為 ，流n的平均服務(wù)率為 ，這樣流n的平 均鏈路利用率為 。假設(shè)屬于流n的分 組的平均等待時間為 。 上面的公式對于任何連續(xù)工作型的調(diào)度算法 都適用 Nn1 n n n n n n q 為常量，其中CCq N 1n nn 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） 斷續(xù)工作（non-wo

18、rk-conserving）的調(diào)度器 而言，盡管有分組在等待傳輸，也可能會空 閑一段時間，以等待該分組滿足傳輸?shù)臈l件。 最大最小公平（max-min fairness）標(biāo)準： 首先把每個流要求的資源按順序進行排列； 資源被首先分配給具有最低要求的流 ； 同時注意每個流不會獲得它所要求之外的額 外資源，在剩下來的資源中，那些還沒有達 到其要求的流平均分配剩余的資源。 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） 有N個流，首先把每個流按照所要求的資源 按序排列，流n要求的資源為 ，其 中 ，資源的總量為C，我們用 表 示實際分配給流n的資源。首先我們根據(jù)剩 下的資源按照平均

19、分配的方法計算，我們用 表示可以分配給流n的資源數(shù)，顯然： N21 xxx n x n m n M 1n-N m-C M 1n 1i i n 數(shù)尚未滿足需求的流的個 剩余資源數(shù) 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） 而分配給流n的資源不能超過其實際要求 的資源數(shù)，因此： Nn1)M,x(minm nnn 其中 第33講QoS綜述和調(diào)度策略方案 12.2.2 FIFO uFIFO調(diào)度機制 又被稱為先來先服務(wù)（First-Come First- Served，F(xiàn)CFS）。每個輸出鏈路有一個隊列， 當(dāng)分組到來時，按照到達的順序放入輸出鏈 路對應(yīng)的隊列，最早到達的分組最先

20、得到服 務(wù)，如果隊列滿，則選擇合適的分組丟棄。 FIFO是一種連續(xù)工作型的調(diào)度算法，很難滿 足不同流的各不相同的服務(wù)質(zhì)量要求。 第33講QoS綜述和調(diào)度策略方案 12.2.2 FIFO（續(xù)） 到來的分組 下一個發(fā)送的分組 排隊的分組空閑緩沖區(qū) 下一個空閑緩沖區(qū) 到來的分組 下一個發(fā)送的分組 排隊的分組 丟棄 FIFO 第33講QoS綜述和調(diào)度策略方案 12.2.3 優(yōu)先級隊列 u機制 輸出鏈路有多個隊列，每個隊列具有不同的 優(yōu)先級，那些要在該輸出鏈路上傳輸?shù)姆纸M 通過分類分別映射到不同的隊列上。 如果輸出鏈路空閑，位于更高優(yōu)先級隊列中 的分組被優(yōu)先傳輸。 低優(yōu)先級隊列中的分組只有在所有更高優(yōu)先

21、 級隊列空的情況下才能進行傳輸，在每個隊 列里面仍然按照FIFO選擇分組傳輸。 第33講QoS綜述和調(diào)度策略方案 12.2.3 優(yōu)先級隊列（續(xù)） u映射機制 u存在的問題 高優(yōu)先級分組可能導(dǎo)致低優(yōu)先級的分組無法 進行傳輸，低優(yōu)先級的分組可能無法得到任 何帶寬保證。 對于同一個優(yōu)先級的分組都平等對待，這樣 一個用戶可能發(fā)送大量的分組，從而剝奪別 的用戶發(fā)送的具有同樣優(yōu)先級分組獲得帶寬 的權(quán)利。 第33講QoS綜述和調(diào)度策略方案 12.2.4 輪轉(zhuǎn)調(diào)度 u輪轉(zhuǎn)調(diào)度（Round-Robin Scheduling）機 制 分組被映射成不同的隊列，按照循環(huán)的方式 輪流從那些非空的隊列中選擇一個分組進行 傳輸。 如果總共有K個隊列，則首先選擇隊列1中的 分組傳輸，然后是隊列2，接著是隊列3，.， 然后是隊列K，然后是隊列1。 如果發(fā)現(xiàn)某個隊列中沒有分組等待傳輸，則 跳過該隊列，按照順序選擇下一個隊列。 第33講QoS綜述和調(diào)度策略方案 12.2.4 輪轉(zhuǎn)調(diào)度（續(xù)） u從赤字輪轉(zhuǎn)調(diào)度（Deficit Round-Robi