混洗交換網

混洗交換網仿效並行處理中使用的混洗交換開關網路，信息包可從傳送站點經過混洗交換網到達任一個目標站點。它的路由選擇算法比較簡單，且具備改變原有路由的能力，可進行流量控制和故障恢復。

基本介紹

• 中文名：混洗交換網
• 外文名：shuffle-exchange network
• 領域：城域網

簡介

為了提供完整的連通性，貝恩斯網路需要個階段，每個階段具有個交換節點。然而，通過使用一類不完全連線網路的網路，可以進一步降低多級網路的成本。一般來說，混洗交換網路由一系列與shuffle或butterfly交織的交換排列組成。並且重要的是理解shuffle和交換排列序列如何一起形成有用的網路。理解多級置換網路的關鍵是考慮每個相繼排列對通過網路的對象標籤的影響。假設S是進入網路的對象的標籤，D是該對象的目的地的標籤。將一個臨時標籤L與對象關聯起來，並且這最初被設定成S。如果可以通過排列序列來修改L，使其等於D，則該對象將到達其目的。

圖一

由於置換提供了選擇輸入標籤的最低有效位或使其保持完整的選擇，所以可以使用置換使L中的最低有效位等於D中的最低有效位。這是從L 到D轉換的基本步驟。並且，或I置換的選擇決定了圖1的一般交換盒中的交換節點設定。下一步是將L中的下一位暴露給置換，這是最簡單地通過將L移位一位來完成的。如圖二中的N = 8所示，這直接相當於在0到N範圍內的所有標籤L上的完全混洗置換。在套用的shuffle和交換排列之後，L中的所有比特都將被改變，L將等於D。作為直接結果，位於標籤L的對象將被路由到由D標識的輸出連線埠，並且這個網路將完成其功能。

圖二

實例

榕樹網路

榕樹網路（The Banyan Network）

可以定義為一般交換和butterfly排列的序列，由複合路由函式 表示為：

在這個網路中，階段，每個階段由n個/ 2個活躍的E1節點組成，連續階段由被動βi置換連線。這在圖三中示出，它描繪了一個三階段（8輸入，8輸出）榕樹網路。

圖三

歐米茄網路

n階歐米茄網路定義為混洗序列和一般交換排列,由複合路由函式 表示為：

這種網路使用具有上下傳播能力的交換節點，並且值得注意的是，網路中的所有階段都是相同的。然而，從圖四可以看出，這種網路不能同時建立從節點4到4和6到5的連線。由於這個原因，這種網路是一個阻塞網路。原則上，具有 級的所有多級網路都阻塞網路，儘管實現阻塞的技術在實現之間有所不同。

圖四

間接二進制n-立方體網路

間接二進制n-立方體網路（The Indirect Binary n-cube Network），這裡表示為 ，可以被正式定義為：

間接二進制n立方體，有時簡單地稱為多級立方體，與Ω-網路非常相似，儘管它不能連線的連線對不同於網路。間接二進制n立方體如圖五所示。

雖然網路的shuffle交換類是阻塞網路，但它們仍然具有豐富的互連結構，能夠以相對低的成本支持大量的同時連線。許多採用多級網路的高性能計算機使用某種形式的混洗交換開關。

圖五

發展現狀

隨著網路技術的不斷發展和普及，混洗交換網路已經成為網路中的主要組成部分，占據著核心地位。在混洗交換網路中，如何對數據進行快速、準確的傳輸，已經成為混洗交換網路中的主要研究課題。現階段，主流的混洗交換網路中衝突消除方法包括基於遺傳算法的混洗交換網路中衝突消除方法、基於蟻群算法的混洗交換網路中衝突消除方法和基於二叉樹搜尋算法的混洗交換網路中衝突消除方法。其中，最常用的是基於二叉樹搜尋算法的混洗交換網路中衝突消除方法。由於混洗交換網路中衝突消除方法擁有極為廣闊的發展空間，因此，受到了廣泛的關注，擁有良好的發展前景。

在混洗交換網路中，開關的數目很難滿足實際通信的需求，容易造成信道中的信號衝突。利用傳統算法進行混洗交換網路中的衝突消除，假設通信信號的數目過多，將造成混洗交換網路中出現通信衝突，難以實現混洗交換網路的通信。