在非均勻狀態下的班樣網路輸出效能之研究

Abstract

多層連結網路（Multistage Interconnection Network）由於它相當經濟，且具有超 大型積體電路的發展潛力，故已被研究應用於平行處理系統或電信網路。在以二輸入 二輸出為結構單位的多層連結網路中，由於大多數為等效結構，因此當人們討論這些 等效網路時，通常以班樣（Banyan）網路為代表。然而存在這些網路中的最大問題乃 是資料在傳送時被阻絕（blocking）甚至被丟失於網路之中。通常輸出效能（throug hput）被用來做為評估網路優劣的依據之一。所以透過一些運算法則來求得班樣網路 的輸出效能是了解這些網路的第一步驟。 至目前為止，有關班樣網路輸出效能的研究大多假設為均勻（uniform ）狀態，這種 假設簡化了分析步驟，卻與實際狀況有所出入。因此在這篇論文中，我們針對非均勻 （nonuniform）狀態來研究班樣網路的輸出效能以切合實際狀況。兩種非均勻模型將 被提出來討論。在這兩種非均勻模型下，一個簡單運算法則將被導出以求得班樣網路 輸出效能。但是這個運算法則著重在每一條傳輸路徑輸出效能的求得，而非網路整體 的輸出效能。至於網路整體的輸出效能可由各傳輸路徑輸出效能的期望值求得。但透 過這些傳輸路徑的輸出效能卻可使我們更了解班樣網路的特性。