交錯群網(wǎng)絡(luò)的容錯性分析.pdf

1、眾所周知，信息社會的基礎(chǔ)是計算機互連網(wǎng)絡(luò)，信息交換的關(guān)鍵是通信算法。尋找具有路由算法簡單、容錯性能高等良好性質(zhì)的互連網(wǎng)絡(luò)是實現(xiàn)各種通信算法和協(xié)議的前提。自從S.B.Akers,B.Krishnamarthy倡導(dǎo)把Cayley圖(群圖)作為對稱互連網(wǎng)絡(luò)模型之后，網(wǎng)絡(luò)設(shè)計者和圖論學(xué)者利用各種技巧提出并研究了一系列互連網(wǎng)絡(luò)模型，如超立方體Qn，星圖網(wǎng)絡(luò)Sn及蝴蝶網(wǎng)絡(luò)(Butterfly Network)，蜂窩網(wǎng)絡(luò)(Honeycomb Netw

2、ork)等。交錯群圖AGn作為星圖可替代的網(wǎng)絡(luò)，也在1993年由J.S．Jwo,S.Lankshmivarahan和S.K.D.Dhall首先提出來。冀有虎提出了一種新的交錯群網(wǎng)絡(luò)ANn，與AGn相比，ANn的每個結(jié)點的度大約是舊網(wǎng)絡(luò)的一半且直徑與舊網(wǎng)絡(luò)大致相同，優(yōu)越性顯而易見。進一步，陳寶興給出了ANn的最優(yōu)路由算法。本文在此基礎(chǔ)上，解決了如下問題： (1)給出了交錯群網(wǎng)絡(luò)ANn的n-1條內(nèi)點不交的并行路構(gòu)造方法及所有路的長度

3、ι的上下界，進而求出了寬直徑與直徑的關(guān)系：D(ANn)+1≤ dn-1(ANn)≤D(ANn)+2，同時確定了其連通度是n-1。 (2)多處理器系統(tǒng)的容錯計算的研究已有近半個世紀的歷史，無論是在診斷策略，診斷模型，還是診斷算法方面，都取得了一系列的成果。Preparata，Metze和Chien首次提出了系統(tǒng)級的t-可診斷的概念。繼PMC模型之后，他們又提出了比較診斷模型。本文給出了交錯群ANn在PMC模型和比較診斷模型下關(guān)于不