【摘要】：2D-Mesh網(wǎng)絡(luò)由于結(jié)構(gòu)簡(jiǎn)單且易于構(gòu)造以及較低的維度,并且在處理各種算法時(shí)具有較高的性能,在集成電路的制造業(yè)中得到了廣泛應(yīng)用。路由算法的負(fù)載平衡會(huì)影響網(wǎng)絡(luò)的吞吐量和延遲,吞吐率低和高延遲會(huì)導(dǎo)致網(wǎng)絡(luò)傳輸性能下降。因此,改善負(fù)載平衡對(duì)路由算法、包括容錯(cuò)路由算法設(shè)計(jì)至關(guān)重要。一些特定的應(yīng)用要求網(wǎng)絡(luò)即使出現(xiàn)少量故障,也要正常工作,因此研究2D-Mesh網(wǎng)絡(luò)中高效網(wǎng)絡(luò)吞吐率的容錯(cuò)路由算法具有重要的意義。容錯(cuò)路由算法傳統(tǒng)上采用自適應(yīng)路由策略。自適應(yīng)路由算法在網(wǎng)絡(luò)中進(jìn)行消息傳輸時(shí),根據(jù)網(wǎng)絡(luò)當(dāng)前的是否繁忙可以自主選擇路徑進(jìn)行傳輸,雖然有很好的靈活性但是需要判斷網(wǎng)絡(luò)狀態(tài)并進(jìn)行路由決策,這增加了網(wǎng)絡(luò)傳輸延時(shí),同時(shí)也使得路由器結(jié)構(gòu)變得復(fù)雜。而隨機(jī)的Oblivious路由算法中不用考慮當(dāng)前網(wǎng)絡(luò)的狀態(tài),通過隨機(jī)的選擇在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在的多條路徑進(jìn)行消息傳輸。因此,隨機(jī)的Oblivious路由算法具有很高的靈活性,能達(dá)到很好的性能。本文提出了一種新的基于Oblivious容錯(cuò)路由的思想。該思想避免在傳統(tǒng)容錯(cuò)路由中,網(wǎng)絡(luò)流量集中在故障邊界的問題,能夠使網(wǎng)絡(luò)流量更加均勻地分布;同時(shí),為了避免基于Oblivious路由不連通的情況,在選擇路由中間節(jié)點(diǎn)的過程中提出了基于矩陣相乘判斷連通性的方法。通過在兩階段的路由中進(jìn)行矩陣相乘計(jì)算準(zhǔn)確排除了哪些導(dǎo)致不連通的中間節(jié)點(diǎn)。實(shí)驗(yàn)顯示,通過使用該算法,有較少故障節(jié)點(diǎn)的網(wǎng)絡(luò)的連通率達(dá)到100%。本文基于新的Oblivious容錯(cuò)路由的思想提出了三種2D-Mesh網(wǎng)絡(luò)容錯(cuò)路由算法,即DXYFT算法、DYXFT算法和U3TFT算法,實(shí)現(xiàn)了從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間隨機(jī)選擇多條路徑的功能。并對(duì)這三種路由算法的無死鎖進(jìn)行了證明。這些算法提高了吞吐率,避免了故障邊界網(wǎng)絡(luò)流量過于集中,使網(wǎng)絡(luò)分布更加均衡,同時(shí)保證了系統(tǒng)的連通性。實(shí)驗(yàn)表明,與傳統(tǒng)路由算法相比,新的算法在最壞情況的通訊情況下的網(wǎng)絡(luò)吞吐率有較好的結(jié)果。例如在網(wǎng)絡(luò)規(guī)模為6×6且多個(gè)故障節(jié)點(diǎn)的情況下與自適應(yīng)繞道路由相比,DXYFT算法、DYXFT算法與U3TFT算法的最壞情況吞吐率分別提高了18%、18%和19%。 【學(xué)位授予單位】：天津工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP393.0

【圖文】：

沖器的大小是流控單元的整數(shù)倍。路由器中開關(guān)的作用是需要將輸入和輸出的緩逡逑沖器進(jìn)行內(nèi)部的連接，其中連接分為全連接和非全連接等結(jié)構(gòu)。逡逑一般的路由器模型如圖２－１所示。傳遞報(bào)文消息的網(wǎng)絡(luò)過程：１．輸入通道的逡逑鏈接控制器收到報(bào)文消息之后，將報(bào)文消息存儲(chǔ)到輸入的緩沖器；２．路由和重載逡逑單元的模塊，會(huì)讀取報(bào)文頭的路由信息；３．根據(jù)交換開關(guān)的使用情況進(jìn)行判斷，逡逑

＿路由逡逑＼和仲戴逡逑圖２－１路由器的結(jié)構(gòu)逡逑２．３路由算法逡逑在二維Ｍｅｓｈ網(wǎng)絡(luò)中，雖然拓?fù)浣Y(jié)構(gòu)比較簡(jiǎn)單，但是它屬于比較嚴(yán)格的正交逡逑拓?fù)�。在二維網(wǎng)絡(luò)的之間進(jìn)行消息傳輸時(shí)，必須有良好的路由算法作為傳輸?shù)谋ｅ义险�。路由算法�?yīng)滿足網(wǎng)絡(luò)的一些基本要求。丨．性能要求是有限延遲、高吞吐量和逡逑低功耗。２．架構(gòu)要求是通用性、可擴(kuò)展性和簡(jiǎn)單性。３．路由算法的可靠性和壽命逡逑擴(kuò)展能力己成為選擇路由算法的關(guān)鍵因素。為了滿足這些要求，存在確定性和自逡逑適應(yīng)路由兩種取向。逡逑２．３．１路由算法設(shè)計(jì)邐．逡逑路由算法是指從源節(jié)點(diǎn)傳送消息到目的節(jié)點(diǎn)時(shí)有一條或者多條可以連通的逡逑路徑。路由算法可以決定網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行路由時(shí)對(duì)轉(zhuǎn)發(fā)端口的選擇，在一定程逡逑度上決定著整個(gè)Ｍｅｓｈ網(wǎng)絡(luò)的吞吐量Ｍ。所以在路由算法設(shè)計(jì)時(shí)要考慮的因素有：逡逑１．

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 周子騰;王開;裴文江;;基于廣義對(duì)數(shù)函數(shù)的統(tǒng)一路由策略[J];新技術(shù)新工藝;2015年01期

2 俞明艷,賴明勇,洪偉林;小城鎮(zhèn)物流配送網(wǎng)絡(luò)再路由策略[J];財(cái)經(jīng)理論與實(shí)踐;2005年02期

3 黨群,曲榮欣,黨誠;一種確定路由策略沖突級(jí)別的方法[J];計(jì)算機(jī)工程;2004年21期

4 張鳳林,郭波,王正明;基于再路由策略的保障網(wǎng)絡(luò)性能可用性評(píng)估[J];國防科技大學(xué)學(xué)報(bào);2003年02期

5 張鳳林,郭波,張濤,王正明;面向任務(wù)的保障網(wǎng)絡(luò)再路由策略及預(yù)先規(guī)劃研究[J];系統(tǒng)工程理論與實(shí)踐;2003年06期

6 倪鑒;矩陣搜索包頭標(biāo)識(shí)固定式路由算法[J];長(zhǎng)春郵電學(xué)院學(xué)報(bào);1989年03期

7 邱偉迪;蔣華;;基于復(fù)雜網(wǎng)絡(luò)的路由策略研究[J];企業(yè)科技與發(fā)展;2018年09期

8 曲榮欣;張春宏;高遠(yuǎn);;基于安全配置準(zhǔn)則的路由策略沖突級(jí)別的確定[J];計(jì)算機(jī)工程;2006年11期

9 彭穎;王淖;王高才;;移動(dòng)社會(huì)網(wǎng)絡(luò)中基于社區(qū)的最優(yōu)能效路由策略研究[J];通信學(xué)報(bào);2017年05期

10 劉偉彥;劉斌;;基于加權(quán)路由策略的復(fù)雜網(wǎng)絡(luò)擁塞控制研究[J];系統(tǒng)工程理論與實(shí)踐;2015年04期

相關(guān)會(huì)議論文 前10條

1 汪秉宏;;通訊網(wǎng)絡(luò)上信息傳輸?shù)淖罴崖酚刹呗匝芯縖A];2006全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文集[C];2006年

2 陽德青;徐林昊;錢衛(wèi)寧;周水庚;周傲英;;SQRT:P2P環(huán)境下的一種基于貢獻(xiàn)的自適應(yīng)查詢路由策略[A];第二十屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2003年

3 黃光昊;謝繼東;張更新;;低軌衛(wèi)星網(wǎng)絡(luò)路由策略研究現(xiàn)狀分析[A];第十四屆衛(wèi)星通信學(xué)術(shù)年會(huì)論文集[C];2018年

4 王禹;趙躍龍;;一種P2P網(wǎng)絡(luò)分級(jí)路由策略[A];第15屆全國信息存儲(chǔ)技術(shù)學(xué)術(shù)會(huì)議論文集[C];2008年

5 譚璐;郭慶;楊明川;;一種基于最早遺傳算法的雙層衛(wèi)星容遲/容斷網(wǎng)絡(luò)路由策略[A];第十二屆衛(wèi)星通信學(xué)術(shù)年會(huì)論文集[C];2016年

6 周萬春;吳博;;一種優(yōu)化的分層式移動(dòng)IPv6路由策略的分析與研究[A];2007年全國開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(上冊(cè))[C];2007年

7 唐宏P(guān)，

本文編號(hào)：2712360