一種基于輸入緩沖交叉開關(guān)的調(diào)度算法

宣二勇,王蘊珠

(1.中國電子科技集團(tuán)公司第五十四研究所,河北石家莊050081;2.河北大學(xué)計算機中心,河北保定071002)

0 引言

隨著Internet中業(yè)務(wù)量爆炸性增長以及鏈路傳輸速率的不斷提高,能夠線速完成IP包轉(zhuǎn)發(fā)與交換的網(wǎng)絡(luò)核心設(shè)備,特別是核心路由器和交換機已成為制約網(wǎng)絡(luò)性能的主要瓶頸之一。Crossbar開關(guān)因其固有的非阻塞特性以及易于實現(xiàn)等特點,被廣泛應(yīng)用于高速交換系統(tǒng)的研究和設(shè)計中。Crossbar開關(guān)主要用于ATM交換系統(tǒng)的設(shè)計,采用固定長度的信元交換方式,變長的IP包在輸入端口被分割為多個固定長度的信元,通過交換開關(guān)后在輸出端口處再被重組為變長的IP包。

開關(guān)結(jié)構(gòu)和調(diào)度算法影響甚至決定著Crossbar開關(guān)的性能,因此采用合適的開關(guān)結(jié)構(gòu)和高效的調(diào)度算法將成為設(shè)計高速大容量交換設(shè)備的關(guān)鍵。

1 系統(tǒng)模型

一個N×NCrossbar開關(guān)具有N2個交叉點,通過交叉點的閉合與斷開可以同時完成N個信元的并行傳輸。根據(jù)緩沖區(qū)位置的不同,Crossbar開關(guān)分為輸入緩沖和輸出緩沖,輸入緩沖Crossbar開關(guān)由于其內(nèi)部交換速率只要求為輸入鏈路速率,具有良好的擴展性,非常適合大容量高速交換系統(tǒng)的要求,因此得到了廣泛關(guān)注和應(yīng)用。

然而采用單一先入先出(FIFO)緩沖方式的輸入緩沖Crossbar開關(guān)存在著嚴(yán)重的隊頭阻塞,隊頭阻塞表現(xiàn)為當(dāng)隊頭信元得不到調(diào)度時,排在其后的所有信元均得不到調(diào)度,即使該信元發(fā)往空閑輸出端口。隊頭阻塞使得開關(guān)的最大吞吐量僅僅為58.6%[1]。研究表明,采用虛擬輸出排隊(VOQ)策略可以完全消除隊頭阻塞:在每一個輸入端口為每一個輸出端口分配一個單獨的隊列,這樣送往不同輸出端口的信元被緩存在不同的隊列中,從而各輸入隊列中的信元之間相互不會產(chǎn)生阻塞。

本文研究的模型采用基_于VOQ的輸入緩沖Crossbar開關(guān),如圖1所示。

圖1 基于VOQ的輸入緩沖Crossbar開關(guān)

2 PB-RRM2算法分析

輸入緩沖Crossbar開關(guān)需要高效調(diào)度算法的支持。調(diào)度算法的作用為在每一信元時隙產(chǎn)生配置信息以決定哪一個輸入端口與哪一個輸出端口相連。算法的設(shè)計基于如下原則:即每個信元時隙,任意一個輸入端口至多可以發(fā)送一個信元,同時任意一個輸出端口至多只可以接收一個信元。在實際的交換系統(tǒng)設(shè)計中,算法應(yīng)高效簡單,即算法在盡可能短的時間內(nèi)應(yīng)產(chǎn)生盡可能多的匹配,同時易于在硬件中實現(xiàn)。

衡量調(diào)度算法性能的主要指標(biāo)[2]包括吞吐量、信元平均時延和公平性。

2.1 優(yōu)先級列表

在并行迭代匹配算法中,Round Robin指針需按照一定的規(guī)則進(jìn)行修改,合適的指針修改規(guī)則可以保證算法具有較少的迭代次數(shù)、更高的吞吐量和好的公平性。本文采用一種稱為優(yōu)先級列表 Round Robin指針修改規(guī)則,使得算法具有較高的性能。優(yōu)先級列表的構(gòu)造原則如下:

①如果輸入端口Ii是輸出端口Oj的第k優(yōu)先級,則輸出端口Oj也是輸入端口Ii的第k優(yōu)先級;

②一個輸入端口只可以是一個輸出端口的第k級優(yōu)先級,同時一個輸出端口只可以是一個輸入端口的第k級優(yōu)先級。

根據(jù)上述原則,優(yōu)先級列表的產(chǎn)生方法為:假設(shè){I1,I2,…,IN}和{O1,O2,…,ON}分別是輸入端口和輸出端口的集合,若輸出端口Oj是輸入端口Ii的第k優(yōu)先級,1≤i,j≤N,則

k=((j+N-i)modN)+1。

由上式可知,起始時輸入端口Ii分別是輸出端口{Oi,Oi+1,…,Oi-1}的第i優(yōu)先級,反之輸出端口Oj分別是輸入端口{Ij,Ij+1,…,Ij-1}的第j優(yōu)先級。

根據(jù)優(yōu)先級列表的構(gòu)造方法,Round Robin指針修改原則如下:

①第i次調(diào)度時,輸入輸出端口的Round Robin指針位置處于優(yōu)先級列表的第i條主對角線上,這樣保證了在N次調(diào)度中任意一輸入輸出端口對將有一次調(diào)度過程中成為最高優(yōu)先級匹配對,從而保證了算法的公平性;

②在每次調(diào)度的每次迭代過程中,輸入端口從當(dāng)前指針位置開始根據(jù)優(yōu)先級列表按照從左到右的順序選擇非空的VOQ發(fā)送請求;輸出端口同樣從當(dāng)前指針位置開始根據(jù)優(yōu)先級列表按照從下到上的順序授權(quán)接收到的請求信號;

③前面迭代中已匹配的輸入輸出對在后續(xù)迭代中不參與調(diào)度,未匹配的輸入輸出端口在后續(xù)迭代過程中繼續(xù)參與調(diào)度,直到找到極大匹配。

2.2 算法步驟

現(xiàn)有調(diào)度算法如并行迭代匹配(PIM)算法[3]、iSLIP[4]算法等,每次迭代包含請求、授權(quán)和接受3個步驟。本文通過將請求和接受2個步驟進(jìn)行合并,提出了一種2步調(diào)度算法,算法步驟如下:

①每個未匹配的輸入端口按照Round Robin指針的優(yōu)先級指示向一個空閑輸出端口發(fā)送一個請求;

②如果一個空閑輸出端口接收到任何請求,它根據(jù)Round Robin指針的優(yōu)先級指示,接受具有最高優(yōu)先級的輸入請求,并通知所有輸入端口該請求是否被接受;

③每次調(diào)度完成后,按照優(yōu)先級列表的規(guī)則修改Round Robin指針,即次高優(yōu)先級修改為最高優(yōu)先級,而最高優(yōu)先級修改為最低優(yōu)先級。

PB-RRM2算法與已有的迭代算法的相比,一方面,由于在請求階段每個輸入端口僅產(chǎn)生一個請求信號,因此當(dāng)該請求被授權(quán)時即意味著該輸入端口與某一輸出端口建立了匹配,從而算法將原先的3步迭代減少為2步迭代,縮短了每次調(diào)度所需的時間,從而提高了開關(guān)的運行速度。另一方面,由于輸入和輸出端口的指針采用優(yōu)先級列表的方式進(jìn)行配置和修改,保證了在每次迭代過程中輸入端口和輸出端口的Round Robin指針不會產(chǎn)生同步,提高了開關(guān)的吞吐量。

2.3 算法特性

通過上述對算法的描述,總結(jié)出PB-RRM2算法特性如下:

①算法采用2步迭代方式,縮短了每次迭代的時間,提高了開關(guān)的運行速度,非常適合于高速交換系統(tǒng)的設(shè)計中;

②由于在每次迭代中,每個輸入端口僅發(fā)送一個請求,從而大大減少了輸入輸出端口間的交互信息,簡化了輸入輸出端口仲裁邏輯的硬件設(shè)計,減少了所需的硬件邏輯資源;

③由于輸入輸出端口的Round Robin指針在每次調(diào)度后均被修改,保證了指針之間不會產(chǎn)生同步,因此消除了指針同步產(chǎn)生的吞吐量下降問題[5];同時可以證明當(dāng)采用一次迭代時,PB-RRM2算法的吞吐量要大于iSLIP算法;

④由于N次調(diào)度中,任意(Ii,Oj)總會在某次調(diào)度期間成為具有最高優(yōu)先級的輸入輸出對,從而算法不會出現(xiàn)“餓死”現(xiàn)象,保證了算法的公平性;

⑤可以證明,算法在獨立同分布keepfull到達(dá)條件下,即任何時刻所有的VOQ不空時,一次迭代獲得的吞吐量可以達(dá)到100%。

3 性能仿真

3.1 均勻分布

由于當(dāng)輸入鏈路速率較高時,調(diào)度的時間長度將受到限制,因此算法在實現(xiàn)中一般采用固定次數(shù)的迭代算法,下面的仿真結(jié)果給出了固定次數(shù)迭代算法的性能指標(biāo)。

假設(shè)各輸入端口的信元到達(dá)服從獨立同分布(i.i.d)貝努利過程,負(fù)載為 λ,采用 16×16端口的Crossbar開關(guān);同時假設(shè)每一輸入端口到達(dá)的信元均勻地分布于各輸出端口,算法每次調(diào)度迭代2次。

PB-RRM2算法和iSLIP算法在均勻的獨立同分布貝努利到達(dá)條件下帶寬利用率和信元平均時延的比較如圖2所示。

由圖2(a)可見,2種算法在λ＜0.55時帶寬利用率基本相同,這是由于當(dāng)λ較小時,算法均類似于隨機匹配。而當(dāng)λ＞0.55時,PB-RRM2算法的帶寬利用率大于iSLIP算法。

由圖2(b)可見,當(dāng)λ＜0.8時,2種算法具有幾乎相同的信元平均時延,而當(dāng)λ＞0.8時,2種算法的信元平均時延呈現(xiàn)突發(fā)性增長,但PB-RRM2算法的信元平均時延要比iSLIP算法小得多。

圖2 i.i.d條件下的帶寬利用率和信元平均時延

3.2 突發(fā)分布

PB-RRM2算法和iSLIP算法在突發(fā)到達(dá)情況下的吞吐量和信元平均時延如圖3所示。

圖3 on-off條件下的帶寬利用率和信元平均時延

假設(shè)業(yè)務(wù)到達(dá)服從on-off過程,負(fù)載為λ,同時假設(shè)每次突發(fā)產(chǎn)生的信元具有相同的輸出端口,突發(fā)長度L分別為10個和40個信元。

由圖 3可以看出,在 on-off到達(dá)條件下,PBRRM2算法和 iSLIP算法的帶寬利用率基本相同。而由圖3(b)可見,當(dāng)λ＜0.6時,PB-RRM2算法的信元平均時延與iSLIP算法基本相同,當(dāng)λ＞0.6時,PB-RRM2算法的信元平均時延要稍＞iSLIP算法。同時可以看出信元平均時延隨著突發(fā)長度L的增加而增大。

4 結(jié)束語

在基于VOQ的Crossbar開關(guān)的基礎(chǔ)上提出了PB-RRM2調(diào)度算法,通過計算機仿真表明,在均勻的獨立同分布貝努利到達(dá)條件下,當(dāng)負(fù)載較重時,該算法的性能要優(yōu)于iSLIP算法,在突發(fā)到達(dá)條件下,2種算法的性能基本相同。PB-RRM2由于采用了2步迭代和基于優(yōu)先級列表的Round Robin指針配置方式,減少了每次調(diào)度的時間,提高了開關(guān)的運行速度,同時消除了現(xiàn)有的Round Robin算法中由于指針同步所帶來的吞吐量下降問題;另外根據(jù)算法2步迭代的運行方式相同這一特點,整個交換開關(guān)的設(shè)計中只需要一組Round Robin指針,減少了硬件邏輯資源。當(dāng)采用流水實現(xiàn)時,算法硬件設(shè)計簡單,非常適合大容量高速交換系統(tǒng)的應(yīng)用場合。

[1]KAR OL M J,HLUCHYJ M,MORGAN S.Input Versus Output Queueing on Aspace Division Switches[J].IEEE Trans.on Communications,1988,35(4):1347-1356.

[2]孫志剛.路由器高速交換開關(guān)調(diào)度算法的研究實現(xiàn)[D].長沙:國防科技大學(xué),2000:5-6.

[3]ANDERSON T E,OWICKI S S,SAXE J B,et al.High Speed SwitchScheduling for Local Area Networks[J].ACM Trans.on Computer Systems,1993,11(4):319-352.

[4]MCKEOWN N.The iSLIP Scheduling Algorithm for Input Queued Switches[J].IEEE/ACM Trans.Networking,1999,7(2):188-201.