發(fā)布時(shí)間：2017-08-27 00:01

  本文關(guān)鍵詞：輸入隊(duì)列交換機(jī)迭代調(diào)度算法研究設(shè)計(jì)

  更多相關(guān)文章： 輸入隊(duì)列交換機(jī) 迭代調(diào)度算法 分布式調(diào)度 往返時(shí)間 數(shù)據(jù)包時(shí)延

【摘要】：互聯(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ù)包,無需加速,更適合于高速實(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)而生。本文主要對輸入隊(duì)列交換機(jī)的集中式和分布式迭代調(diào)度算法兩大方面進(jìn)行了探討。首先,本文研究了輸入隊(duì)列交換機(jī)的集中式迭代調(diào)度算法。迭代調(diào)度算法能取得極大尺寸匹配(Maximal Size Matching, MSM),是當(dāng)前應(yīng)用最廣泛的調(diào)度算法。迭代調(diào)度算法通常由請求、授權(quán)和接受三個(gè)階段組成,雖然有些迭代調(diào)度算法能取得很好的性能,但是依然存在提升的空間。本文首先對已有算法RR/LQF(Round Robin with Longest Queue First)進(jìn)行了兩方面的改進(jìn)。一方面,對請求階段進(jìn)行了調(diào)整,極大程度地降低了時(shí)延,提升了性能。另一方面,在復(fù)雜度上,提出了一種流水線更新數(shù)據(jù)包計(jì)數(shù)器的機(jī)制,將其復(fù)雜度從O(NlogN)降低為O(logN),更適合于高速擴(kuò)展。其次,本文提出了一種最大-最小公平的集中式迭代調(diào)度算法GRR/LRR (Global Round Robin with Local Round Robin)。GRR/LRR首先采用全局輪詢調(diào)度,即優(yōu)先輸入-輸出對,來最大化匹配尺寸,當(dāng)全局輪詢失敗時(shí),進(jìn)一步通過每個(gè)端口的局部輪詢指針來進(jìn)行調(diào)度。GRR/LRR的復(fù)雜度僅為0(1)。當(dāng)GRR/LRR執(zhí)行一次迭代時(shí),能獲得比其他相同復(fù)雜度和通信開銷的算法更好的性能。當(dāng)GRR/LRR執(zhí)行多至N次迭代時(shí),我們證明它只需2-1/N倍加速即可達(dá)到穩(wěn)定。最重要的是,GRR/LRR在任何數(shù)據(jù)源下均能滿足最大-最小公平性規(guī)則。最后,本文研究了輸入隊(duì)列交換機(jī)的分布式迭代調(diào)度算法。當(dāng)交換機(jī)的單邊端口數(shù)目超過64時(shí),集中式調(diào)度器受其I/O接口的限制已無法實(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。為了打破這一瓶頸,本文提出了一種請求預(yù)測(Request Prediction, RP)機(jī)制,當(dāng)其應(yīng)用于很多迭代調(diào)度算法時(shí),能將低負(fù)載時(shí)延降低至RTT以下。這種請求預(yù)測的思想非常簡單,復(fù)雜度僅為O(1),而且應(yīng)用于不同的調(diào)度算法時(shí)可進(jìn)行不同的調(diào)整以獲取更好的性能。
【關(guān)鍵詞】：輸入隊(duì)列交換機(jī) 迭代調(diào)度算法 分布式調(diào)度 往返時(shí)間 數(shù)據(jù)包時(shí)延
【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TN915.05
【目錄】：

• 致謝4-6
• 摘要6-8
• Abstract8-13
• 第1章 緒論13-21
• 1.1 高速單芯片交換機(jī)設(shè)計(jì)13
• 1.2 交換機(jī)架構(gòu)13-15
• 1.3 輸入隊(duì)列交換機(jī)的迭代調(diào)度算法15-19
• 1.3.1 單比特單次迭代算法16-17
• 1.3.2 單比特多次迭代算法17
• 1.3.3 多比特單次迭代算法17-18
• 1.3.4 多比特多次迭代算法18
• 1.3.5 迭代調(diào)度算法的設(shè)計(jì)18-19
• 1.4 本文的工作19-20
• 1.5 本文的結(jié)構(gòu)20-21
• 第2章 集中式迭代調(diào)度算法RR/LQF的優(yōu)化21-29
• 2.1 RR/LQF21-22
• 2.2 RR/LQF的優(yōu)化22-24
• 2.2.1 時(shí)延吞吐量性能的優(yōu)化22-23
• 2.2.2 流水線重排序機(jī)制降低復(fù)雜度23-24
• 2.3 仿真結(jié)果24-28
• 2.3.1 均勻數(shù)據(jù)源25
• 2.3.2 突發(fā)數(shù)據(jù)源25-26
• 2.3.3 熱點(diǎn)數(shù)據(jù)源26-28
• 2.3.4 流水線重排序機(jī)制對比28
• 2.4 本章總結(jié)28-29
• 第3章 一種最大-最小公平的集中式迭代調(diào)度算法GRR/LRR29-44
• 3.1 迭代調(diào)度算法GRR/LRR30-31
• 3.1.1 GRR/LRR30-31
• 3.1.2 GRR/LRR與其他算法的比較31
• 3.2 GRR/LRR的穩(wěn)定性研究31-37
• 3.2.1 建立流體模型31-33
• 3.2.2 100%吞吐量證明33-37
• 3.3 GRR/LRR的最大-最小公平性研究37-39
• 3.4 仿真結(jié)果39-42
• 3.4.1 均勻數(shù)據(jù)源39-40
• 3.4.2 突發(fā)數(shù)據(jù)源40-42
• 3.4.3 熱點(diǎn)數(shù)據(jù)源42
• 3.5 本章小結(jié)42-44
• 第4章 分布式迭代調(diào)度算法研究44-61
• 4.1 現(xiàn)存分布式調(diào)度算法45-47
• 4.2 請求預(yù)測機(jī)制RP47-53
• 4.2.1 RP基本思想47-48
• 4.2.2 RP的具體實(shí)現(xiàn)48-49
• 4.2.3 RP應(yīng)用于RR/LQF49-50
• 4.2.4 RP應(yīng)用于HRF/RC50-52
• 4.2.5 RP應(yīng)用于其他的調(diào)度算法52-53
• 4.3 仿真結(jié)果53-56
• 4.3.1 均勻數(shù)據(jù)源53
• 4.3.2 突發(fā)數(shù)據(jù)源53-55
• 4.3.3 熱點(diǎn)數(shù)據(jù)源55-56
• 4.4 理論分析56-60
• 4.4.1 均勻數(shù)據(jù)源57-58
• 4.4.2 熱點(diǎn)數(shù)據(jù)源58-59
• 4.4.3 理論分析結(jié)果與仿真結(jié)果對比59-60
• 4.5 本章小結(jié)60-61
• 第5章 總結(jié)與展望61-64
• 參考文獻(xiàn)64-67
• 個(gè)人簡歷、在學(xué)期間的研究成果及發(fā)表的論文67

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 向哲,鐘玉琢,冼偉銓;一種基于周期合并策略的流調(diào)度算法[J];軟件學(xué)報(bào);2001年08期

2 伊鵬,張興明,郭云飛;基于輸入排隊(duì)的調(diào)度算法[J];計(jì)算機(jī)工程;2003年19期

3 易云山,桂志波;分組網(wǎng)絡(luò)中包調(diào)度算法研究[J];江蘇通信技術(shù);2004年03期

4 任艷穎,張文軍,王彬;無線調(diào)度算法[J];計(jì)算機(jī)工程;2004年15期

5 劉越洋,席裕庚;基于兩步滾動(dòng)的單機(jī)調(diào)度算法研究[J];計(jì)算機(jī)工程;2004年24期

6 楊梅樾;馬祥杰;;輸入排隊(duì)中調(diào)度算法的研究[J];信息工程大學(xué)學(xué)報(bào);2006年02期

7 曾東海;劉海;金士堯;;集群負(fù)載調(diào)度算法性能評價(jià)[J];計(jì)算機(jī)工程;2006年11期

8 孫力娟;李超;張登銀;王汝傳;;低速網(wǎng)絡(luò)中實(shí)時(shí)補(bǔ)償型差額循環(huán)調(diào)度算法的設(shè)計(jì)和實(shí)現(xiàn)[J];電子與信息學(xué)報(bào);2006年10期

9 劉東;張春元;;軟件容錯(cuò)模型中反向與正向調(diào)度算法研究[J];計(jì)算機(jī)工程與科學(xué);2007年09期

10 何琨;趙勇;黃文奇;;基于任務(wù)復(fù)制的分簇與調(diào)度算法[J];計(jì)算機(jī)學(xué)報(bào);2008年05期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前10條

1 彭洪;涂凍生;;面向操作的調(diào)度算法[A];1994中國控制與決策學(xué)術(shù)年會(huì)論文集[C];1994年

2 羅豪杰;許都;;IEEE 802.16 MAC層上行調(diào)度算法[A];四川省通信學(xué)會(huì)2007年學(xué)術(shù)年會(huì)論文集[C];2007年

3 張遵福;李樂民;;支持QoS的調(diào)度算法設(shè)計(jì)[A];2006中國西部青年通信學(xué)術(shù)會(huì)議論文集[C];2006年

4 姚建波;竺小松;李晶晶;;非對稱通信環(huán)境中兩種廣播調(diào)度算法的分析與比較[A];中國通信學(xué)會(huì)第六屆學(xué)術(shù)年會(huì)論文集（上）[C];2009年

5 景維鵬;吳智博;劉宏偉;董劍;;一種支持任務(wù)依賴關(guān)系容錯(cuò)調(diào)度算法[A];第十四屆全國容錯(cuò)計(jì)算學(xué)術(shù)會(huì)議(CFTC'2011)論文集[C];2011年

6 李琪林;甄威;周明天;;一種適用于Master-Worker應(yīng)用的動(dòng)態(tài)統(tǒng)一調(diào)度算法的研究[A];2008'中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（一）[C];2008年

7 呂鋒;涂曉東;;高性能交換結(jié)構(gòu)調(diào)度算法的研究[A];四川省通信學(xué)會(huì)2006年學(xué)術(shù)年會(huì)論文集（二）[C];2006年

8 趙爾敦;肖靜;;無線網(wǎng)絡(luò)中基于信道狀態(tài)預(yù)測的調(diào)度算法[A];2006全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文集[C];2006年

9 殷潔;;城市光網(wǎng)光纖自動(dòng)調(diào)度算法研究和應(yīng)用[A];中國通信學(xué)會(huì)信息通信網(wǎng)絡(luò)技術(shù)委員會(huì)2011年年會(huì)論文集（下冊）[C];2011年

10 陳平;王柏;徐六通;吳斌;王艷輝;;電信社群網(wǎng)絡(luò)中介度的網(wǎng)格并行算法及調(diào)度算法[A];2006年全國通信軟件學(xué)術(shù)會(huì)議論文集[C];2006年

中國重要報(bào)紙全文數(shù)據(jù)庫 前1條

1 張建輝 吳松;TD—SCDMA積跬步 HSDPA以致千里[N];通信產(chǎn)業(yè)報(bào);2005年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 劉曉鋒;可擴(kuò)展多級多平面交換網(wǎng)絡(luò)及調(diào)度算法研究[D];電子科技大學(xué);2015年

2 沈文楓;CPU-GPU異構(gòu)高性能計(jì)算中的負(fù)載預(yù)測調(diào)度算法研究及應(yīng)用[D];上海大學(xué);2016年

3 馬丹;任務(wù)間相互依賴的并行作業(yè)調(diào)度算法研究[D];華中科技大學(xué);2007年

4 田沖;無線網(wǎng)絡(luò)跨層調(diào)度算法研究[D];山東大學(xué);2009年

5 黃平;分布式交換系統(tǒng)隊(duì)列結(jié)構(gòu)及調(diào)度算法研究[D];華中科技大學(xué);2006年

6 劉惠;嵌入式系統(tǒng)節(jié)能調(diào)度算法研究[D];西安電子科技大學(xué);2011年

7 趙明宇;集群系統(tǒng)的調(diào)度算法研究[D];哈爾濱工業(yè)大學(xué);2007年

8 吳剛;對低功耗進(jìn)程調(diào)度算法的研究[D];復(fù)旦大學(xué);2006年

9 牛進(jìn)平;3G長期演進(jìn)系統(tǒng)中調(diào)度算法和干擾抑制技術(shù)研究[D];西安電子科技大學(xué);2014年

10 羅威;分布式實(shí)時(shí)容錯(cuò)調(diào)度算法研究[D];華中科技大學(xué);2008年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 丁雪飛;純電動(dòng)車整車CAN網(wǎng)絡(luò)實(shí)時(shí)調(diào)度算法的研究[D];遼寧大學(xué);2015年

2 王德龍;Hadoop平臺下作業(yè)調(diào)度算法的研究與改進(jìn)[D];南京信息工程大學(xué);2015年

3 袁林偉;載波聚合資源分配及調(diào)度算法研究[D];西南交通大學(xué);2015年

4 景木均;3GPP LTE系統(tǒng)中基于多目標(biāo)決策的下行資源調(diào)度算法研究與實(shí)現(xiàn)[D];西南交通大學(xué);2015年

5 劉盼紅;大數(shù)據(jù)環(huán)境下Hadoop作業(yè)調(diào)度算法的研究[D];河北工程大學(xué);2015年

6 楊軒;高鐵無線通信VoIP業(yè)務(wù)與多業(yè)務(wù)共存的資源調(diào)度算法[D];西南交通大學(xué);2015年

7 陳傳慶;基于衰落信道的無線鏈路調(diào)度算法研究[D];曲阜師范大學(xué);2015年

8 陳文龍;Hadoop平臺下作業(yè)調(diào)度方法研究[D];南京理工大學(xué);2015年

9 陳瑜;針對Hadoop集群的節(jié)能調(diào)度算法研究[D];電子科技大學(xué);2015年

10 朱新新;網(wǎng)絡(luò)端到端流量的QoS優(yōu)化技術(shù)研究[D];電子科技大學(xué);2014年

，

本文編號：743367