Mobius立方體互連網(wǎng)絡(luò)容錯(cuò)路由選擇算法研究.pdf

1、 本文以提高網(wǎng)絡(luò)的容錯(cuò)度為目的，在M(o)bius立方體這種互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，考慮故障處理器發(fā)生的概率和故障處理器的分布狀況，即在條件連通度下分析互連網(wǎng)絡(luò)的容錯(cuò)性能和容錯(cuò)路由選擇問題。 首先，本文以0-M(o)bius立方體為例證明了M(o)bius立方體在其任一頂點(diǎn)的鄰接頂點(diǎn)并不同時(shí)發(fā)生故障時(shí)，Mobius立方體的條件頂點(diǎn)連通度也為2n-2。 然后，本文給出一個(gè)M(o)bius立方體互連網(wǎng)絡(luò)上基于頂點(diǎn)連通度的容

2、錯(cuò)路由選擇算法，分析該算法的時(shí)間復(fù)雜度為O(n)，并且證明在Mn中，在給定一組至多有n-1個(gè)故障頂點(diǎn)的故障集F的條件下，對于兩個(gè)無故障頂點(diǎn)s和t，能夠在O(n)時(shí)間內(nèi)找到從s→t的一條無故障路徑。 接下來，本文給出M(o)bius立方體互連網(wǎng)絡(luò)上基于條件頂點(diǎn)連通度的一個(gè)容錯(cuò)路由選擇算法，分析該算法的時(shí)間復(fù)雜度為O(n)，并且證明在1-safe的Mn中，在給定故障集F( )V(Mn)，且|F|≤2n-3的條件下，對于兩個(gè)無故障頂點(diǎn)