摺疊式超方體網路上的容錯路由研究

Abstract

尋找路由在摺疊式超方體網路上有節點或連線壞掉時，摺疊式超方體網路是在超方體 網路上額外的連線使得網路的直徑減半。首先我們提出一個分散式的容錯路由演算法 ，網路上每個節點只知道鄰近連線的好壞。當節點或連線壞掉的個數小於或等於網路 的維度數時，演算法可以正常的執行。 由於分散式演算法只知道相臨連線的好壞，有時無法找到最短路徑。為了克服這個缺 點，我們提出兩種集中式容錯路由演算法，網路上每個節點都知道整個網路上的情形 。一個是啟發式演算法，當壞掉的連線數小於或等於網路的維度數時，找到最短路徑 的效果非常好。另一個是利用分割並克服的演算法，當節點或連線壞掉的個數小於或 等於網路的維度數時，可以找到最佳路徑。