PMC模型下EQn,k和Q(d1,d2)的條件診斷度.pdf

1、計算機大規(guī)模處理數據有多種方式，伴隨著因特網的普及和云計算的高速發(fā)展，網絡與計算機更緊密的結合在了一起。在龐大的網絡環(huán)境中散布著大量的處理終端和服務器，發(fā)生錯誤或者物理性故障是不可避免的。如何在發(fā)生故障時依靠網絡系統(tǒng)自身的能力進行錯誤判別，并且不額外增加系統(tǒng)資源的投入和消耗就變得非常具有現(xiàn)實意義。
　　應用圖論中的無向圖理論對計算機網絡進行抽象分析是普遍的方法。將網絡中的處理器抽象成頂點，將通信鏈路抽象成無向邊，即可構造出系統(tǒng)所對

2、應的圖。如果系統(tǒng)中某些處理器或者服務器錯誤，那么如何通過一定的算法將錯誤節(jié)點查找出來就是網絡診斷問題。這一類算法已經有過比較深入系統(tǒng)的研究，可以應用于復雜網絡系統(tǒng)的診斷，也可以應用于多處理器系統(tǒng)的診斷。
　　對于一些特殊網絡拓撲結構的研究比較成熟，比如超立方圖Qn就已經在IBM大型機上得到實際應用。擴展超立方體EQn,k是經典的超立方體網絡Qn的一種改進和推廣，廣義立方體Q(d1，d2，…，dn）是網絡拓撲結構的更一般化的推廣。他

3、們不但繼承了超立方體網絡的優(yōu)點，還在某些方面大大的改進了網絡性質。本文通過對小規(guī)模圖進行分析歸納找到規(guī)律，再通過嚴格的數學證明來研究上述兩類網絡拓撲結構的診斷性質，得出診斷度:
　　(1)當n≥3，k≥3的情況下，EQn,k的條件診斷度為4n-3。
　　(2)當n≥3，k=2的情況下，EQn,k的條件診斷度為4n-7。
　　(3)當d2≤2d1的情況下，有tc(Q(d1，d2))=2d1+2d2-7。
　　(4)