寇茲網路上之分散式容錯路由

Abstract

在寇玆網路上，我們提出一分散式容錯路由演算法(Distributed Fault-Tolerant R- outing) ，藉此演算法無論網路上出現損壞與否，皆可成功地傳遞信息 (Message)。 而且此策略只需假設網路上未損壞的節點能知道相鄰之節點是否損壞，所以在傳遞的 信息中必須加入已遭遇過之損壞節點的資訊 (Information)。由於寇玆網路很複雜， 在提出容錯路由演算法之前，先針對任意目的節點(Destination Node)建構一對應之 以目的節點為根的樹，由此樹我們可以發展出一些寇玆網路的特性，這些特性可供運 用來確保信息在傳遞時不會重覆經過同一個損壞的節點。 概述我們的策略如下：首先，網路上每一節點均嘗試以最短路徑來傳遞信息。然而由 於無法預知依此路徑是否將遭遇損壞節點，所以依此策略選擇之路徑不一定最短。但 是我們可使用寇玆網路的特性，取得繞路路徑。另外，為了提昇取得新的繞路路徑之 效率，以及節點檢視此繞路是否包含已遭遇過之損壞節點的計算時間，我們亦發展出 一些規則和方法來避免許多多餘的工作。最後，將我們提出的路由演算法與其他網路 上的不同策略作比較。