星形圖上無(wú)死鎖受限條件及路由算法.pdf

1、由于具有正則性、對(duì)稱性、可嵌入性、并行性和可擴(kuò)展性等優(yōu)良特性，星形圖(StarGraph)和超立方體(Hypercube)互聯(lián)網(wǎng)絡(luò)受到了研究者們的廣泛關(guān)注，成為并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)中的重要拓?fù)浣Y(jié)構(gòu)。隨著現(xiàn)在的并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)規(guī)模越來(lái)越大，網(wǎng)絡(luò)中出現(xiàn)處理機(jī)故障或處理機(jī)間的鏈路故障的可能性也越來(lái)越大；這就使得并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)的容錯(cuò)性及其研究也變得越來(lái)越重要，因此，設(shè)計(jì)具有較好容錯(cuò)性的路由算法對(duì)并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)有著重要意義。 到目

2、前為止，人們已經(jīng)對(duì)星形圖和超立方體互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦约捌淙蒎e(cuò)模型與容錯(cuò)路由算法方面分別進(jìn)行了深入的研究，并基于星形圖和超立方體互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦苑謩e建立了一些容錯(cuò)模型及其容錯(cuò)路由算法，但是仍有許多問(wèn)題有待研究。本文研究星形圖互聯(lián)網(wǎng)絡(luò)的受限條件的無(wú)死鎖路徑算法和超立方體互聯(lián)網(wǎng)絡(luò)的安全通路容錯(cuò)算法。 在對(duì)星形圖互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦约捌淙蒎e(cuò)模型與容錯(cuò)路由算法方面，針對(duì)星形圖中可能產(chǎn)生死鎖的問(wèn)題，本文對(duì)星形圖上無(wú)死鎖的路徑算法進(jìn)行了研究，

3、得到了星形圖上的二類最小無(wú)死鎖受限條件，并給出了一個(gè)滿足該二類最小無(wú)死鎖受限條件的無(wú)死鎖路徑算法。此外，本文還提出了星形圖上兩類基于單緩沖和雙緩沖技術(shù)的無(wú)死鎖受限條件，并給出了相應(yīng)的無(wú)死鎖路徑算法。 在對(duì)超立方體互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦约捌淙蒎e(cuò)模型與容錯(cuò)路由算法方面，本文首先綜述了目前國(guó)內(nèi)、國(guó)際上在超立方體互聯(lián)網(wǎng)絡(luò)研究方面所做的主要研究工作，并基于已有的一些研究成果，提出了一種新的超立方體互聯(lián)網(wǎng)絡(luò)的容錯(cuò)模型及其容錯(cuò)路由算法：即基于安全