輸入隊(duì)列交換機(jī)迭代調(diào)度算法研究設(shè)計(jì).pdf

1、互聯(lián)網(wǎng)向云計(jì)算的持續(xù)轉(zhuǎn)變進(jìn)一步加劇了提高網(wǎng)絡(luò)帶寬的需求。在云計(jì)算架構(gòu)中，業(yè)務(wù)和數(shù)據(jù)存放于一個(gè)共享的數(shù)據(jù)中心，并通過互聯(lián)網(wǎng)被用戶所獲取。用戶和數(shù)據(jù)中心之間以及在一個(gè)數(shù)據(jù)中心的不同服務(wù)器間需要傳輸大量的流量。為了滿足互連高速低時(shí)延交換等要求，為多種流量需求設(shè)計(jì)一個(gè)統(tǒng)一的交換機(jī)架構(gòu)是非常可取的。數(shù)據(jù)交換機(jī)通常有兩種架構(gòu)，輸入隊(duì)列交換機(jī)和輸出隊(duì)列交換機(jī)。由于輸入隊(duì)列交換機(jī)每個(gè)時(shí)隙僅允許每個(gè)輸入/輸出端口發(fā)送/接受一個(gè)數(shù)據(jù)包，無(wú)需加速，更適合于高

2、速實(shí)現(xiàn)，因此也是目前應(yīng)用最廣泛的交換機(jī)架構(gòu)。輸入隊(duì)列交換機(jī)的調(diào)度算法是實(shí)現(xiàn)低時(shí)延、高吞吐量性能的關(guān)鍵。另外隨著交換機(jī)規(guī)模的增大，分布式調(diào)度也應(yīng)運(yùn)而生。
　　本研究主要內(nèi)容包括：⑴研究了輸入隊(duì)列交換機(jī)的集中式迭代調(diào)度算法。迭代調(diào)度算法能取得極大尺寸匹配（Maximal Size Matching, MSM)，是當(dāng)前應(yīng)用最廣泛的調(diào)度算法。迭代調(diào)度算法通常由請(qǐng)求、授權(quán)和接受三個(gè)階段組成，雖然有些迭代調(diào)度算法能取得很好的性能，但是依然存在

3、提升的空間。本文首先對(duì)巳有算法RR/LQF￡Round Robin with Longest Queue First)進(jìn)行了兩方面的改進(jìn)。一方面，對(duì)請(qǐng)求階段進(jìn)行了調(diào)整，極大程度地降低了時(shí)延，提升了性能。另一方面，在復(fù)雜度上，提出了一種流水線更新數(shù)據(jù)包計(jì)數(shù)器的機(jī)制，將其復(fù)雜度從降低為O(W＃)，更適合于高速擴(kuò)展。⑵提出了一種最大-最小公平的集中式迭代調(diào)度算法GRR/LRR(Global Round Robin with Local Rou

4、nd Robin)。GRR/LRR首先釆用全局輪詢調(diào)度，即優(yōu)先輸入-輸出對(duì)，來(lái)最大化匹配尺寸，當(dāng)全局輪詢失敗時(shí)，進(jìn)一步通過每個(gè)端口的局部輪詢指針來(lái)進(jìn)行調(diào)度。GRR/LRR的復(fù)雜度僅為0(1)。當(dāng)GRR/LRR執(zhí)行一次迭代時(shí)，能獲得比其他相同復(fù)雜度和通信開銷的算法更好的性能。當(dāng)GRR/LRR執(zhí)行多至＃次迭代時(shí)，我們證明它只需2-1/N倍加速即可達(dá)到穩(wěn)定。最重要的是，GRR/LRR在任何數(shù)據(jù)源下均能滿足最大-最小公平性規(guī)則。⑶研究了輸入隊(duì)列

5、交換機(jī)的分布式迭代調(diào)度算法。當(dāng)交換機(jī)的單邊端口數(shù)目超過64時(shí)，集中式調(diào)度器受其I/O接口的限制巳無(wú)法實(shí)現(xiàn)。因此需要釆用多芯片設(shè)計(jì)，在每個(gè)輸入輸出端口分布獨(dú)立的調(diào)度器/選擇器，即分布式調(diào)度器。此時(shí)，不同芯片之間的傳播時(shí)延導(dǎo)致輸入輸出端口之間存在很大的往返時(shí)間（Round Trip Time, RTT)，通常為多個(gè)時(shí)隙。在大部分現(xiàn)存的分布式調(diào)度算法中，數(shù)據(jù)包的最低排隊(duì)時(shí)延總是大于RTT。為了打破這一瓶頸，提出了一種請(qǐng)求預(yù)測(cè)（Request