一種改進(jìn)的光突發(fā)交換數據信道調度算法

　　1 引言

　　在光突發(fā)交換(OBS)網(wǎng)絡(luò )中，控制分組(BHPBurst Head Packet)和數據分組(BDP-Burst DataPacket)在時(shí)間和空間上是分離的。由于采用了單向資源預留方式，BHP先于BDP在特定的WDM信道巾傳送，核心節點(diǎn)根據BHP中的信息為相應的BDP建立全光通路。BDP經(jīng)過(guò)一段延遲后，在不需要確認的情況下直接在預先設置的全光通道中透明傳輸[1，2]。在這種情況下，核心節點(diǎn)如何根據BHP中的信息及當前節點(diǎn)信道占用情況為后續到達的BDP合理配置相應的交換矩陣，即數據信道調度算法，就成為人們研究的一個(gè)熱點(diǎn)。一個(gè)好的數據信道調度算法應盡量做到：(1)算法簡(jiǎn)單，計算量小;(2)信道利用率高，丟包率低：(3)不增加額外的網(wǎng)絡(luò )資源開(kāi)銷(xiāo)及網(wǎng)絡(luò )設備的復雜程度。傳統的調度算法如LAUC，LAUC_VF等[3, 4]，都是僅針對當前BHP來(lái)調度分配信道的,這樣就可能造成對當前的BHP來(lái)說(shuō),該次調度為最合適的調度。但對后續到達的其它BHP該次調度為不合理的涮度,從而造成數據信道使用不合理現象的出現[5]?？紤]圖1(為方便僅以?xún)蓚€(gè)數據信道為例)所示的情況，圖中每一個(gè)方框代表一個(gè)BDP，方框中數字代表與BDP相應的BHP的到達順序，也就是BDP被調度的順序，BDP5為新到達的BHP對應的BDP。采用LAUC或LAUC_VF等傳統調度算法,BDP5將由于無(wú)可用信道而被丟棄。

　　采用重新調度算法[2]或成組調度算法[6,7,8]可以較好的解決這個(gè)問(wèn)題。下面我們將先簡(jiǎn)單介紹一下這兩種調度算法,然后在分析不合理調度產(chǎn)生原因的基礎上，提出一種新的改進(jìn)算法。

　　2 兩類(lèi)基于LAUC的信道調度算法

　　2.1重新調度算法

　　重新調度算法的主要思想是一個(gè)已經(jīng)調度的BDP可以被重新調度到另一個(gè)可用波長(cháng)上,以容納新的突發(fā)請求。一旦重調度成功,需要發(fā)送一個(gè)"NOTIFY"消息,通知下一個(gè)節點(diǎn)突發(fā)數據包改變后的波長(cháng),以便其修改該包的入口信道設置[2]。在調度與重調度的每一步，仍然應用LAUC的"最遲可用信道"思想。在文獻[2]中提到了一種ABR(Active Burst Re-scheduling)算法,該算法在每個(gè)BDP的請求(即與該BDP對應得BHP)到達時(shí),按LAUC方式安排信道,一旦調度成功(安排了某個(gè)信道Di).就檢查其他信道的最后一個(gè)突發(fā)包是否可以"移動(dòng)"到信道Di,當存在多個(gè)可能性時(shí),找出其中最新的一個(gè)進(jìn)行重調度。對圖1所示情況來(lái)說(shuō)，當BDP4被調度安排到信道D2后，已調度的DBP3符合ABR算法的條件，被重新調度到信道D2，而DBP5將可以被調度到D1，從而降低了丟包率。圖2說(shuō)明了這一重調度過(guò)程。

　　ABR算法的優(yōu)點(diǎn)是提高了數據信道利用率(與LAUC相比)，降低了丟包率：其缺點(diǎn)是由于"朝令夕改",追發(fā)的NOTIFY消息增加了控制信道的負擔,同時(shí)也對核心節點(diǎn)的處理能力提出了更高的要求。文獻[2]指出，ABR的計算量近似為L(cháng)AUC的兩倍，但小于LAUC-VF。

　　2.2 成組調度算法

　　文獻[6，7，8]分別提出了幾種調度算法，雖然其具體實(shí)現過(guò)程各異,但都存在一個(gè)共同之處,即核心節點(diǎn)每次調度都是以一組BHP為單位進(jìn)行的,在本文中統稱(chēng)之為成組調度算法。文獻[8]提出了一種最小間隙組調度(SGGS)算法,該算法的基本思想是核心節點(diǎn)對每個(gè)到達的BHP,先不分配信道,而是按其對應的BDP到達時(shí)間順序將其插入一個(gè)隊列，當隊列中的BHP數目達到事先規定的一組控制包應包含的控制包數目N時(shí)，再按隊列中BHP的排列順序以L(fǎng)AUC(最小間隙)方式調度安排。這樣就保證了BHP在數據信道調度時(shí)按突發(fā)數據包DBP到達的先后次序被調度,達到合理使用數據信道的目的。

　　SGGS算法不需要額外的控制信息,信道利用率在LAUC算法的基礎上有了進(jìn)一步的提高。增加一組控制包中包含的BHP數目N可以進(jìn)一步提高其信道利用率,但付出的代價(jià)是整個(gè)系統偏置時(shí)間foffsettime)的普遍增加.因此Ⅳ不能取得很大。其它成組調度算法也存在同樣的問(wèn)題,即在提高信道利用率的同時(shí)付出了系統偏置時(shí)間延長(cháng)的代價(jià)。

　　3 一種改進(jìn)的調度算法

　　3.1 不合理調度產(chǎn)生原因分析

　　考慮圖3所示的情況。t'、t"分別為突發(fā)數據包BDP3和BDP4的到達時(shí)刻,l1為BDP4的持續時(shí)間,L為所有BDP的最大持續時(shí)間,d為BDP3與各數據信道Di的最遲可用時(shí)刻(即未調度時(shí)間)之間的間隔。由于d1

　　在OBS網(wǎng)絡(luò )中,由于偏置時(shí)間的存在,核心節點(diǎn)處的BHP到達順序與BDP到達順序不一致.就會(huì )產(chǎn)生上述不合理調度現象。實(shí)際上，在"最遲可用信道"思想下,只要一個(gè)BDP的到達時(shí)刻與某個(gè)信道的最遲可用時(shí)刻ti之間的間隔di>L,那么一旦后續調度的突發(fā)數據包完全在這個(gè)間隔內到達,就會(huì )產(chǎn)生不合理調度。若一個(gè)BHP對應的BDP符合上述條件(即di>L)，我們就稱(chēng)該BHP存在"隱患"。圖3中的BDP3對應的BHP就存在"隱患",因為它與信道D2的最遲可用時(shí)刻之間的問(wèn)隔d2>L。當一個(gè)存在"隱患"的BHP到達核心節點(diǎn)時(shí),一次不合理的調度就很有可能會(huì )發(fā)生(究竟能否發(fā)生還要視其后到達的BHP所攜帶的信息而定)。

　　3.2 改進(jìn)調度算法的提出

　　針對上述情況,我們提出了一種基于LAUC算法的改進(jìn)調度算法。該算法的核心思想是主動(dòng)去發(fā)現存在不合理"隱患"的BHP.并試圖通過(guò)等待分析其后的一個(gè)BHP所攜帶的BDP到達情況來(lái)出合理的決定。當一個(gè)BHP到達后,程序首先判斷其是否存在"隱患",若不存在"隱患"，則按LAUC方式調度該BHP,返回程序頭部繼續分析下一個(gè)BHP;若存在"隱患"，則該BHP的調度要視下一個(gè)BHP所攜帶的BDP到達情況而定：要么兩個(gè)BDP能構成一種更為合理的信道占用情況(形如圖2中的BDP3和BDP4),將兩個(gè)BDP分配到同一信道,視為一次成功的調度,返回程序頭部,繼續分析處理后續到達的BHP：要么兩個(gè)BDP不能構成更為合理的信道占用情況,則首先調度先到的BHP，然后分析后到的BHP是否存在"隱患",再重復上述過(guò)程。在該算法中,具體分配某個(gè)BDP時(shí),按照LAUC的最遲可用信道思想進(jìn)行。

　　為防止等待時(shí)間過(guò)長(cháng),可設定一個(gè)最大等待時(shí)間Tmax，當Tmax內無(wú)BHP到達時(shí)，結束等待,調度當前BHP。由于只須等待一個(gè)BHP,該算法的偏置時(shí)間延長(cháng)量與所有成組調度算法相比是最小的。

　　3.3 程序流程圖及變量說(shuō)明

　　圖4給出了該算法的程序流程圖。相關(guān)變量說(shuō)明如下：

　　M：核心節點(diǎn)到下一個(gè)相鄰節點(diǎn)的數據信道數目：

　　t'、t"：存放BDF到達時(shí)刻的兩個(gè)變量：

　　l1、l2：存放BDP持續時(shí)間的兩個(gè)變量;

　　ti：各信道的最遲可用時(shí)刻，i=1～M;

　　di：BDP到各信道最遲可用時(shí)刻的間隔，i=1～M;

　　min1、min2：存放最小間隔的兩個(gè)變量;

　　c1、c2：存放最小間隔對應的信道編號的兩個(gè)變量;

　　L：所有BDP的最大持續時(shí)間：

　　Lmax：事先設定的等待時(shí)間。

　　4 結論

　　在數據信道調度算法中,提高信道利用率和降低計算復雜度是一對不可調和的矛盾。本文提出的改進(jìn)算法由于采取了主動(dòng)尋找存在"隱患"BHP的策略,其信道利用率高于LAUC算法及SGGS算法(N=2時(shí)),同時(shí)能解決一些特定的問(wèn)題(例如圖1所示情況)，降低了丟包率。作為代價(jià),新算法由于增加了在大于零的di中輪詢(xún)di是否大于L的過(guò)程，在最壞的情況下計算量將比LAUC算法多M次(僅就算法的時(shí)間復雜度來(lái)說(shuō)，兩者都是O(M)，相對LAUC算法而言偏置時(shí)間也有所延長(cháng)。