路由器原理與設(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ù)臺操作維護(hù)臺外部接口外部接口本本 章章 內(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是一個交換矩陣，在同一時刻（時是一個交換矩陣，在同一時刻（時隙）每一個輸出只能連接到一個輸入上，因而當(dāng)隙）每一個輸出只能連接到一個輸入上，因而當(dāng)多個輸入往同一輸出端發(fā)包時，必須有緩存，根多個輸入往同一輸出端發(fā)包時，必須有緩存，根據(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ì)能提供很好的性能，但商用存儲器訪問速率的限制制約了其在高用存儲器訪問速率的限制制約了其在高速路由器中的使用速路由器中的使用6.2交換網(wǎng)絡(luò)分類交換網(wǎng)絡(luò)分類-優(yōu)點(diǎn)：不需要加速缺點(diǎn)：鏈頭（HOL）阻塞；對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、對每個輸出都在輸入端建立一個單獨(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)先級和公平調(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é)合配對uGSA（Gale-Shapley Algorithm）算法u利用定義的優(yōu)先級來調(diào)度分組，可以獲得好的吞吐率和時延限度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ò)分類 超摩爾定律 傳輸速率每九個月翻一番。結(jié)論：結(jié)論：處理速率的發(fā)展無法跟上傳輸速率發(fā)展的處理速率的發(fā)展無法跟上傳輸速率發(fā)展的步伐，因此采用并行交換結(jié)構(gòu)是高速路由器的必然步伐，因此采用并行交換結(jié)構(gòu)是高速路由器的必然趨勢。趨勢。 摩爾定律 CPU的處理速率每18個月將翻一番。 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)換每隔固定的時間變換一次每隔固定的時間變換一次不定長包交換：無法保

13、證每一路包的傳輸時間是不定長包交換：無法保證每一路包的傳輸時間是相等的，因此若用相等的，因此若用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)中的一個組件，它依照一定的調(diào)度算法選擇緩存隊(duì)列中最需要發(fā)送的包送到輸出鏈路上 包調(diào)度算法管理著最重要的網(wǎng)絡(luò)資源輸出鏈路帶寬。 良好的調(diào)度算法能夠隔離各個用

14、戶流，起到防火墻的作用，為路由器提供安全保障，保證正常使用網(wǎng)絡(luò)的用戶不受其他用戶有意或無意的干擾。 調(diào)度算法直接控制包的時延而緩存器管理控制包的丟失率，所以調(diào)度算法與緩存器管理策略控制著QoS中最重要的性能指標(biāo)時延和丟包率。 時延和丟包率是密切相關(guān)的，對一個業(yè)務(wù)流，分配給它的帶寬越多，它需要的緩存空間越小，另外，大的包時延容易導(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)度算法時，只有緩存器中沒有待發(fā)送的包時，輸出鏈路才會空閑 非盡職工作型調(diào)度算法則可能在緩存器中還有包時，輸出鏈路空閑。 盡職工作型調(diào)度算法可以最大限度地利用輸出鏈路的帶寬資源 非盡職工作型調(diào)度算法在控制時延抖動時往往是一種較好的選擇，即包可以進(jìn)行時延以滿足特定的時延要求。 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)上時延上界的調(diào)度策略基于保證單節(jié)點(diǎn)上時延上界的調(diào)度策略 ( (EDF、Stop-and

16、-Go) )基于保證端到端時延上界的調(diào)度策略基于保證端到端時延上界的調(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ì)列中，然后逐個的思想是在每一網(wǎng)絡(luò)節(jié)點(diǎn)上將不同流放入不同的隊(duì)列中，然后逐個輪詢調(diào)度輸出各隊(duì)列的包，跳過空隊(duì)列，若有多個活動的流，則每個隊(duì)列每一輪詢調(diào)度輸出各隊(duì)列的包，跳過空隊(duì)列，若有多個活動的流，則每個隊(duì)列每一輪詢周期發(fā)送一個包輪詢周期發(fā)送一個包 圖3.4 逐包調(diào)度策略示意圖

17、加權(quán)公平排隊(duì)策略（加權(quán)公平排隊(duì)策略（Weighted Fair Queuing）Demers，Keshav和Shenker對Nagle的算法進(jìn)行了改進(jìn)，提出了逐比特輪詢調(diào)度算法逐比特輪詢調(diào)度算法（Bit-by-bit Round Robin Service; BBRR），輪詢機(jī)每一輪從每一隊(duì)列中調(diào)度一比特而非一個包，因而解決了包長不同帶來的不公平，但這僅僅是一個理論分析方法，因?yàn)榘l(fā)送時不可能將包打碎。加權(quán)逐比特輪詢調(diào)度算法加權(quán)逐比特輪詢調(diào)度算法 當(dāng)輪詢到某一隊(duì)列時，從該隊(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策略時，第i個隊(duì)列中的包最后一比特被調(diào)度出去的時間；2.比較各個隊(duì)列Fi的大小。若FjFi (i=1,2, ,K, ij) 則調(diào)度第j個隊(duì)列中的一個包輸出。FjCi，則將該輪應(yīng)發(fā)的字節(jié)數(shù)N儲蓄起來，留到下一輪使用，轉(zhuǎn)到下一隊(duì)列；(d) 如果輪詢到隊(duì)列i時，隊(duì)列是空的，則將計(jì)數(shù)器Ci清零，這一做法是為了不讓Ci無限增大，雖然顯得不很公平，但是卻能夠防止突發(fā)的形成和對其他隊(duì)列的影響。DRR算法中，每個隊(duì)列的計(jì)數(shù)器記錄了輪詢機(jī)虧欠該隊(duì)列的字節(jié)數(shù)，因此稱為欠帳式輪詢調(diào)度算法。6.3調(diào)度策略調(diào)度策略-虛時鐘（虛時鐘（Virtual Clock）調(diào)度算法

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

20、果某一流按照約定的速率發(fā)包，則虛時鐘的跳變時刻就在實(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)度算法時第i個隊(duì)列中包P的最后一個比特離開節(jié)點(diǎn)的時間，則PGPS依照Fi的順序調(diào)度各隊(duì)列中的包。可見P

21、GPS算法的實(shí)際效果同加權(quán)公平排隊(duì)策略完全一樣。PGPS的意義在于：在采用漏桶算法限制各個業(yè)務(wù)時，網(wǎng)絡(luò)能夠提供一個端到端時延的理論上限。 自定時公平排隊(duì)策略自定時公平排隊(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)度方式中，時標(biāo)是依照實(shí)時系統(tǒng)的事調(diào)度方式中，時標(biāo)是依照實(shí)時系統(tǒng)的事件計(jì)算，而非參照件計(jì)算，而非參照GPS系統(tǒng)，所以不必跟蹤理系統(tǒng)，所以不必跟蹤理想想GPS系統(tǒng)的過程，它是一個低復(fù)雜度和系統(tǒng)的過程，它是一個

22、低復(fù)雜度和GPS近似程度的折衷，所以其時延特性不如近似程度的折衷，所以其時延特性不如GPS嚴(yán)嚴(yán)格。格。 6.3調(diào)度策略調(diào)度策略-WF2Q調(diào)度算法對WFQ做了改進(jìn)，WFQ算法的調(diào)度原則是根據(jù)GPS算法計(jì)算出的調(diào)度順序調(diào)度包；而WF2Q調(diào)度算法的基本原則仍然是根據(jù)GPS算法計(jì)算的順序調(diào)度包，但是采用GPS算法調(diào)度時，已開始發(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、成，提供時延和包丟失率的保證。采用Stop-and-Go調(diào)度策略時，端到端的傳輸速率在連接建立時就根據(jù)可用的網(wǎng)絡(luò)資源確定了，Stop-and-Go由在源節(jié)點(diǎn)上的每一個連接的接入控制策略（在時間間隔T內(nèi)每一流發(fā)送的數(shù)據(jù)不能超過r比特）和內(nèi)部節(jié)點(diǎn)上的特殊服務(wù)策略組成。Stop-and-Go采用幀結(jié)構(gòu)，將時間軸分成長度為T的幀。所有在一個給定幀內(nèi)到達(dá)的包都將在下一幀內(nèi)發(fā)送，以保證業(yè)務(wù)的平滑特性，防止突發(fā)形成。傳輸時延抖動也可控制在一定范圍內(nèi)。 6.3調(diào)度策略調(diào)度策略-調(diào)度算法調(diào)度算法公平性公平性時延特性時延特性運(yùn)算復(fù)雜度運(yùn)算復(fù)雜度適用場合適用場合帶寬利用率帶寬利用率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較好提供端到端時延上界高定長包交換系統(tǒng)高GPS好小難以實(shí)現(xiàn)PGPS好小高混合業(yè)務(wù)高FIFO+較好提供端到端時延上界高混合業(yè)務(wù)高WF2Q好不確定高混合業(yè)務(wù)高EDF差提供單節(jié)點(diǎn)時延上界高混合業(yè)務(wù)高SCED較好提供端到端時延上界高混合業(yè)務(wù)高Stop-and-Go差提供單節(jié)點(diǎn)時延上界較低混合業(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)度算法對不同包長的流的公平性測試：調(diào)度算法對不同包長的流的公平性測試：CRR

28、調(diào)度算法對不同速率流的公平性測試：調(diào)度算法對不同速率流的公平性測試：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ù)雜度小 ( (處理一個包的運(yùn)算量為O（1）) ) 保證實(shí)時業(yè)務(wù)的時延特性需要緩存器管理策略保證實(shí)時業(yè)務(wù)的時延特性需要緩存器管理策略 的支持的支持 需要研究良好的緩存器管理策略需要研究良好的緩存器管理策略本本 章章 內(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)的目的線路上。如果在某些時間間隔內(nèi)，到達(dá)包的速率超過了輸出線路的速率，則需要對輸入報(bào)文進(jìn)行緩存。緩存器不能增加帶寬，但可增加帶寬的利用率，它就象一條河中的水庫，能吸收短時突發(fā)，利用線路空閑資源。主要的緩存技術(shù)有共享存儲器方式共享存儲器方式和每流單獨(dú)緩存方式每流單獨(dú)緩存方式緩存器的采用對傳送標(biāo)準(zhǔn)數(shù)據(jù)業(yè)務(wù)（如文件傳輸?shù)龋┓浅Ｓ欣?，但是傳送那些對對時延敏感的多媒體業(yè)務(wù)時必須要特別注意，因?yàn)榫彺婕夹g(shù)是靠增加端到端的時延來提高帶寬利用率的。 6.3 緩存器管理緩存器管理6.3 緩存器管理緩存

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