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

1、數(shù)據(jù)通信與計(jì)算機(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 實(shí)時(shí)和非實(shí)時(shí)應(yīng)用 12.1.2 QoS的定義 12.1.3 QoS模型和QoS機(jī)制 12.2 調(diào)度策略和隊(duì)列管理 12.2.1 調(diào)度策略概述 12.2.2 FIFO 12.2.3 優(yōu)先級(jí)隊(duì)列 12.2.4 輪轉(zhuǎn)調(diào)度 第33講QoS綜述和調(diào)度策略方案 12.1.1 實(shí)時(shí)和非實(shí)時(shí)應(yīng)用 u問題的提出： 傳統(tǒng)的Internet采用一種盡力遞交的服務(wù)模 型，它并不確保會(huì)及時(shí)正確地遞交。隨著多 媒體

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、同的服務(wù)質(zhì)量要 求； 公平性：不能因?yàn)槟硯讉€(gè)用戶的不當(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個(gè)流等待調(diào)度，每個(gè)流n( )的帶寬 為 ，流n的平均服務(wù)率為 ，這樣流n的平 均鏈路利用率為 。假設(shè)屬于流n的分 組的平均等待時(shí)間為 。 上面的公式對(duì)于任何連續(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)度器 而言，盡管有分組在等待傳輸，也可能會(huì)空 閑一段時(shí)間，以等待該分組滿足傳輸?shù)臈l件。 最大最小公平（max-min fairness）標(biāo)準(zhǔn)： 首先把每個(gè)流要求的資源按順序進(jìn)行排列； 資源被首先分配給具有最低要求的流 ； 同時(shí)注意每個(gè)流不會(huì)獲得它所要求之外的額 外資源，在剩下來的資源中，那些還沒有達(dá) 到其要求的流平均分配剩余的資源。 第33講QoS綜述和調(diào)度策略方案 12.2.1 調(diào)度策略概述（續(xù)） 有N個(gè)流，首先把每個(gè)流按照所要求的資源 按序排列，流n要求的資源為 ，其 中 ，資源的總量為C，我們用 表 示實(shí)際分配給流n的資源。首先我們根據(jù)剩 下的資源按照平均

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

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

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