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

　　1 引言

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

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

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

　　2.1重新調(diào)度算法

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

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

　　2.2 成組調(diào)度算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　c1、c2：存放最小間隔對(duì)應(yīng)的信道編號(hào)的兩個(gè)變量;

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

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

　　4 結(jié)論

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