九章業(yè)務(wù)量管理課件

1、第九章 業(yè)務(wù)量管理主要內(nèi)容業(yè)務(wù)量監(jiān)管分組調(diào)度隊(duì)列管理流量調(diào)節(jié)流量控制主要內(nèi)容業(yè)務(wù)量監(jiān)管分組調(diào)度隊(duì)列管理業(yè)務(wù)量監(jiān)管業(yè)務(wù)監(jiān)管：Traffic Policing對(duì)業(yè)務(wù)進(jìn)行監(jiān)視，以避免超過許可的服務(wù)質(zhì)量參數(shù)約定（平均速率，峰值速率、突發(fā)長(zhǎng)度等）通過業(yè)務(wù)監(jiān)管機(jī)制，可以對(duì)超過約定QoS參數(shù)業(yè)務(wù)的流量進(jìn)行調(diào)節(jié)業(yè)務(wù)監(jiān)管功能一般由位于網(wǎng)絡(luò)入口處的邊緣路由器上執(zhí)行實(shí)現(xiàn)機(jī)制漏桶算法 令牌桶算法漏桶算法應(yīng)用于分組傳輸?shù)穆┩八惴ㄆ交话l(fā)業(yè)務(wù)流不論輸入的速率為多大，輸出速率始終是常數(shù)漏桶算法算法過程1）將漏桶看做是一個(gè)有限長(zhǎng)度的隊(duì)列，以字節(jié)為單位計(jì)數(shù)，當(dāng)分組到達(dá)的時(shí)候，如果隊(duì)列中還有空間的話，就被添加到對(duì)列的尾部，否則該

2、分組將被丟棄2）在每一個(gè)嘀嗒周期，首先將計(jì)數(shù)器初始化為n，如果隊(duì)列中第一個(gè)分組的字節(jié)數(shù)少于計(jì)時(shí)器的當(dāng)前值，則將分組發(fā)送出去，并且將計(jì)數(shù)器減去該分組的字節(jié)數(shù)。然后對(duì)下一個(gè)分組執(zhí)行同樣的過程，直到出現(xiàn)計(jì)數(shù)器的值小于隊(duì)列中的分組的長(zhǎng)度為止。此時(shí)，傳輸過程終止，直到下一個(gè)嘀嗒再開始3）到達(dá)下一個(gè)嘀嗒的時(shí)候，計(jì)數(shù)器被重置，執(zhí)行步驟2），再次開始分組發(fā)送過程令牌桶算法算法過程1）每個(gè)令牌桶維護(hù)一個(gè)字節(jié)計(jì)數(shù)器，每隔T秒，計(jì)數(shù)器的值增加K字節(jié)，這就相當(dāng)于往桶中放一個(gè)令牌，一個(gè)令牌代表了傳輸K字節(jié)的權(quán)利，令牌速率為r=K/T（Bps）。假設(shè)桶的大小為b字節(jié)，當(dāng)計(jì)數(shù)器的值大于b字節(jié)時(shí)，就會(huì)發(fā)生溢出，需要注意的是，

3、這里溢出丟棄的是令牌，而不是數(shù)據(jù) 2）當(dāng)有分組等待發(fā)送時(shí)，如果計(jì)數(shù)器的值大于當(dāng)前分組的長(zhǎng)度，則發(fā)送該分組，并且將計(jì)數(shù)器的值減去分組長(zhǎng)度。如果還有分組等待發(fā)送，繼續(xù)執(zhí)行上面的過程，直到計(jì)數(shù)器的值小于分組長(zhǎng)度為止漏桶和令牌桶兩者都可以用于業(yè)務(wù)監(jiān)管，判斷一個(gè)流是否違反約定的參數(shù) 漏桶算法的輸出保持的是嚴(yán)格的均勻速率，不管業(yè)務(wù)流量的突發(fā)程度如何在漏桶算法中，不允許將空閑時(shí)的發(fā)送許可權(quán)保存起來以便發(fā)送大的突發(fā)數(shù)據(jù)（每個(gè)時(shí)鐘嘀嗒后，漏桶的字節(jié)計(jì)數(shù)器都將被重置）令牌桶算法在大量突發(fā)數(shù)據(jù)到來的時(shí)候，允許輸出流適當(dāng)?shù)募涌炜梢詫l(fā)送許可權(quán)保存起來，直到到達(dá)桶的最大尺寸。這也就意味著只要突發(fā)數(shù)據(jù)不超過桶的大小，就可

4、以一次發(fā)送出去 在漏桶算法中，桶中填充的是數(shù)據(jù)，所以當(dāng)桶填滿后將丟棄分組，而在令牌桶中，桶中填充的是令牌，所以當(dāng)桶填滿后將丟棄令牌，相當(dāng)于是傳輸許可，而不是分組6543210Arrival time at bucketDeparture time from a leaky bucketLeaky bucket rate = 1 packet / 2 time units65432106543210Departure time from a token bucketToken bucket rate = 1 token / 2 time unitsToken bucket size = 2 to

5、kens漏桶和令牌桶主要內(nèi)容業(yè)務(wù)量監(jiān)管分組調(diào)度隊(duì)列管理概述分組調(diào)度用于緩存區(qū)中的多個(gè)分組競(jìng)爭(zhēng)使用同一個(gè)輸出鏈路時(shí)使用什么樣的策略來選擇分組發(fā)送？該策略會(huì)對(duì)性能有什么影響？1990年代的一個(gè)熱點(diǎn)研究領(lǐng)域共享存儲(chǔ)交換占主導(dǎo)傳輸鏈路帶寬特別是骨干網(wǎng)鏈路帶寬是稀缺的資源路由器輸出緩存以隊(duì)列的方式進(jìn)行組織，調(diào)度主要對(duì)輸出隊(duì)列進(jìn)行調(diào)度可以更加有效地利用路由器有限的帶寬資源，以盡量滿足不同業(yè)務(wù)的需求設(shè)計(jì)考慮因素在設(shè)計(jì)調(diào)度算法時(shí)，應(yīng)該根據(jù)實(shí)際情況考慮三個(gè)因素優(yōu)先級(jí)（Priorization）：如果不同的流具有不同的QoS需求，需要使用優(yōu)先級(jí)來實(shí)現(xiàn)流區(qū)分。例如某些流可能需要更低的延遲，那么屬于這些流的分組將被優(yōu)

6、先調(diào)度公平性（Fairness）：不同流能夠平等地訪問網(wǎng)絡(luò)資源，也就是說這些流對(duì)于網(wǎng)絡(luò)資源具有相同的權(quán)利隔離（Protection）：對(duì)于以超過其分配帶寬發(fā)送分組的惡意流不應(yīng)該影響到其它正常流的性能算法先到先服務(wù)優(yōu)先級(jí)調(diào)度Round Robin公平調(diào)度GPS、FQ、WFQ等常用于具有QoS需求的場(chǎng)合先到先服務(wù)先到先服務(wù)（FCFS：First-Come-First Served）發(fā)送機(jī)會(huì)到來時(shí)，最先到達(dá)的分組具有最高的調(diào)度優(yōu)先級(jí)缺點(diǎn)：無法實(shí)現(xiàn)流區(qū)分，不支持基于流的優(yōu)先級(jí)，也無法保證公平性和隔離優(yōu)先級(jí)調(diào)度當(dāng)有比當(dāng)前正在發(fā)送分組優(yōu)先級(jí)更高的分組到達(dá)時(shí)，如何處理？繼續(xù)發(fā)送低優(yōu)先級(jí)分組，直到發(fā)送完成后再

7、處理高優(yōu)先級(jí)分組低優(yōu)先級(jí)分組被停止服務(wù)，重新放回隊(duì)列中或者被丟棄，開始發(fā)送高優(yōu)先級(jí)分組非搶占式調(diào)度搶占式調(diào)度Round RobinRound Robin調(diào)度到達(dá)輸出隊(duì)列的流被分成不同的隊(duì)列當(dāng)有發(fā)送機(jī)會(huì)到來時(shí)，采用輪詢的方式選擇隊(duì)列，并且從隊(duì)列中選擇分組發(fā)送 缺點(diǎn)：當(dāng)每個(gè)流的分組大小不同時(shí)，難以保證公平性隊(duì)列1：分組1，2，4隊(duì)列2：分組3，5Round Robin在Round Robin調(diào)度的過程中，如果某個(gè)隊(duì)列為空，如何處理？在分配給該隊(duì)列的時(shí)間內(nèi)鏈路保持空閑，也就是說即使隊(duì)列中沒有分組要發(fā)送，也在每一輪調(diào)度中都保留為該隊(duì)列分配的資源 直接轉(zhuǎn)到下一個(gè)隊(duì)列。也就就是說，只要有分組在隊(duì)列中等待發(fā)

8、送，鏈路就不會(huì)空閑non-work-conversing調(diào)度work-conversing調(diào)度公平調(diào)度公平（Fairness）不是指用戶分配相同份額的資源，而是指每個(gè)用戶對(duì)資源具有相同的訪問權(quán)利問題：如果系統(tǒng)沒有足夠的資源滿足所有用戶的需求，并且某些用戶可能比其他用戶需要更少的資源。在保證公平的情況下如何分配資源？ Max-Min公平共享：首先要滿足那些需求小于它們可以得到部分的用戶，然后將多余的資源在那些需求更大的用戶之間平均分配 可以證明，在Round Robin調(diào)度算法中，如果每個(gè)隊(duì)列中的分組大小都相等，則滿足Max-Min公平共享Max-Min公平共享定義資源按照遞增的順序分配沒有用戶

9、獲得大于其所需的資源無法滿足需求的用戶獲得相同的資源分配過程假設(shè)系統(tǒng)總資源R用戶集合1，2， n對(duì)應(yīng)的資源需求r1，r2，rn，r1r2= maxth then mark or drop the packet else if minth= avgQ 0)wq：RED對(duì)擁塞的反應(yīng)程度過大，不能過濾由于突發(fā)導(dǎo)致的短暫擁塞過小，對(duì)實(shí)際隊(duì)列長(zhǎng)度反應(yīng)過慢，不能有效地檢測(cè)擁塞avgQ = (1-wq)mavgQ (if q=0)m=queue_idle_time/typical_transmission_timeWq: 由路由器或者交換機(jī)允許的突發(fā)業(yè)務(wù)大小和持續(xù)時(shí)間決定RED計(jì)算標(biāo)記（丟棄）概率方法1：P

10、b = maxp*(avgQ-minth)/(maxth-minth) maxth-minth應(yīng)該大于一個(gè)往返時(shí)間內(nèi)平均隊(duì) 列的增加值，以避免由于丟棄過多的分組而導(dǎo)致全局同步一般將maxth設(shè)置為minth的2倍方法2：P = Pb/(1-count*Pb) count:上一次丟棄到現(xiàn)在進(jìn)入隊(duì)列的分組數(shù)量，實(shí)現(xiàn)均勻分組間隔地丟包，避免對(duì)突發(fā)流的偏見和產(chǎn)生全局同步現(xiàn)象Average Queue Length01minthmaxthmaxp在假設(shè)平均隊(duì)列長(zhǎng)度為常數(shù)的情況下，丟棄概率的選擇應(yīng)該使得分組丟棄間隔盡量均勻避免對(duì)突發(fā)業(yè)務(wù)流的偏見避免產(chǎn)生全局同步現(xiàn)象X：連續(xù)兩次分組丟棄之間到達(dá)分組數(shù)量（包括

11、后一次丟棄分組）1）直接使用Pb計(jì)算丟棄概率2）在計(jì)算丟棄概率時(shí)考慮count均勻間隔丟棄RED性能分析TimeMax Queue Sizemax_thmin_thForced dropProbabilistic dropsNo dropsDrop probabilityAverage queue length丟棄概率依賴于擁塞程度，并且均勻間隔丟棄，避免了由于分組連續(xù)丟棄導(dǎo)致的全局同步現(xiàn)象發(fā)生擁塞時(shí)，丟棄某個(gè)流的分組的概率基本上與該流在路由器或者交換機(jī)上獲得的帶寬成比例平均隊(duì)列超過閾值后就開始丟棄分組，有效地控制了平均隊(duì)列長(zhǎng)度，限制了平均延遲，并且允許一定程度的突發(fā)分組RED參數(shù)設(shè)置問題RED的參數(shù)的微小變化會(huì)給總體性能帶來很大的影響，與特定的業(yè)務(wù)環(huán)境相關(guān)不能有效估計(jì)擁塞的嚴(yán)重性從路由器或者交換機(jī)開始丟棄分組到源端檢查到丟棄從而做出反應(yīng)，可能需要很長(zhǎng)的時(shí)間，RED