時(shí)隙可變長分組緩存調(diào)度算法

杜曉萍，陳名松，王 寧

(桂林電子科技大學(xué)光通信研究所，廣西 桂林 541004)

為了適應(yīng)DWDM技術(shù)所帶來的更高核心節(jié)點(diǎn)交換性能需求，全光交換技術(shù)應(yīng)運(yùn)而生，它不需要進(jìn)行光電轉(zhuǎn)換，數(shù)據(jù)交換在光域中完成，除了能提供很高的帶寬外，還可以提供高速的數(shù)據(jù)速率、透明的數(shù)據(jù)格式和靈活的配置，它也能消除電域所帶來的瓶頸[1-2]。然而光分組交換網(wǎng)絡(luò)存在著分組沖突的問題，在同一時(shí)間、同一波長的兩個(gè)或兩個(gè)以上的分組需要到達(dá)同一個(gè)輸出端口時(shí)，必然會(huì)造成分組沖突。在電域中，分組交換中出現(xiàn)的分組沖突可以由隨機(jī)訪問存儲(chǔ)器(RAM)解決。但在光域中，光RAM還不成熟，不能應(yīng)用在光分組交換中。因此，為了解決光分組交換的分組沖突問題，以下幾種方法被提出:波長轉(zhuǎn)換、空間上的偏移路由和時(shí)間上的光纖緩存?；诠饫w延遲線(FDL)的光緩存即為時(shí)間上的緩存，目前被廣泛地應(yīng)用于解決分組沖突。但是FDL只能提供固定數(shù)量的時(shí)延，緩存性能是否能通過使用傳統(tǒng)的排隊(duì)模型準(zhǔn)確地獲得，還需要考慮符合緩存結(jié)構(gòu)的排隊(duì)調(diào)度算法。分組交換的排隊(duì)調(diào)度算法對分組交換結(jié)構(gòu)的吞吐量、平均時(shí)延和分組丟失率等性能指標(biāo)有著較大的影響[3]，交換調(diào)度的設(shè)計(jì)是整個(gè)OPS系統(tǒng)的關(guān)鍵，是對OPS網(wǎng)絡(luò)性能影響最大的一個(gè)環(huán)節(jié)。緩存調(diào)度算法主要功能是根據(jù)光分組的信息和節(jié)點(diǎn)的狀態(tài)信息進(jìn)行資源的調(diào)度，從而提供對交換矩陣、FDL的配置，為光分組建立全光的透明通路。目前，支持異步可變長分組的光分組交換的調(diào)度算法有很多[4-11]，在文獻(xiàn)[8-11]中，主要應(yīng)用了大量的可變長波長轉(zhuǎn)換器，但可變長波長轉(zhuǎn)換目前仍然難以實(shí)現(xiàn)，并且價(jià)格也很昂貴。在這些文獻(xiàn)中，都沒有考慮到利用光線延遲線所帶來的固有缺陷，即將當(dāng)前的緩存資源延緩到下一時(shí)刻，占用下一時(shí)刻的緩存資源，從而使下一時(shí)刻有更加嚴(yán)重的分組丟失率。因此，本文的算法不依靠波長轉(zhuǎn)換器，針對FDLS緩存結(jié)構(gòu)這一不足，提出了一種改進(jìn)的算法——時(shí)隙可變長分組緩存調(diào)度算法SVPB(slotted variable-lengthpacket-capable buffer)。

1 輸出緩存結(jié)構(gòu)

所提出的算法是依據(jù)N×N的通用輸出緩存結(jié)構(gòu)設(shè)計(jì)的，該結(jié)構(gòu)由N個(gè)1×N的交換矩陣和N×1的緩存結(jié)構(gòu)，以及一個(gè)處理光分組信號的調(diào)度控制器組成，該結(jié)構(gòu)能處理異步可變長光分組的交換[12]，如圖1所示。

圖1 參考的輸出緩存型交換結(jié)構(gòu)

當(dāng)光分組從輸入端輸入，光分組的分組頭信息(目的地址、分組長度等)被提取到調(diào)度控制器中進(jìn)行處理，調(diào)度器調(diào)度光分組到達(dá)目的輸出端口輸出或緩存器進(jìn)行緩存。調(diào)度控制器處理信息需要一定的時(shí)間，所以在輸入端增加了提供固定時(shí)延的光纖延遲線，延遲的時(shí)間等于分組頭處理的時(shí)間。B×1的緩存器采用B根光纖延遲線組成，每根延遲線的長度為單位長度D(也稱為延遲粒度)的整數(shù)倍(分別為0，D，2D，…，(B-1)D)，則該緩存器提供0～(B-1)D的離散延遲時(shí)間。

2 時(shí)隙可變長分組緩存調(diào)度算法SVPB

假設(shè)上述介紹的結(jié)構(gòu)的輸入端口N為4，輸入波長為1，延遲深度B為5(D0～D4)。分組到達(dá)的情況如圖2所示。

圖2 分組的到達(dá)情況

調(diào)度控制器有一個(gè)內(nèi)部調(diào)度時(shí)鐘，周期為T，調(diào)度器以周期T為一個(gè)時(shí)隙來處理到達(dá)的分組。在每個(gè)時(shí)隙里，調(diào)度器通過提取到達(dá)分組的信息，得到在該時(shí)隙中到來的分組數(shù)目、各個(gè)分組的到達(dá)時(shí)間和長度，從而根據(jù)先到先服務(wù)的排隊(duì)原則確定每個(gè)到達(dá)分組的處理順序和延遲時(shí)間。

圖2的時(shí)隙 T0中，有5個(gè)光分組(L0，L1，L2，L3和L4)到達(dá)(圖中白色的分組)，到達(dá)的時(shí)刻與該時(shí)隙的開始時(shí)刻時(shí)間間隔分別為t0，t1，t2，t3和t4，由于t4＜t2＜t0＜t3＜t1，根據(jù)先到先服務(wù)的排隊(duì)原則，調(diào)度器安排分組進(jìn)入FDL的順序?yàn)長4→L2→L0→L3→L1，因此，L4將進(jìn)入D0延遲線，L2將進(jìn)入D2，L0將進(jìn)入D4，如圖3所示。

在圖3中，各光分組在FDL緩存器中延遲的時(shí)間依據(jù)分組延遲時(shí)間公式得到

圖3 分組在FDL的順序和位置

式中:「x?表示取大于等于x的最小正整數(shù);tf表示緩存器所存儲(chǔ)的所有分組都離開緩存器，緩存器變?yōu)榭臻e的時(shí)刻。當(dāng)?shù)趇個(gè)光分組完全離開緩存器時(shí)，tf=ti+li+Δi－1D，它將為下一個(gè)到達(dá)的分組的時(shí)延做參考;ti表示第i個(gè)分組到達(dá)的時(shí)刻;則tf－ti等于第i個(gè)分組為避免發(fā)生沖突所需要的延遲時(shí)間。

在FDL緩存器中，進(jìn)行緩存的連續(xù)的兩個(gè)分組間會(huì)產(chǎn)生空隙Vi=ΔiD－tf+ti，空隙的大小不僅與FDL的粒度有關(guān)，還與分組的大小和分組到達(dá)的時(shí)間間隔有關(guān)?？障兜漠a(chǎn)生會(huì)導(dǎo)致額外的負(fù)荷，在異步操作中，這種空隙是最主要的損失之一。然而，如果所產(chǎn)生的空隙被后面到來的具有合適長度的光分組利用，就可以大大提高FDL緩存器的利用率，降低光分組丟失率，因此，考慮算法時(shí)應(yīng)該把空隙填充考慮進(jìn)去。由于D4是最大的一根延遲線，剩下的兩個(gè)分組因?yàn)闆]有可用的延遲線，采用了空隙填充算法，把沒有進(jìn)入延遲線的分組填充到可利用的空隙中，如圖中的L3分組。由于L1沒有可用的FDL和空隙，所以只能被丟棄。在處理完該時(shí)隙到來的所有分組后，開始調(diào)度下一個(gè)時(shí)隙到來的分組。

因此，提出的SVPB算法的步驟如下:

1)在第i個(gè)時(shí)隙[0，T]內(nèi)，分組從輸入端口n進(jìn)入交換節(jié)點(diǎn);

2)調(diào)度器查看各個(gè)輸入端口，記錄到達(dá)分組的情況，用 L(Ti，lj，tj)表示，Ti表示分組在第 i個(gè)時(shí)隙到達(dá)，li為分組的長度，ti為分組到達(dá)時(shí)距時(shí)隙的開始時(shí)刻的時(shí)間間隔;

3)根據(jù)先到先服務(wù)的原則，確定分組進(jìn)入緩存器的順序;

5)記錄隨后到達(dá)分組的時(shí)間間隔ti與第1個(gè)到達(dá)分組時(shí)間間隔tfirst的差值(ti–tfirst)，作為空隙的信息;

6)參看FDL使用情況，如果Δi≤B，表明有可用的FDL，把分組傳輸?shù)綍r(shí)延最小的可用的FDL上，然后轉(zhuǎn)到步驟2);

7)如果Δi＞B，表明沒有可用的FDL，然后比較到達(dá)分組的長度li與差值(ti–tfirst)的大小;

8)如果li＜ti–tfirst，分組插入該空隙中，然后轉(zhuǎn)到步驟2);

9)如果li≥ti–tfirst，表明沒有可以利用的空隙，分組丟棄，然后轉(zhuǎn)到步驟2);

10)第i個(gè)時(shí)隙的時(shí)間結(jié)束，進(jìn)入下一個(gè)時(shí)隙(i+1)，重復(fù)步驟2)～9)。

3 仿真分析

假設(shè)光分組以Poisson過程到達(dá)，光分組的長度分布遵從均值為1.0的負(fù)指數(shù)分布，F(xiàn)DL的粒度和時(shí)鐘周期也為0.8，輸入光纖為6，波長數(shù)為1，F(xiàn)DL緩存器的數(shù)量為10。下面對SVPB算法的性能進(jìn)行仿真實(shí)驗(yàn)，并與已有的對光分組進(jìn)行連續(xù)處理的空隙填充算法做比較，如圖4所示。

圖4 SVBP算法與已有空隙填充的分組丟失率

從仿真結(jié)果可以看出，在相同條件下，當(dāng)業(yè)務(wù)負(fù)載較小時(shí)，已有的空隙填充調(diào)度算法和SVBP算法性能差不多，但當(dāng)業(yè)務(wù)負(fù)載增大到0.6以上時(shí)，SVBP算法與已有的算法相比，能夠獲得更小的分組丟失率(PLR)。在較大的業(yè)務(wù)負(fù)載情況下(ρ=0.9)，已有調(diào)度算法由于無法立即處理發(fā)生沖突的分組，將不得不丟棄后面到來的分組，從而導(dǎo)致分組丟失率急劇提高，PLR幾乎接近于1。而SVBP算法由于上一時(shí)刻的分組處理并不影響現(xiàn)在的分組處理，PLR將趨于平穩(wěn)。

4 小結(jié)

由于FDL緩存器解決競爭沖突的思想是將當(dāng)前無法解決的情況延緩到下一時(shí)刻去解決，從而增加了下一時(shí)刻緩存器的負(fù)擔(dān)，即增加了下一時(shí)刻緩存器的輸入負(fù)載，導(dǎo)致下一時(shí)刻更加嚴(yán)重的競爭沖突。為了解決FDL緩存器的不足，提出了時(shí)隙可變長分組緩存調(diào)度算法SVPB，該算法以一個(gè)時(shí)隙為分組處理單元，在時(shí)隙中及時(shí)處理這段時(shí)間到來的全部分組，解決了FDL緩存器的不足，這種有效性在網(wǎng)絡(luò)負(fù)載較大的時(shí)候更加明顯。

[1]ZHENGHAO Z，YUANYUAN Y.Prioritized schduling in WDM packet switching networks with limited range wavelength conversion[C]//Proc.IEEE Global Telecommunications Conference.[S.l.]:IEEE Press，2004:1823-1827.

[2]“下一代通信技術(shù)和計(jì)算機(jī)技術(shù)對廣播電視發(fā)展的影響”項(xiàng)目組.下一代網(wǎng)絡(luò)的發(fā)展趨勢與業(yè)務(wù)融合(續(xù)一)[J].電視技術(shù)，2007，31(8):4-6.

[3]ERAMO V，LISTANTI M，DONATO M D.Performance evaluation of a bufferless optical packet switch with limited-range wavelength converters[J].IEEE Photonics Technology Letters，2004，16(2):644-646.

[4]CALLEGATI F.Optical buffers for variable length packets[J].IEEE Communicatioms Letters，2000，4(9):292-294.

[5]KITAYAMA K I，MURATA M.WDM fiber delay line buffer control for optical packet switching[C]//Proc.Optical Networking and Communications.Imrich Chlamtac:SPIE，2000:247-256.

[6]ALMEIDA R C，PELEGRINI J U，WALDMAN H.Delay-line buffer modeling for asynchronous optical networks[C]//Proc.Optical Networking and Communications.[S.l.]:SPIE，2003:381-391.

[7]HARAI H，MURATA M.Optical fiber-delay-line buffer management in output-buffered photonic packet switch to support service differentation[J].IEEE Journal on Selected Areas in Communications，2006，24(8):108-116.

[8]MURATA M，KITAYAMA K.Ultrafast photonic label switch for asynchronous packets of variable length[C]//Proc.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]:IEEE Press，2002:371 –380.

[9]CALLEGATI F，CORAZZA G，RAFFAELLI C.Exploitation of DWDM for optical packet switching with quality of service guarantees[J].IEEE J.Selected Areas in Communications，2002，20(1):190-201.

[10]WADA N，HARAI H，HARAI H.Photonic packet routing based on multiwavelength label switching using fiber Bragg gratings[C]//Proc.Optical Transmission Systems and Equipment for WDM Networking.[S.l.]:SPIE，2002:185-198.

[11]ROGIEST W，BRUNEEL H.Exact optimization method for an FDL buffer with variable packet length[J].IEEE Photonics Technology Letters，2010，22(4):242-244.

[12]WADA N，HARAI H.Optical code based photonic packet switch prototype-10 to 40Gbit/s，ultra-high speed，scalable packet switching[C]//Proc.7th IFIP Working Conference on Optical Network Design and Modelling.[S.l.]:IEEE Press，2003:1119-1132.