路由器原理與設(shè)計(jì)講稿6-交換網(wǎng)絡(luò)

1、內(nèi)內(nèi) 部部 通通 信信路由器總體結(jié)構(gòu)路由器總體結(jié)構(gòu)高高 速速 交交 換換 網(wǎng)網(wǎng) 絡(luò)（主絡(luò)（主備）備）內(nèi)內(nèi) 部部 通通 信（主信（主/備）備）主控主控 / 管理模塊管理模塊主主 控控 模模 塊塊 （主（主/備）備）轉(zhuǎn)發(fā)引擎轉(zhuǎn)發(fā)引擎線路接口線路接口轉(zhuǎn)發(fā)引擎轉(zhuǎn)發(fā)引擎線路接口線路接口轉(zhuǎn)發(fā)引擎轉(zhuǎn)發(fā)引擎線路接口線路接口外部接口外部接口外部接口外部接口操作維護(hù)臺(tái)操作維護(hù)臺(tái)外部接口外部接口本本 章章 內(nèi)內(nèi) 容容n交換網(wǎng)絡(luò)的基本原理交換網(wǎng)絡(luò)的基本原理n交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類n調(diào)度策略調(diào)度策略n緩存器管理緩存器管理n組播實(shí)現(xiàn)組播實(shí)現(xiàn)nQoS支持支持輸入緩存與控制輸入緩存與控制輸出緩存與控制輸出緩存與控制輸輸 入

2、入輸輸 出出輸入緩存與控制輸入緩存與控制輸出緩存與控制輸出緩存與控制輸入緩存與控制輸入緩存與控制輸出緩存與控制輸出緩存與控制輸入緩存與控制輸入緩存與控制輸出緩存與控制輸出緩存與控制6.1交換網(wǎng)絡(luò)的基本原理交換網(wǎng)絡(luò)的基本原理輸入緩存與控制輸入緩存與控制輸出緩存與控制輸出緩存與控制輸輸 入入輸輸 出出輸入緩存與控制輸入緩存與控制輸出緩存與控制輸出緩存與控制輸入緩存與控制輸入緩存與控制輸出緩存與控制輸出緩存與控制輸入緩存與控制輸入緩存與控制輸出緩存與控制輸出緩存與控制合合 路路緩緩 存存分分 發(fā)發(fā)6.1交換網(wǎng)絡(luò)的基本原理交換網(wǎng)絡(luò)的基本原理本本 章章 內(nèi)內(nèi) 容容n交換網(wǎng)絡(luò)的基本原理交換網(wǎng)絡(luò)的基本原理n

3、交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類n調(diào)度策略調(diào)度策略n緩存器管理緩存器管理n組播實(shí)現(xiàn)組播實(shí)現(xiàn)nQoS支持支持n共享內(nèi)存Speed is limited by memory access speedn共享總線Speed is limited by bus capacitancen空分復(fù)用crossbarSpeed is limited by the scheduler6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類共享內(nèi)存Route ProcessorMemoryDMARoute CacheMemoryMACLine CardDMARoute CacheMemoryMACLine CardDM

4、ARoute CacheMemoryMACLine CardBus Cache updates6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類共享總線6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類crossbar6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類crossbar空分空分Crossbar是一個(gè)交換矩陣，在同一時(shí)刻（時(shí)是一個(gè)交換矩陣，在同一時(shí)刻（時(shí)隙）每一個(gè)輸出只能連接到一個(gè)輸入上，因而當(dāng)隙）每一個(gè)輸出只能連接到一個(gè)輸入上，因而當(dāng)多個(gè)輸入往同一輸出端發(fā)包時(shí)，必須有緩存，根多個(gè)輸入往同一輸出端發(fā)包時(shí)，必須有緩存，根據(jù)緩存器的位置不同，交換結(jié)構(gòu)分為，據(jù)緩存器的位置不同，交換結(jié)構(gòu)分為，輸出排隊(duì)（輸出排隊(duì)（OQ）結(jié)構(gòu)）結(jié)構(gòu)輸入排隊(duì)（輸入排隊(duì)（

5、IQ）結(jié)構(gòu)）結(jié)構(gòu)虛擬輸入排隊(duì)（虛擬輸入排隊(duì)（VOQ）組合輸入輸出排隊(duì)（組合輸入輸出排隊(duì)（CIOQ）結(jié)構(gòu)）結(jié)構(gòu)優(yōu)點(diǎn)：高性能 ；高QoS保障；大量成熟的調(diào)度策略可選用缺點(diǎn)： N倍加速問題，在高速環(huán)境下應(yīng)用受限6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類-LookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableQueuePacket

6、BufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryBufferManagerBufferMemoryBufferManagerBufferMemoryBufferManagerBufferMemory6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類LookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader Pro

7、cessingAddressTableQueuePacketBufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryDataHdrDataHdrDataHdr12N 12NN times line rateN times line rate6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類-雖然輸出排隊(duì)能提供很好的性能，但商雖然輸出排隊(duì)能提供很好的性能，但商用存儲(chǔ)器訪問速率的限制制約了其在高用存儲(chǔ)器訪問速率的限制制約了其在高速路由器中的使用速路由器中的使用6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類-優(yōu)點(diǎn)：不需要加速缺點(diǎn)：鏈頭（HOL）阻塞；對(duì)QoS支持較差；調(diào)度策略

8、復(fù)雜度高6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類-LookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableQueuePacketBufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryDataHdrDataHdrDataHdr12N 12NDataHdrDataH

9、drDataHdrScheduler6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類-0%20%40%60%80%100%LoadDelayThe best that any queueing system can achieve.理論上吞吐率可下降為原來的58.6%6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類0%20%40%60%80%100%LoadDelayThe best that any queueing system can achieve.2258%6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類優(yōu)點(diǎn)：克服了HOL阻塞，提高了吞吐率，理論上可達(dá)100%缺點(diǎn)：需要集中式的調(diào)度策略支持，較差的QoS保證

10、對(duì)每個(gè)輸出都在輸入端建立一個(gè)單獨(dú)的隊(duì)列FIFO6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類 0%20%40%60%80%100%LoadDelayThe best that any queueing system can achieve.6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類 u最大匹配MSM（Maximum Size Matching）u復(fù)雜度高，硬件實(shí)現(xiàn)復(fù)雜，實(shí)際用極大匹配（maximal matching）來近似uSLIP（iterative round-robin matching with SLIP）支持優(yōu)先級(jí)和公平調(diào)度。擴(kuò)展版的ESLIP支持組播u最大權(quán)重匹配MWM（Max

11、imum Weighed Matching ）uLQF（Longest Queue First）和OCF（Oldest Cell First）算法硬件實(shí)現(xiàn)復(fù)雜采用iLQF和iOCF來迭代逼近，但實(shí)現(xiàn)依然相當(dāng)復(fù)雜u穩(wěn)定結(jié)合配對(duì)uGSA（Gale-Shapley Algorithm）算法u利用定義的優(yōu)先級(jí)來調(diào)度分組，可以獲得好的吞吐率和時(shí)延限度u輸入排隊(duì)的管理策略都采用了避免HOL阻塞的方法，努力實(shí)現(xiàn)好的QoS保證6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類優(yōu)點(diǎn)：2倍加速下可模擬實(shí)現(xiàn)OQ的性能；適合任意端口數(shù)目和流量模式缺點(diǎn)：調(diào)度策略復(fù)雜度過高，僅具有理論意義在輸入和輸出端都建立隊(duì)列來緩存分組6.2交換網(wǎng)絡(luò)分類

12、交換網(wǎng)絡(luò)分類 超摩爾定律 傳輸速率每九個(gè)月翻一番。結(jié)論：結(jié)論：處理速率的發(fā)展無法跟上傳輸速率發(fā)展的處理速率的發(fā)展無法跟上傳輸速率發(fā)展的步伐，因此采用并行交換結(jié)構(gòu)是高速路由器的必然步伐，因此采用并行交換結(jié)構(gòu)是高速路由器的必然趨勢(shì)。趨勢(shì)。 摩爾定律 CPU的處理速率每18個(gè)月將翻一番。 6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類優(yōu)點(diǎn)：處理速度要求低 ，可提供高性能交換缺陷：在一定程度上導(dǎo)致系統(tǒng)控制維護(hù)復(fù)雜6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類定長包交換：定長包交換：Crossbar，交換矩陣中的開關(guān)轉(zhuǎn)換，交換矩陣中的開關(guān)轉(zhuǎn)換每隔固定的時(shí)間變換一次每隔固定的時(shí)間變換一次不定長包交換：無法保

13、證每一路包的傳輸時(shí)間是不定長包交換：無法保證每一路包的傳輸時(shí)間是相等的，因此若用相等的，因此若用Crossbar交換結(jié)構(gòu)，必須進(jìn)行切交換結(jié)構(gòu)，必須進(jìn)行切片。片。6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類不定長包交換不定長包交換6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類不定長包交換不定長包交換本本 章章 內(nèi)內(nèi) 容容n交換網(wǎng)絡(luò)的基本原理交換網(wǎng)絡(luò)的基本原理n交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類n調(diào)度策略調(diào)度策略n緩存器管理緩存器管理n組播實(shí)現(xiàn)組播實(shí)現(xiàn)nQoS支持支持 調(diào)度機(jī)是網(wǎng)絡(luò)節(jié)點(diǎn)中的一個(gè)組件，它依照一定的調(diào)度算法選擇緩存隊(duì)列中最需要發(fā)送的包送到輸出鏈路上 包調(diào)度算法管理著最重要的網(wǎng)絡(luò)資源輸出鏈路帶寬。 良好的調(diào)度算法能夠隔離各個(gè)用

14、戶流，起到防火墻的作用，為路由器提供安全保障，保證正常使用網(wǎng)絡(luò)的用戶不受其他用戶有意或無意的干擾。 調(diào)度算法直接控制包的時(shí)延而緩存器管理控制包的丟失率，所以調(diào)度算法與緩存器管理策略控制著QoS中最重要的性能指標(biāo)時(shí)延和丟包率。 時(shí)延和丟包率是密切相關(guān)的，對(duì)一個(gè)業(yè)務(wù)流，分配給它的帶寬越多，它需要的緩存空間越小，另外，大的包時(shí)延容易導(dǎo)致更大的包丟失率。 因而包調(diào)度算法和緩存器管理策略是網(wǎng)絡(luò)保證業(yè)務(wù)QoS最重要兩項(xiàng)關(guān)鍵技術(shù) 6.3調(diào)度策略調(diào)度策略6.3調(diào)度策略調(diào)度策略 圖3.3 包調(diào)度原理示意圖 調(diào)度算法可分為盡職工作型（Work-conserving）和非盡職工作型（Non Work-conserv

15、ing） 采用盡職工作型調(diào)度算法時(shí)，只有緩存器中沒有待發(fā)送的包時(shí)，輸出鏈路才會(huì)空閑 非盡職工作型調(diào)度算法則可能在緩存器中還有包時(shí)，輸出鏈路空閑。 盡職工作型調(diào)度算法可以最大限度地利用輸出鏈路的帶寬資源 非盡職工作型調(diào)度算法在控制時(shí)延抖動(dòng)時(shí)往往是一種較好的選擇，即包可以進(jìn)行時(shí)延以滿足特定的時(shí)延要求。 6.3調(diào)度策略調(diào)度策略現(xiàn)有調(diào)度算法主要分為三類：現(xiàn)有調(diào)度算法主要分為三類： 基于輪詢的調(diào)度策略基于輪詢的調(diào)度策略( (PRR，BBRR，WRR，WFQ,SFQ，DRR，GPS，PGPS，WF2Q) )基于保證單節(jié)點(diǎn)上時(shí)延上界的調(diào)度策略基于保證單節(jié)點(diǎn)上時(shí)延上界的調(diào)度策略 ( (EDF、Stop-and

16、-Go) )基于保證端到端時(shí)延上界的調(diào)度策略基于保證端到端時(shí)延上界的調(diào)度策略 (FIFO+、Virtual Clock、SCED) 6.3調(diào)度策略調(diào)度策略-6.3調(diào)度策略調(diào)度策略-包輪詢或逐包調(diào)度策略（包輪詢或逐包調(diào)度策略（Packet Round Robin；PRR） Nagle的思想是在每一網(wǎng)絡(luò)節(jié)點(diǎn)上將不同流放入不同的隊(duì)列中，然后逐個(gè)的思想是在每一網(wǎng)絡(luò)節(jié)點(diǎn)上將不同流放入不同的隊(duì)列中，然后逐個(gè)輪詢調(diào)度輸出各隊(duì)列的包，跳過空隊(duì)列，若有多個(gè)活動(dòng)的流，則每個(gè)隊(duì)列每一輪詢調(diào)度輸出各隊(duì)列的包，跳過空隊(duì)列，若有多個(gè)活動(dòng)的流，則每個(gè)隊(duì)列每一輪詢周期發(fā)送一個(gè)包輪詢周期發(fā)送一個(gè)包 圖3.4 逐包調(diào)度策略示意圖

17、加權(quán)公平排隊(duì)策略（加權(quán)公平排隊(duì)策略（Weighted Fair Queuing）Demers，Keshav和Shenker對(duì)Nagle的算法進(jìn)行了改進(jìn)，提出了逐比特輪詢調(diào)度算法逐比特輪詢調(diào)度算法（Bit-by-bit Round Robin Service; BBRR），輪詢機(jī)每一輪從每一隊(duì)列中調(diào)度一比特而非一個(gè)包，因而解決了包長不同帶來的不公平，但這僅僅是一個(gè)理論分析方法，因?yàn)榘l(fā)送時(shí)不可能將包打碎。加權(quán)逐比特輪詢調(diào)度算法加權(quán)逐比特輪詢調(diào)度算法 當(dāng)輪詢到某一隊(duì)列時(shí)，從該隊(duì)列中調(diào)度的比特?cái)?shù)由該隊(duì)列的權(quán)值決定。6.3調(diào)度策略調(diào)度策略-它是BBRR的實(shí)用版，其工作原理如下：1.在理論上計(jì)算Fi（i=

18、1,2,K；K為隊(duì)列數(shù)）的值，F(xiàn)i為采用加權(quán)BBRR策略時(shí)，第i個(gè)隊(duì)列中的包最后一比特被調(diào)度出去的時(shí)間；2.比較各個(gè)隊(duì)列Fi的大小。若FjFi (i=1,2, ,K, ij) 則調(diào)度第j個(gè)隊(duì)列中的一個(gè)包輸出。FjCi，則將該輪應(yīng)發(fā)的字節(jié)數(shù)N儲(chǔ)蓄起來，留到下一輪使用，轉(zhuǎn)到下一隊(duì)列；(d) 如果輪詢到隊(duì)列i時(shí)，隊(duì)列是空的，則將計(jì)數(shù)器Ci清零，這一做法是為了不讓Ci無限增大，雖然顯得不很公平，但是卻能夠防止突發(fā)的形成和對(duì)其他隊(duì)列的影響。DRR算法中，每個(gè)隊(duì)列的計(jì)數(shù)器記錄了輪詢機(jī)虧欠該隊(duì)列的字節(jié)數(shù)，因此稱為欠帳式輪詢調(diào)度算法。6.3調(diào)度策略調(diào)度策略-虛時(shí)鐘（虛時(shí)鐘（Virtual Clock）調(diào)度算法

19、）調(diào)度算法81,97虛時(shí)鐘的概念來源于TDM系統(tǒng)，由于每一用戶只能在給定的時(shí)隙內(nèi)發(fā)送數(shù)據(jù)，因而TDM系統(tǒng)沒有用戶間的干擾。但是，當(dāng)某一用戶在某一段時(shí)間內(nèi)沒有數(shù)據(jù)發(fā)送時(shí)，它所對(duì)應(yīng)的時(shí)隙就空閑，帶寬資源被浪費(fèi)了。虛時(shí)鐘算法的目的就是既得到TDM系統(tǒng)的隔離作用，又保持包交換系統(tǒng)的統(tǒng)計(jì)復(fù)用效果。TDM系統(tǒng)是在實(shí)時(shí)鐘控制下工作，Virtual Clock算法是在虛時(shí)鐘控制下工作。假設(shè)某一流到達(dá)路由器的包具有虛時(shí)間空間的固定速率，則每當(dāng)一個(gè)包到達(dá)時(shí)，就有一個(gè)時(shí)隙的時(shí)間過去了。依據(jù)這一思想，為每一數(shù)據(jù)流指定一個(gè)虛時(shí)鐘，每當(dāng)這一流的一個(gè)包到達(dá)時(shí)，該時(shí)鐘走一步，步幅Vticki等于包到達(dá)的間隔（設(shè)包長固定），如

20、果某一流按照約定的速率發(fā)包，則虛時(shí)鐘的跳變時(shí)刻就在實(shí)際時(shí)間附近。 一般處理器共享一般處理器共享（Generalized Processor Sharing Algorithm；GPS） 輸入鏈路 圖3.5 GPS調(diào)度算法示意圖 輸出鏈路Fluid Flow6.3調(diào)度策略調(diào)度策略-6.3調(diào)度策略調(diào)度策略-逐包一般處理器共享（逐包一般處理器共享（Packet-by-Packet GPS；PGPS）算法）算法2,82,84 PGPS算法是GPS的近似實(shí)現(xiàn)，它以逐包調(diào)度的方式進(jìn)行。設(shè)Fi是采用GPS調(diào)度算法時(shí)第i個(gè)隊(duì)列中包P的最后一個(gè)比特離開節(jié)點(diǎn)的時(shí)間，則PGPS依照Fi的順序調(diào)度各隊(duì)列中的包?？梢奝

21、GPS算法的實(shí)際效果同加權(quán)公平排隊(duì)策略完全一樣。PGPS的意義在于：在采用漏桶算法限制各個(gè)業(yè)務(wù)時(shí)，網(wǎng)絡(luò)能夠提供一個(gè)端到端時(shí)延的理論上限。 自定時(shí)公平排隊(duì)策略自定時(shí)公平排隊(duì)策略(Self Clocked Fair Queuing; SCFQ)前述幾種方案的缺點(diǎn)在于難于實(shí)現(xiàn)，計(jì)算復(fù)雜前述幾種方案的缺點(diǎn)在于難于實(shí)現(xiàn)，計(jì)算復(fù)雜；需要跟蹤；需要跟蹤GPS；緩存器管理復(fù)雜。；緩存器管理復(fù)雜。在在SCFQ調(diào)度方式中，時(shí)標(biāo)是依照實(shí)時(shí)系統(tǒng)的事調(diào)度方式中，時(shí)標(biāo)是依照實(shí)時(shí)系統(tǒng)的事件計(jì)算，而非參照件計(jì)算，而非參照GPS系統(tǒng)，所以不必跟蹤理系統(tǒng)，所以不必跟蹤理想想GPS系統(tǒng)的過程，它是一個(gè)低復(fù)雜度和系統(tǒng)的過程，它是一個(gè)

22、低復(fù)雜度和GPS近似程度的折衷，所以其時(shí)延特性不如近似程度的折衷，所以其時(shí)延特性不如GPS嚴(yán)嚴(yán)格。格。 6.3調(diào)度策略調(diào)度策略-WF2Q調(diào)度算法對(duì)WFQ做了改進(jìn)，WFQ算法的調(diào)度原則是根據(jù)GPS算法計(jì)算出的調(diào)度順序調(diào)度包；而WF2Q調(diào)度算法的基本原則仍然是根據(jù)GPS算法計(jì)算的順序調(diào)度包，但是采用GPS算法調(diào)度時(shí)，已開始發(fā)送的包優(yōu)先 WF2Q(Worst-case Fair Weighted Fair Queueing) 6.3調(diào)度策略調(diào)度策略- Stop-and-Go Stop-and-Go最早由貝爾通信研究所的J.Golestani提出，目的在于在網(wǎng)絡(luò)的節(jié)點(diǎn)上保持業(yè)務(wù)的平滑特性，防止突發(fā)的形

23、成，提供時(shí)延和包丟失率的保證。采用Stop-and-Go調(diào)度策略時(shí)，端到端的傳輸速率在連接建立時(shí)就根據(jù)可用的網(wǎng)絡(luò)資源確定了，Stop-and-Go由在源節(jié)點(diǎn)上的每一個(gè)連接的接入控制策略（在時(shí)間間隔T內(nèi)每一流發(fā)送的數(shù)據(jù)不能超過r比特）和內(nèi)部節(jié)點(diǎn)上的特殊服務(wù)策略組成。Stop-and-Go采用幀結(jié)構(gòu)，將時(shí)間軸分成長度為T的幀。所有在一個(gè)給定幀內(nèi)到達(dá)的包都將在下一幀內(nèi)發(fā)送，以保證業(yè)務(wù)的平滑特性，防止突發(fā)形成。傳輸時(shí)延抖動(dòng)也可控制在一定范圍內(nèi)。 6.3調(diào)度策略調(diào)度策略-調(diào)度算法調(diào)度算法公平性公平性時(shí)延特性時(shí)延特性運(yùn)算復(fù)雜度運(yùn)算復(fù)雜度適用場(chǎng)合適用場(chǎng)合帶寬利用率帶寬利用率FCFS差小低Best Effor

24、t高優(yōu)先排隊(duì)策略差小適中混合業(yè)務(wù)高PRR差不確定低定長包交換系統(tǒng)高BBRR好難以實(shí)現(xiàn)WRR好不確定難以實(shí)現(xiàn)WFQ好不確定高Best Effort高SFQ好不確定低Best Effort高DRR好不確定低Best Effort高Virtual Clock較好提供端到端時(shí)延上界高定長包交換系統(tǒng)高GPS好小難以實(shí)現(xiàn)PGPS好小高混合業(yè)務(wù)高FIFO+較好提供端到端時(shí)延上界高混合業(yè)務(wù)高WF2Q好不確定高混合業(yè)務(wù)高EDF差提供單節(jié)點(diǎn)時(shí)延上界高混合業(yè)務(wù)高SCED較好提供端到端時(shí)延上界高混合業(yè)務(wù)高Stop-and-Go差提供單節(jié)點(diǎn)時(shí)延上界較低混合業(yè)務(wù)低6.3調(diào)度策略調(diào)度策略-WF2Q(Worst-case F

25、air Weighted Fair Queueing) 圖3.6 相同輸入模型下，GPS、WFQ和WF2Q調(diào)度方式的比較（a）（b）（c）（d）輸入鏈路Hash變換器Q0Q1Qm輪詢調(diào)度輸出隊(duì)列控制器補(bǔ)償性輪詢調(diào)度算法的原理框圖補(bǔ)償性輪詢調(diào)度算法的原理框圖 （Compensating Round Robin; CRR）6.3調(diào)度策略調(diào)度策略- 6.3調(diào)度策略調(diào)度策略- STi 門限T 5 200 800 160 560 640 64 64 160 64 64 640 320 200 560 64 64 160 320Q1Q4Q3 (無整包)Qm-1From Q1From Q4From Q2Fr

26、om Qm-1 720From Qm 調(diào)度機(jī)調(diào)度機(jī) 輸出緩存器輸出緩存器CiMax 800 720Qm 輸入隊(duì)列輸入隊(duì)列: 第一輪被調(diào)度輸出的包Q26.3調(diào)度策略調(diào)度策略-05101520Q u e u e sQ u e u e sPacket Loss RatePacket Loss RateFCFSCRR 非擁塞狀態(tài)下包丟失率的比較非擁塞狀態(tài)下包丟失率的比較(1+2+20= 0.9C,9=51) 10-7 10-6 10-5 10-4 10-3 丟包率丟包率隊(duì)列隊(duì)列 丟包率丟包率 擁塞狀態(tài)下包丟失率的比較擁塞狀態(tài)下包丟失率的比較(1+2+20= 2C,9=51) 00.20.40.60.8

27、105101520QueuesQueuesPacket Loss RatePacket Loss RateFCFSCRR隊(duì)列隊(duì)列 非擁塞狀態(tài)下采用各流獲得的帶寬非擁塞狀態(tài)下采用各流獲得的帶寬(1+2+20= 0.9C,9=51) 01234505101520FCFSCRR帶寬帶寬 (108 bps)隊(duì)列隊(duì)列 擁塞狀態(tài)下采用各流獲得的帶寬擁塞狀態(tài)下采用各流獲得的帶寬(1+2+20=2C ,9=51) 帶寬帶寬 (108 bps)0246805101520FCFSCRR隊(duì)列隊(duì)列 丟包率丟包率6.3調(diào)度策略調(diào)度策略-CRR調(diào)度算法對(duì)不同包長的流的公平性測(cè)試：調(diào)度算法對(duì)不同包長的流的公平性測(cè)試：CRR

28、調(diào)度算法對(duì)不同速率流的公平性測(cè)試：調(diào)度算法對(duì)不同速率流的公平性測(cè)試：6.3調(diào)度策略調(diào)度策略-6.3調(diào)度策略調(diào)度策略-6.3調(diào)度策略調(diào)度策略-CRR調(diào)度算法的優(yōu)缺點(diǎn)：調(diào)度算法的優(yōu)缺點(diǎn)： 公平特性好公平特性好 ( (FairnessIndexi 0.5,2) ) 運(yùn)算復(fù)雜度小運(yùn)算復(fù)雜度小 ( (處理一個(gè)包的運(yùn)算量為O（1）) ) 保證實(shí)時(shí)業(yè)務(wù)的時(shí)延特性需要緩存器管理策略保證實(shí)時(shí)業(yè)務(wù)的時(shí)延特性需要緩存器管理策略 的支持的支持 需要研究良好的緩存器管理策略需要研究良好的緩存器管理策略本本 章章 內(nèi)內(nèi) 容容n交換網(wǎng)絡(luò)的基本原理交換網(wǎng)絡(luò)的基本原理n交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類n調(diào)度策略調(diào)度策略n緩存器管理緩存

29、器管理n組播實(shí)現(xiàn)組播實(shí)現(xiàn)nQoS支持支持緩存（緩存（Buffering）網(wǎng)絡(luò)節(jié)點(diǎn)接收到達(dá)該節(jié)點(diǎn)的包，然后發(fā)送到相應(yīng)的目的線路上。如果在某些時(shí)間間隔內(nèi)，到達(dá)包的速率超過了輸出線路的速率，則需要對(duì)輸入報(bào)文進(jìn)行緩存。緩存器不能增加帶寬，但可增加帶寬的利用率，它就象一條河中的水庫，能吸收短時(shí)突發(fā)，利用線路空閑資源。主要的緩存技術(shù)有共享存儲(chǔ)器方式共享存儲(chǔ)器方式和每流單獨(dú)緩存方式每流單獨(dú)緩存方式緩存器的采用對(duì)傳送標(biāo)準(zhǔn)數(shù)據(jù)業(yè)務(wù)（如文件傳輸?shù)龋┓浅Ｓ欣莻魉湍切?duì)對(duì)時(shí)延敏感的多媒體業(yè)務(wù)時(shí)必須要特別注意，因?yàn)榫彺婕夹g(shù)是靠增加端到端的時(shí)延來提高帶寬利用率的。 6.3 緩存器管理緩存器管理6.3 緩存器管理緩存

30、器管理緩存器管理緩存器管理機(jī)制是在緩存器已滿或?qū)M時(shí)的丟包策略。緩存器管理機(jī)制僅僅在一個(gè)隊(duì)列中起作用，若有許多個(gè)隊(duì)列，各隊(duì)列可采用不同的丟包策略。緩存器管理主要有先到先丟(FIFD)、末尾丟棄（Drop Tail）、隨機(jī)早期探測(cè)（Random Early Detection, RED）、標(biāo)記隨機(jī)早期探測(cè)（RED with IN and OUT bit; RIO）和加權(quán)隨機(jī)早期探測(cè)（Weighted RED ；WRED）機(jī)制。 每流單獨(dú)緩存 調(diào)度機(jī) 調(diào)度機(jī) 輸出 輸出 輸入 輸入 圖3.1 共享存儲(chǔ)器緩存技術(shù)和每流單獨(dú)緩存技術(shù)共享存儲(chǔ)器：流1；：流2；：流3；：流4共享存儲(chǔ)器緩存技術(shù)和每流單獨(dú)緩存技術(shù) 共享存儲(chǔ)器緩存技術(shù)和每流單獨(dú)緩存技術(shù)共享存儲(chǔ)器緩存技術(shù)和每流單獨(dú)緩存技術(shù)6.3 緩存器管理緩存器管理 標(biāo)記隨機(jī)早期探測(cè) (RIO) 調(diào)度機(jī)輸出 輸入末尾丟棄 (Drop Tail)隨機(jī)早期探測(cè) (RED) 輸入 輸入 調(diào)度機(jī)輸