超立方體圖上的容錯(cuò)路由算法研究.pdf

1、隨著現(xiàn)代工業(yè)對(duì)數(shù)據(jù)計(jì)算的要求越來越高，包括運(yùn)算速度，運(yùn)算準(zhǔn)確度和連續(xù)性安全性，導(dǎo)致計(jì)算機(jī)技術(shù)飛速發(fā)展以適應(yīng)各種計(jì)算的需要。多計(jì)算機(jī)系統(tǒng)和多處理器計(jì)算機(jī)系統(tǒng)的出現(xiàn)解決了對(duì)計(jì)算量的巨大需要，并且擁有很強(qiáng)的穩(wěn)定性和安全性。 超立方體網(wǎng)絡(luò)是多處理機(jī)系統(tǒng)中常見的一種互連網(wǎng)絡(luò)．由于多處理機(jī)系統(tǒng)的規(guī)模越來越大，系統(tǒng)中出現(xiàn)處理機(jī)故障或處理機(jī)間的鏈路故障的可能性也隨之增加．因此設(shè)計(jì)較好的容錯(cuò)路由策略，盡可能多地記錄系統(tǒng)中存在的最優(yōu)通路的信息，使得

2、當(dāng)系統(tǒng)中存在故障的情況下實(shí)現(xiàn)更有效的容錯(cuò)路由，達(dá)到提高整個(gè)系統(tǒng)性能的目的，也越發(fā)顯得重要。 本文首先對(duì)一些基本概念作了介紹，包括當(dāng)前多計(jì)算機(jī)系統(tǒng)的發(fā)展趨勢(shì)，研究模型，圖和超立方體圖，容錯(cuò)路由及其算法。然后從一種最基本和簡(jiǎn)單的研究模型一安全系數(shù)模型入手，對(duì)超立方體網(wǎng)絡(luò)的容錯(cuò)性能作了分析和介紹。但是安全系數(shù)模型是針對(duì)僅出現(xiàn)故障機(jī)的情況而言的，并且容錯(cuò)路由算法是一種近似貪婪算法，因此應(yīng)用方面具有較大的局限性。所以在安全系數(shù)模型的基礎(chǔ)上

3、引入了安全向量模型。安全向量模型大大改善了其可用性，使超立方體網(wǎng)絡(luò)中無(wú)論出現(xiàn)故障鏈路還是故障機(jī)都可以運(yùn)用，只要故障機(jī)的數(shù)目不超過總數(shù)-1。但是安全向量算法的缺陷在于每個(gè)處理機(jī)的安全向量?jī)H僅根據(jù)其相鄰處理機(jī)的安全向量來計(jì)算得到，在一定程度上限制了每個(gè)處理機(jī)反映全局故障信息的能力，導(dǎo)致有些最優(yōu)路由不能通過算法得到。擴(kuò)展安全向量模型改進(jìn)了安全向量模型的局限性，將范圍擴(kuò)大到距離為2以內(nèi)的相鄰處理機(jī)，也就是說根據(jù)距離為2以內(nèi)的處理機(jī)的安全向量來確

4、定該處理機(jī)的安全向量，使得得到的最優(yōu)和次優(yōu)容錯(cuò)路由的數(shù)目更接近于實(shí)際數(shù)目，大大提高了網(wǎng)絡(luò)的容錯(cuò)性。 本文在上述三種模型的基礎(chǔ)上提出了改進(jìn)型安全通路向量模型，即將所有的故障處理機(jī)轉(zhuǎn)化成故障鏈路，簡(jiǎn)化了網(wǎng)絡(luò)研究的復(fù)雜程度，然后針對(duì)純故障鏈路的超立方體網(wǎng)絡(luò)進(jìn)行分析，提出了改進(jìn)安全通路向量的定義，此種模型計(jì)算出來的安全向量比擴(kuò)展安全向量更接近于實(shí)際值，并且比單純解決故障機(jī)問題的安全系數(shù)模型和解決故障鏈路問題的安全通路向量模型更具有普遍性