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

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

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

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

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