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

　　1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　3.3 程序流程圖及變量說明

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

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

　　t'、t"：存放BDF到達時刻的兩個變量：

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

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

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

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

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

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

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

　　4 結(jié)論

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