1.FIFO調(diào)度

FIFO(First In Forst Out)調(diào)度使用的是FCFS策略，是一種不考慮QoS的調(diào)度算法。FIFO調(diào)度不進(jìn)行報(bào)文分類，所有業(yè)務(wù)共用一個(gè)隊(duì)列，按照請(qǐng)求進(jìn)入隊(duì)列順序進(jìn)行調(diào)度。如下圖所示，三種不同業(yè)務(wù)的請(qǐng)求全部加入到一個(gè)隊(duì)列中，按照FIFO的規(guī)則進(jìn)行調(diào)度。

FIFO調(diào)度實(shí)現(xiàn)簡(jiǎn)單、開銷小，但是FIFO不區(qū)分請(qǐng)求類型、不考慮QoS，對(duì)時(shí)延、抖動(dòng)敏感的業(yè)務(wù)不友好，無(wú)法保證關(guān)鍵業(yè)務(wù)服務(wù)質(zhì)量。

2.SP調(diào)度

SP(Strict Priority)嚴(yán)格優(yōu)先級(jí)調(diào)度嚴(yán)格按照隊(duì)列優(yōu)先級(jí)進(jìn)行調(diào)度，只有在高優(yōu)先級(jí)隊(duì)列中請(qǐng)求全部調(diào)度完成的情況下，才會(huì)考慮調(diào)度低優(yōu)先級(jí)隊(duì)列中的請(qǐng)求。如下圖所示，三種不同業(yè)務(wù)分別對(duì)應(yīng)三種不同優(yōu)先級(jí)的隊(duì)列：高優(yōu)隊(duì)列、中優(yōu)隊(duì)列和低優(yōu)隊(duì)列。不同業(yè)務(wù)的請(qǐng)求分別加入到相應(yīng)優(yōu)先級(jí)隊(duì)列中，調(diào)度時(shí)優(yōu)先調(diào)度高優(yōu)隊(duì)列請(qǐng)求，高優(yōu)隊(duì)列中請(qǐng)求調(diào)度完成后，依次調(diào)度中優(yōu)和低優(yōu)隊(duì)列請(qǐng)求。

SP調(diào)度算法的實(shí)現(xiàn)比較簡(jiǎn)單，優(yōu)點(diǎn)是可以保證關(guān)鍵業(yè)務(wù)可以優(yōu)先調(diào)度到，可以最大限度的降低網(wǎng)絡(luò)延遲和抖動(dòng)；缺點(diǎn)是網(wǎng)絡(luò)擁塞，高優(yōu)先級(jí)隊(duì)列中一直有請(qǐng)求時(shí)，會(huì)導(dǎo)致低優(yōu)先級(jí)隊(duì)列中請(qǐng)求一直調(diào)度不到，出現(xiàn)“餓死”的情況。

3.RR調(diào)度

RR(Round Robin)輪詢調(diào)度通常采用分時(shí)機(jī)制，為每個(gè)隊(duì)列分配一個(gè)時(shí)間片或調(diào)度時(shí)刻。RR調(diào)度按照固定順序循環(huán)調(diào)度每一個(gè)隊(duì)列中的請(qǐng)求，每次調(diào)度相同數(shù)量（一般是1個(gè)）的請(qǐng)求，且在調(diào)度過(guò)程中不考慮任何優(yōu)先級(jí)。算法較為簡(jiǎn)單且容易實(shí)現(xiàn)，同時(shí)不會(huì)產(chǎn)生“餓死”問(wèn)題。如下圖所示，RR調(diào)度輪詢調(diào)度隊(duì)列1/2/3中的請(qǐng)求，每次調(diào)度一個(gè)隊(duì)列中的一個(gè)請(qǐng)求，直到請(qǐng)求調(diào)度完成。

RR調(diào)度假設(shè)所有隊(duì)列的優(yōu)先級(jí)和帶寬需求都是相同的，調(diào)度時(shí)不考慮包長(zhǎng)、隊(duì)列時(shí)延和帶寬需求。隊(duì)列包長(zhǎng)差異比較大時(shí)，可能導(dǎo)致不同隊(duì)列實(shí)際占用帶寬差異巨大，同時(shí)因?yàn)椴豢紤]時(shí)延和帶寬需求，導(dǎo)致無(wú)法做到對(duì)網(wǎng)絡(luò)流量的精準(zhǔn)隔離和調(diào)度。

4.WRR調(diào)度

輪詢調(diào)度保證了各隊(duì)列在請(qǐng)求調(diào)度時(shí)的公平性，但是無(wú)法滿足個(gè)性化的調(diào)度需求。WRR(Weighted Round Robin)加權(quán)輪詢調(diào)度在輪詢的基礎(chǔ)上為隊(duì)列增加權(quán)重，每個(gè)隊(duì)列設(shè)置一個(gè)計(jì)數(shù)器，根據(jù)權(quán)重初始化計(jì)數(shù)器初始值，每調(diào)度一個(gè)報(bào)文，計(jì)數(shù)器減1。權(quán)重越大，每次輪詢調(diào)度次數(shù)越多，能調(diào)度的包數(shù)量也就越多。如下圖所示，三個(gè)隊(duì)列權(quán)重分別是3:2:1，每一輪調(diào)度的包數(shù)量比例就是3:2:1。

當(dāng)所有隊(duì)列權(quán)重值都是1時(shí)，WRR調(diào)度退化為RR調(diào)度。WRR的優(yōu)點(diǎn)是可以按比例調(diào)度各個(gè)隊(duì)列的請(qǐng)求，適應(yīng)性更強(qiáng)，但是由于調(diào)度時(shí)沒(méi)有考慮包長(zhǎng)，還是按照請(qǐng)求個(gè)數(shù)進(jìn)行調(diào)度，在請(qǐng)求長(zhǎng)度變化時(shí)無(wú)法保證各隊(duì)列按照設(shè)置比例占用帶寬，而用戶一般關(guān)心和感知到的是帶寬。此外隊(duì)列請(qǐng)求長(zhǎng)度不一致時(shí)，WRR調(diào)度對(duì)請(qǐng)求長(zhǎng)度較小的隊(duì)列帶來(lái)不公平性。

5.DWRR調(diào)度

為了解決隊(duì)列請(qǐng)求長(zhǎng)度不一致帶來(lái)的不公平性，DWRR(Deficit Weighted Round Robin)差分加權(quán)輪詢調(diào)度在WRR基礎(chǔ)上，基于請(qǐng)求長(zhǎng)度而非請(qǐng)求個(gè)數(shù)設(shè)置權(quán)值，按照權(quán)重和請(qǐng)求長(zhǎng)度進(jìn)行調(diào)度。DWRR為每個(gè)隊(duì)列設(shè)置一個(gè)計(jì)數(shù)器，計(jì)數(shù)器初始化為weight * MTU，每次調(diào)度計(jì)數(shù)器減去請(qǐng)求長(zhǎng)度。具體算法邏輯如下：

1. 初始化隊(duì)列計(jì)數(shù)器DC = weight * MTU；
2. 調(diào)度器輪詢非空隊(duì)列，如果隊(duì)列DC <= 0，則跳過(guò)輪詢下一個(gè)隊(duì)列；
3. 調(diào)度隊(duì)列請(qǐng)求，計(jì)數(shù)器DC = DC - request_len；
4. 所有隊(duì)列DC < 0或無(wú)請(qǐng)求調(diào)度時(shí)，DC = DC + weight * MTU。

DWRR調(diào)度克服了請(qǐng)求長(zhǎng)度變化帶來(lái)的不公平性，提供了更為精準(zhǔn)的帶寬分配。但是隊(duì)列數(shù)量較大或者M(jìn)TU設(shè)置較大時(shí)，調(diào)度器完成一輪調(diào)度的時(shí)間可能比較長(zhǎng)，這樣可能會(huì)引發(fā)較大的傳輸時(shí)延抖動(dòng)，此外DWRR調(diào)度無(wú)法滿足高優(yōu)隊(duì)列優(yōu)先調(diào)度的需求。

6.SP+DWRR調(diào)度

SP調(diào)度可能出現(xiàn)“餓死”問(wèn)題，同時(shí)不能實(shí)現(xiàn)帶寬按比例調(diào)度；而DWRR調(diào)度可以實(shí)現(xiàn)帶寬的按比例調(diào)度，同時(shí)解決了“餓死”問(wèn)題，但是無(wú)法滿足高優(yōu)業(yè)務(wù)優(yōu)先調(diào)度的需求。因此結(jié)合SP調(diào)度和DWRR調(diào)度的優(yōu)點(diǎn)，實(shí)現(xiàn)SP+DWRR的調(diào)度。調(diào)度時(shí)優(yōu)先保證SP調(diào)度，在高優(yōu)隊(duì)列無(wú)請(qǐng)求調(diào)度時(shí)，才嘗試調(diào)度低優(yōu)隊(duì)列請(qǐng)求。如下圖所示，SP調(diào)度高優(yōu)隊(duì)列、低優(yōu)隊(duì)列和普通隊(duì)列，隊(duì)列優(yōu)先級(jí)為：高優(yōu)隊(duì)列 > 普通隊(duì)列 > 低優(yōu)隊(duì)列。

隊(duì)列1/2/3按照配置權(quán)重值進(jìn)行DWRR調(diào)度，高優(yōu)隊(duì)列、低優(yōu)隊(duì)列和普通隊(duì)列間按照SP算法進(jìn)行調(diào)度。高優(yōu)隊(duì)列無(wú)請(qǐng)求調(diào)度時(shí)，嘗試調(diào)用普通隊(duì)列組內(nèi)的請(qǐng)求，在普通隊(duì)列組內(nèi)所有隊(duì)列均無(wú)請(qǐng)求時(shí)，才調(diào)度低優(yōu)隊(duì)列請(qǐng)求。