關於降低班樣網路的阻塞機率

Abstract

近年來，將班樣網路（Banyan networks）應用於大型多處理機系統（Multi-process ors system）以及電信（Telecommunication ）的研究，已經引起工程師以及研究工 作者們的興趣。班樣網路是多層連結網路（Multistage interconnection network） 的一種，由於它有路由相當的容易，經濟，具有超大型積體電路的發展潛力等等的特 性，使得它變的如此受歡迎。然而，阻塞（blocking）現象以及可信度（reliabilit y ）是它的問題。在此我們提出一些降低班樣網路的阻塞機率（blocking probabili ty）的方法。 首先，提出diversity-2 方式來降低班樣網路的阻塞機率。吾人將網路擴展成原班樣 網路的四倍，也就是說，如果原班樣網路是NxN ，對diversity-w 方式，則擴展成4N x4N 班樣網路。再者，將預送入此網路的封包（package ）複製成兩份，送入擴展後 的網路，經由兩條不相交（disjoint）的路徑送至目的地，結果發現降低了阻塞機率 ，並提供了容錯（fault-tolerant）能力，更重要的是當有單一暫時（single, inte rmittent）的錯誤產生時，可以不必診斷錯誤。 另外一種降低阻塞機率的方法是加緩衝器（buffer），我們討論幾種單一緩衝器班樣 網路（single-buffered banyan network）的輸出效能（throughput performance） 以及延遲效能（delay performance）。