超立方體的漸增延伸設計及可靠度分析

Abstract

超立方體(Hypercubes)有個重大缺點，就是它的節點數必須是二的冪次因而限制了可選擇的圖形大小。為了改進這個缺點，漸增式超立方體(Incrementally extensible hypercubes)被設計出來；它不但沒有了節點數的限制，也保留了數個超立方體的優點。在這本論文中，我們分析漸增式超立方體在嵌置迴圈(Cycles)，環形網狀結構(Tori)，以及完全二元樹(Complete binary trees)的能力。我們也更進一步的設計了一個新的架構；我們稱之為漸增式折疊超立方體(Incrementally extensible folded hypercubes)。 對於大型的超立方體而言，總有些零件會隨著時間而損壞，所以可靠度的分析就十分重要。在考慮節點及連線都有壞的可能假設下，我們也導出了超立方體可靠度的封閉式(Closed form)。最後，我們設計了一個在損壞的超立方體中配置(Allocate)次超立方體演算法。

The hypercube has a serious drawback that the number of nodes must be a power of two, and thus considerably limits the choice of the number of nodes in the graph. In order to overcome this drawback, the incrementally extensible hypercube (IEH) graph is proposed for an arbitrary number of nodes. The IEH graph reserves several advantages of the hypercube. In this dissertation, we analyze the IEH graph with embedded cycles, tori, and complete binary trees. Further, we design a new topology, the incremental In large hypercubes, some components may fail before long. Therefore, it is important to obtain system reliabilities. We consider the reliability of the hypercube in both node and link failure model and give a closed formula to obtain reliabilities. Finally, we devise an algorithm to allocate a subcube in a faulty circuit-switched hypercube.