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

宣二勇,王蘊(yùn)珠

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

0 引言

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

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

1 系統(tǒng)模型

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

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

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

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

2 PB-RRM2算法分析

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

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

2.1 優(yōu)先級(jí)列表

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

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

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

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

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

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

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

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

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

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

2.2 算法步驟

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

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

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

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

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

2.3 算法特性

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

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

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

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

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

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

3 性能仿真

3.1 均勻分布

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

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

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

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

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

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

3.2 突發(fā)分布

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

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

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

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

4 結(jié)束語(yǔ)

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