Clos網絡中變長分組交換及調度算法研究

摘 要:Clos網絡是多端口的路由器和交換機中經常采用的交換網絡，其優點在于它是一個結構全對稱的網絡。比較了多級Clos網絡分布式調度算法中定長分組和變長分組交換的特點;給出一種基于變長分組交換的MSM型三級Clos交換網絡結構和相應的ACBS調度算法;消除了分組負載分配的不公平性。分析表明該調度算法優于傳統算法，并通過仿真實驗驗證了算法的有效性。

關鍵詞:Clos; 交換網絡; 變長分組; 調度算法

中圖分類號:TN915; TP393 文獻標識碼:A 文章編號:1004-373X(2010)14-0105-04

Research on Varied Length Packet Mechanism and Scheduling Algorithm in Clos Switched Network

LIU Wei1， DU Juan2， YANG Shuai1

(1. The PLA Commanding Communications Academy， Wuhan 430010， China;

2. Chongqing Communication College， Chongqing 400035， China)

Abstract: Clos network is widely used in multi-port router and switch device， due to its holosymmetric network structure. The properties of fixed length cell and varied length packet switch in multi-level Clos network distributed scheduling algorithm are compared in this paper. A three-stage MSM Clos network structure based on varied length packet and correspongding ACBS scheduling algorithm are proposed， which eliminates the unfair load-allotment in the packet switch mechanism. The analysis shows that the scheduling algorithm is superior to the traditional algorithm. The simulation proves the efficiency of the proposed algorithm.

Keywords: Clos; switched network; varied length packet; scheduling algorithm

目前大容量交換結構采用的分組交換技術主要是基于信元的(cell-based)，即在變長分組如IP進行交換前，先切割為定長的信元(cell)，通過交換結構(switch fabric)后再在出端口重組為原變長分組[1-2]。這種技術可帶來很高的交換容量和吞吐率，如對于輸入緩存的縱橫開關(crossbar)單級交換結構[3]，應當采用較高的內部交換加速因子和優良的交換調度算法時，可達到近Tb/s的交換容量和100%的系統吞吐率。本文首先比較了多級Clos網絡[4]的定長分組和變長分組交換的特點，然后給出了一種基于變長分組交換的MSM型三級Clos交換網絡結構和相應的調度算法，并對算法性能進行了分析和仿真。

1 定長分組與變長分組交換的特點

雖然就交換結構本身而言，基于信元的交換技術已發展的相當完善，但從系統的角度看它仍存在一些問題。首先，由于交換結構在入端口需要對變長分組切割、在出端口需要對信元重組，從而引入了較大的交換時延;其次，在分組切割為信元的過程中還存在n+1問題;此外，多級交換網絡中采用定長信元交換，除了在單Crossbar中的缺點外，還會引起信元的亂序。……