一種改進(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)過一段延遲后,在不需要確認(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)算法簡單,計(jì)算量小;(2)信道利用率高,丟包率低:(3)不增加額外的網(wǎng)絡(luò)資源開銷及網(wǎng)絡(luò)設(shè)備的復(fù)雜程度。傳統(tǒng)的調(diào)度算法如LAUC,LAUC_VF等[3, 4],都是僅針對當(dāng)前BHP來調(diào)度分配信道的,這樣就可能造成對當(dāng)前的BHP來說,該次調(diào)度為最合適的調(diào)度。但對后續(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對應(yīng)的BDP。采用LAUC或LAUC_VF等傳統(tǒng)調(diào)度算法,BDP5將由于無可用信道而被丟棄。
采用重新調(diào)度算法[2]或成組調(diào)度算法[6,7,8]可以較好的解決這個(gè)問題。下面我們將先簡單介紹一下這兩種調(diào)度算法,然后在分析不合理調(diào)度產(chǎn)生原因的基礎(chǔ)上,提出一種新的改進(jìn)算法。
2 兩類基于LAUC的信道調(diào)度算法
2.1重新調(diào)度算法
重新調(diào)度算法的主要思想是一個(gè)已經(jīng)調(diào)度的BDP可以被重新調(diào)度到另一個(gè)可用波長上,以容納新的突發(fā)請求。一旦重調(diào)度成功,需要發(fā)送一個(gè)"NOTIFY"消息,通知下一個(gè)節(jié)點(diǎn)突發(fā)數(shù)據(jù)包改變后的波長,以便其修改該包的入口信道設(shè)置[2]。在調(diào)度與重調(diào)度的每一步,仍然應(yīng)用LAUC的"最遲可用信道"思想。在文獻(xiàn)[2]中提到了一種ABR(Active Burst Re-scheduling)算法,該算法在每個(gè)BDP的請求(即與該BDP對應(yīng)得BHP)到達(dá)時(shí),按LAUC方式安排信道,一旦調(diào)度成功(安排了某個(gè)信道Di).就檢查其他信道的最后一個(gè)突發(fā)包是否可以"移動"到信道Di,當(dāng)存在多個(gè)可能性時(shí),找出其中最新的一個(gè)進(jìn)行重調(diào)度。對圖1所示情況來說,當(dāng)BDP4被調(diào)度安排到信道D2后,已調(diào)度的DBP3符合ABR算法的條件,被重新調(diào)度到信道D2,而DBP5將可以被調(diào)度到D1,從而降低了丟包率。圖2說明了這一重調(diào)度過程。
ABR算法的優(yōu)點(diǎn)是提高了數(shù)據(jù)信道利用率(與LAUC相比),降低了丟包率:其缺點(diǎn)是由于"朝令夕改",追發(fā)的NOTIFY消息增加了控制信道的負(fù)擔(dān),同時(shí)也對核心節(jié)點(diǎn)的處理能力提出了更高的要求。文獻(xiàn)[2]指出,ABR的計(jì)算量近似為LAUC的兩倍,但小于LAUC-VF。
2.2 成組調(diào)度算法
文獻(xiàn)[6,7,8]分別提出了幾種調(diào)度算法,雖然其具體實(shí)現(xiàn)過程各異,但都存在一個(gè)共同之處,即核心節(jié)點(diǎn)每次調(diào)度都是以一組BHP為單位進(jìn)行的,在本文中統(tǒng)稱之為成組調(diào)度算法。文獻(xiàn)[8]提出了一種最小間隙組調(diào)度(SGGS)算法,該算法的基本思想是核心節(jié)點(diǎn)對每個(gè)到達(dá)的BHP,先不分配信道,而是按其對應(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)度算法也存在同樣的問題,即在提高信道利用率的同時(shí)付出了系統(tǒng)偏置時(shí)間延長的代價(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á)順序不一致.就會產(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á),就會產(chǎn)生不合理調(diào)度。若一個(gè)BHP對應(yīng)的BDP符合上述條件(即di>L),我們就稱該BHP存在"隱患"。圖3中的BDP3對應(yīng)的BHP就存在"隱患",因?yàn)樗c信道D2的最遲可用時(shí)刻之間的問隔d2>L。當(dāng)一個(gè)存在"隱患"的BHP到達(dá)核心節(jié)點(diǎn)時(shí),一次不合理的調(diào)度就很有可能會發(fā)生(究竟能否發(fā)生還要視其后到達(dá)的BHP所攜帶的信息而定)。
3.2 改進(jìn)調(diào)度算法的提出
針對上述情況,我們提出了一種基于LAUC算法的改進(jìn)調(diào)度算法。該算法的核心思想是主動去發(fā)現(xiàn)存在不合理"隱患"的BHP.并試圖通過等待分析其后的一個(gè)BHP所攜帶的BDP到達(dá)情況來出合理的決定。當(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ù)上述過程。在該算法中,具體分配某個(gè)BDP時(shí),按照LAUC的最遲可用信道思想進(jìn)行。
為防止等待時(shí)間過長,可設(shè)定一個(gè)最大等待時(shí)間Tmax,當(dāng)Tmax內(nèi)無BHP到達(dá)時(shí),結(jié)束等待,調(diào)度當(dāng)前BHP。由于只須等待一個(gè)BHP,該算法的偏置時(shí)間延長量與所有成組調(diào)度算法相比是最小的。
3.3 程序流程圖及變量說明
圖4給出了該算法的程序流程圖。相關(guān)變量說明如下:
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:存放最小間隔對應(yīng)的信道編號的兩個(gè)變量;
L:所有BDP的最大持續(xù)時(shí)間:
Lmax:事先設(shè)定的等待時(shí)間。
4 結(jié)論
在數(shù)據(jù)信道調(diào)度算法中,提高信道利用率和降低計(jì)算復(fù)雜度是一對不可調(diào)和的矛盾。本文提出的改進(jìn)算法由于采取了主動尋找存在"隱患"BHP的策略,其信道利用率高于LAUC算法及SGGS算法(N=2時(shí)),同時(shí)能解決一些特定的問題(例如圖1所示情況),降低了丟包率。作為代價(jià),新算法由于增加了在大于零的di中輪詢di是否大于L的過程,在最壞的情況下計(jì)算量將比LAUC算法多M次(僅就算法的時(shí)間復(fù)雜度來說,兩者都是O(M),相對LAUC算法而言偏置時(shí)間也有所延長。
評論