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

杜曉萍，陳名松，王 寧

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

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

1 輸出緩存結(jié)構

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

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

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

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

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

圖2 分組的到達情況

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10)第i個時隙的時間結(jié)束，進入下一個時隙(i+1)，重復步驟2)～9)。

3 仿真分析

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

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

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

4 小結(jié)

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

[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]“下一代通信技術和計算機技術對廣播電視發(fā)展的影響”項目組.下一代網(wǎng)絡的發(fā)展趨勢與業(yè)務融合(續(xù)一)[J].電視技術，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.