基于Kautz圖和OPS的多層光分組交換網(wǎng)絡(luò)調(diào)度準(zhǔn)則研究*

鄭 羽，胡積寶，董甲東,

(1.安慶師范大學(xué) 現(xiàn)代教育技術(shù)中心，安徽 安慶 246133； 2.安慶師范大學(xué) 物理與電氣工程學(xué)院，安徽 安慶 246133)

基于Kautz圖和OPS的多層光分組交換網(wǎng)絡(luò)調(diào)度準(zhǔn)則研究*

鄭 羽1，胡積寶2，董甲東1,2

(1.安慶師范大學(xué) 現(xiàn)代教育技術(shù)中心，安徽 安慶246133；2.安慶師范大學(xué) 物理與電氣工程學(xué)院，安徽 安慶246133)

多跳光網(wǎng)絡(luò)是滿足日益增長的互聯(lián)網(wǎng)服務(wù)應(yīng)用的最合適的解決方案。將常規(guī)的Kautz圖從一層擴(kuò)展為多層，以產(chǎn)生更多架構(gòu)上的變化。相鄰層之間采用常規(guī)Kautz圖的系統(tǒng)連接方式，并由此提出了一種基于屬性的路由算法。采用光無源星形耦合器來實(shí)現(xiàn)新的拓?fù)浣Y(jié)構(gòu)。為了解決中間節(jié)點(diǎn)爭用問題，評估并比較了三個調(diào)度準(zhǔn)則，主要原則是它們提高可用性的能力。

光分組交換；Kautz圖；無源星形耦合器；拓?fù)湓O(shè)計

0 引言

光纖技術(shù)在當(dāng)前的通信網(wǎng)絡(luò)中發(fā)揮著重要的作用。光網(wǎng)絡(luò)可能是單跳或者多跳。一個多跳網(wǎng)絡(luò)不需要快速調(diào)整收發(fā)器或任何預(yù)傳輸?shù)膮f(xié)調(diào)。從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的流量可能會經(jīng)過一個或多個中間節(jié)點(diǎn)。流量在這些節(jié)點(diǎn)間經(jīng)歷了光-電-光(O/E/O)的轉(zhuǎn)換，在被處理前以不同的波長通過另一個連接被發(fā)送。節(jié)點(diǎn)可以是任何產(chǎn)生、接收和路由數(shù)據(jù)包的終端。關(guān)于多跳光網(wǎng)絡(luò)的設(shè)計已經(jīng)提出了很多的邏輯拓?fù)浣Y(jié)構(gòu)，其中Kautz圖是一個可行的選擇。相比于其他已知的正則圖，如de Bruijn圖(DBG)或Shuffle Net圖[1]，Kautz 圖在相同節(jié)點(diǎn)度的情況下平均跳數(shù)最小。此屬性使得Kautz圖是作為多跳光網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的很好的選擇[2-3]。Kautz圖已在光網(wǎng)絡(luò)中有不同形式的應(yīng)用，如單一的Kautz圖和棧Kautz圖(SKG)[4]。SKG網(wǎng)絡(luò)的設(shè)計通過堆疊系列的正則Kautz圖和兩層節(jié)點(diǎn)之間的連接形成一個小的分區(qū)OPS(光學(xué)無源星形)網(wǎng)絡(luò)。這種拓?fù)浣Y(jié)構(gòu)通過使用低度操作耦合器可以支持大型的網(wǎng)絡(luò)。在這種網(wǎng)絡(luò)中，設(shè)備的總數(shù)仍然很多，控制任務(wù)繁重。

本文目的在于設(shè)計一個靈活、易于實(shí)施的數(shù)據(jù)包交換網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[5-6]。一個主要目標(biāo)是決定在復(fù)雜度、靈活性和可實(shí)施方面具有良好性能的邏輯網(wǎng)絡(luò)架構(gòu)，還要對建議的拓?fù)浣Y(jié)構(gòu)的路由算法進(jìn)行檢查。為了實(shí)現(xiàn)目標(biāo)，結(jié)合Kautz圖和多層拓?fù)涞膬?yōu)點(diǎn)。此網(wǎng)絡(luò)架構(gòu)能夠克服Kautz圖網(wǎng)絡(luò)的一些缺陷。同時也會考慮OPS耦合器的實(shí)施以及用于解決爭用的三個調(diào)度方案[7-8]的分析。

本文首先提出了一個多層網(wǎng)絡(luò)模型；然后使用單波長和多波長OPS耦合器來設(shè)計模型的架構(gòu)；接著提出了模擬結(jié)果，并對其進(jìn)行了比較和分析，討論了如何用目前的技術(shù)來實(shí)現(xiàn)；最后，基于分析做了討論。

1 網(wǎng)絡(luò)模型和運(yùn)用

為了介紹多層拓?fù)涞亩x和操作，總結(jié)了Kautz圖KG(d，k)的屬性。G=(V，E)是一個Kautz圖，V是節(jié)點(diǎn)集，E是邊集，點(diǎn)入度和點(diǎn)出度為d，直徑為k。每個頂點(diǎn)被標(biāo)記為一個長度為k的串，如(x1，x2，…,xk)。每個字母都是從d+1個字母表中選擇的。每個標(biāo)簽的串都有一個條件，即沒有兩個連續(xù)的字母是一樣的。當(dāng)且僅當(dāng)頂點(diǎn)X的最后k-1個字母和頂點(diǎn)Y的最后k-1個字母是一樣的，兩個頂點(diǎn)間才會有一條邊。如頂點(diǎn)(x1，x2，…，xk)與d個頂點(diǎn)(x2，x3，…,xk，z)相鄰，這里z是任意一個與Xk不一樣的字母。在Kautz圖中，從節(jié)點(diǎn)X到節(jié)點(diǎn)Y的最優(yōu)化(短)的路由路徑是由一個路由串(x1，x2，…,xn+d)決定的，這個串代表了一系列的n跳。圖1是一個(2，3)圖。作為一個正則圖，Kautz圖的應(yīng)用非常有限，因?yàn)槊總€節(jié)點(diǎn)都要遵守定義好的連接模式。表1所示為KG圖與OBG圖及ShuffleNet圖在各個性能參數(shù)上的比較。

圖1 KG(3，2)Kautz圖

節(jié)點(diǎn)數(shù)/N平均跳數(shù)/h鏈路負(fù)載/LKG(3，3)362．5918．44(4，4)3203．67212．58(4，5)12804．651168．39DBG(3，3)272．4821．48(4，5)10244．582344．92ShuffleNet(3，3)182．7212．33(4，7)10245．171323．00

MKG網(wǎng)絡(luò)用于光分組交換網(wǎng)絡(luò)，這樣可以以類似Kautz圖的方式定義路由規(guī)則。對于同一層的兩個節(jié)點(diǎn)，可以使用一個Kautz圖的最優(yōu)路由算法，這在新的結(jié)構(gòu)中也是最優(yōu)的。當(dāng)源節(jié)點(diǎn)(ls，x)和目的節(jié)點(diǎn)(ld，x)根據(jù)層的位置判斷處于不同層時，可以把路由算法分成兩種情況。假設(shè)在一個單一Kautz圖上的最優(yōu)路由線路從一個節(jié)點(diǎn)x到節(jié)點(diǎn)y是 (x1，x2，…，xn，y1，y2，…，yk)，跳數(shù)等于n，這樣就知道:

(1)如果n≥(ld-ls+m) modm：路由串將和在單一Kautz圖上一樣。路由的開始n-m個節(jié)點(diǎn)將位于源層中。剩余m節(jié)點(diǎn)的標(biāo)簽和最短路由上最后m個節(jié)點(diǎn)的是一樣的，在每一個步驟中，每個節(jié)點(diǎn)的層數(shù)將增加1。

(2)如果n≤(ld-ls+m) modm：在這種情況下，路由字符串將擴(kuò)展匹配層的差異。一些冗余的節(jié)點(diǎn)必須插入到最優(yōu)(最短)路由路徑以保持連接關(guān)系，即在路由串中不能分配兩個相同的相鄰字母。新的路由串的跳數(shù)大于或等于處在不同層的源節(jié)點(diǎn)和目的節(jié)點(diǎn)的跳數(shù)。路由規(guī)則將類似于第一種情況，即首先在源層拿一些跳數(shù)。

以MKG(4，2，3)中節(jié)點(diǎn)(4，121)到節(jié)點(diǎn)(3，101)的路由為例，在KG(2，3)中，從(121)到(101)的最短路由是由跳數(shù)n為2的路由串(12101)決定的。在MKG(4，2，3)中，(4，121)到(3，101)的層差異是3(即(ld-ls+m) modm=(3-4+4) mod 4)，這個值比2大，因此，新的路由串是(12101)的擴(kuò)展，會把跳數(shù)增加到至少3。因?yàn)樾碌穆酚纱淖蠖撕陀叶朔謩e就是源節(jié)點(diǎn)和目的節(jié)點(diǎn)，這是不會變化的，最短的新的路由串的形式將變成121…101。因?yàn)樵垂?jié)點(diǎn)121的最后一個字母和目標(biāo)節(jié)點(diǎn)的首字母101是相同的，一個不同于字母“1”的冗余的字母需要插入兩者之間，所以新的路由串是跳數(shù)等于4的(1212101)。表2說明了一些MKG的典型性能結(jié)果。

表2 一些MKG的性能

從表2中能看出，當(dāng)層數(shù)m接近單個圖的直徑d的時候，跳度的平均數(shù)量會變得更小。通過選擇不同的組合層和圖的大小，可以獲得不同給定大小的MKG，然后可以選擇具有最佳性能的MKG。這種類型的網(wǎng)絡(luò)設(shè)計顯然有更多的靈活性。

注意，路由路徑可以動態(tài)地取決于所需的網(wǎng)絡(luò)條件和所需要的跳度數(shù)。首先，只要未完成的跳度的數(shù)量不小于從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的層數(shù)，跳度數(shù)可以在同一層或兩個相鄰層上。在上面的例子中，不改變節(jié)點(diǎn)的標(biāo)簽，可以讓層序列變成4-1-1-2-3或4-1-2-2-3或4-1-2-3-3。其次，可以使用自適應(yīng)路由，而不是固定的路由，因?yàn)檎麄€路由路徑可以用路由字符串(x1，x2，…，xn，y1，y2，…，yk)表示，通過插入一些冗余的字母到字符串來調(diào)整中間節(jié)點(diǎn)，同時保持第k個和最后k個字母分別成為源節(jié)點(diǎn)和目的節(jié)點(diǎn)。這個插入將產(chǎn)生更多的跳度數(shù)，不過改變流量將變得更加靈活。

2 OPS耦合器的實(shí)現(xiàn)

采用d×d的OPS耦合器來實(shí)現(xiàn)。網(wǎng)絡(luò)中的每個節(jié)點(diǎn)連接到兩個OPS耦合器，一個連接同一層的節(jié)點(diǎn)，另一個連接到下一層的節(jié)點(diǎn)。那些連接到相同目的節(jié)點(diǎn)的節(jié)點(diǎn)也會連接到相同的OPS耦合器上。盡管MKG的節(jié)點(diǎn)的度數(shù)是2d，但是需要d×d的OPS耦合器。度數(shù)偏低，更易于實(shí)現(xiàn)。需要一個時間段(或是稱為一個時間步)的數(shù)據(jù)包從一個節(jié)點(diǎn)傳播到另一個節(jié)點(diǎn)。因此，整個網(wǎng)絡(luò)可以被認(rèn)為是運(yùn)行在連續(xù)的時間段。所有時段都包含這一系列步驟。

2.1控制問題

對MKG的每一層，選擇一個節(jié)點(diǎn)作為節(jié)點(diǎn)組的控制節(jié)點(diǎn)，節(jié)點(diǎn)組共享兩個相同的OPS耦合器。節(jié)點(diǎn)的操作受節(jié)點(diǎn)組的控制節(jié)點(diǎn)的控制。組中的任何節(jié)點(diǎn)組都可以成為控制節(jié)點(diǎn)組，它的任務(wù)是為了收集所有傳遞節(jié)點(diǎn)組的數(shù)據(jù)包的頭信息和發(fā)送控制信息，并指導(dǎo)節(jié)點(diǎn)的操作。當(dāng)兩個或兩個以上的數(shù)據(jù)包到達(dá)一個或多個與目的地相同的輸出鏈接節(jié)點(diǎn)時，需要訪問相同的具有相同波長的OPS耦合器，這就可能發(fā)生爭用。必須采取一些調(diào)度原則來解決爭用問題，比如在數(shù)據(jù)包通過OPS耦合器時，賦予它們不同的優(yōu)先級。只要緩沖區(qū)非滿，不能獲得傳輸許可的數(shù)據(jù)包存儲在緩沖區(qū)中。

(1)“延遲”法：在當(dāng)前序列步驟中累計最長延遲的數(shù)據(jù)包將獲得最高優(yōu)先級。延遲包括緩沖時間和傳輸時間。

圖2 單一波長環(huán)境中的平均延遲

(2)“距離”法：距離目標(biāo)節(jié)點(diǎn)路徑最短的數(shù)據(jù)包將獲得最高優(yōu)先級。

(3)“時間等待”法：在當(dāng)前緩沖區(qū)具有等待時間最長的數(shù)據(jù)包將獲得最高優(yōu)先級。

2.2使用單波長OPS耦合器

圖3 采用多波長的MKG(4.2.3)性能考慮(“延遲”的方法)

OPS耦合器是一種能夠匹配網(wǎng)絡(luò)需求和應(yīng)用組件技術(shù)的可行的選擇。設(shè)備雖簡單，但潛力無限。第一個實(shí)現(xiàn)模型利用單波長OPS耦合器，它不需要昂貴和復(fù)雜的可調(diào)收發(fā)器。目前，可調(diào)組件仍然昂貴，很難制造，所以單波長法被認(rèn)為是第一個可行的方法。每個節(jié)點(diǎn)配備固定波長發(fā)射端和接收端。在任意時間，每個耦合器中只有一個波長是可用的，這意味著一次只有一個節(jié)點(diǎn)可以訪問某個OPS耦合器。如果沒有控制機(jī)制來區(qū)分輸入和輸出，每個輸入和輸出連接都能夠接收和傳輸同等優(yōu)先級的信號。在各個時間段，在一個OPS耦合器中允許一個節(jié)點(diǎn)發(fā)送一個數(shù)據(jù)包。當(dāng)發(fā)生爭用時，只有滿足某些條件的數(shù)據(jù)包可以通過耦合器。雖然信號傳遞到所有輸出鏈接，但只有一個接收端可以接收數(shù)據(jù)包。

3 性能評估

這里模擬的主要性能標(biāo)準(zhǔn)是延遲，定義為持續(xù)時間(在數(shù)量的序列步驟)即數(shù)據(jù)包的生成時間到其服務(wù)完成時間，即數(shù)據(jù)包需要傳輸和緩沖的時間總數(shù)。之所以選擇延遲作為分析的目標(biāo)，與光信號的傳輸特性有關(guān)。為了補(bǔ)償長距離光纖傳輸中的功率損耗，將使用光放大器，這將帶來更多的非線性效應(yīng)，降低信噪比。因此，在一個良好的光學(xué)結(jié)構(gòu)設(shè)計中，減少延遲是一個重要的目標(biāo)。選擇了兩個網(wǎng)絡(luò)來進(jìn)行分析，分別為有48節(jié)點(diǎn)的MKG(4，2，3)和有540個節(jié)點(diǎn)的MKG(5，3，4)。

圖2顯示在單一波長情況下的平均時延隨數(shù)據(jù)包到達(dá)率的變化。注意水平軸也是標(biāo)準(zhǔn)化的負(fù)載(一個新的數(shù)據(jù)包在每個時間段生成的節(jié)點(diǎn)概率)，因?yàn)榉?wù)時間也正好是一個時間段。圖3和圖4是多波長的平均延遲和延遲分布的情況，從圖4可以看出，在MKG(4，2，3)網(wǎng)絡(luò)的平均延遲與負(fù)載的增加呈指數(shù)增長，正如預(yù)期的一般延遲-吞吐量關(guān)系的經(jīng)典排隊論。當(dāng)負(fù)載接近30%時，延遲大大增加。通常情況下，網(wǎng)絡(luò)的性能將是不可接受的非常高的延遲。從圖4(b)看到，MKG(5，3，4)中這種情況會出現(xiàn)得更早，也就是說，在圖4(a)中負(fù)載是0.1而不是0.3。估計第二種網(wǎng)絡(luò)的規(guī)模將是以前的10倍并且更復(fù)雜。

結(jié)果表明， 與MKG(4，2，3)單一波長的情況相比，圖4中的平均延遲以同樣的方式增加?？墒?，在相同的網(wǎng)絡(luò)延遲情況下，多波長網(wǎng)絡(luò)能夠比單一波長網(wǎng)絡(luò)支持兩倍的負(fù)載。顯然，這性能的改進(jìn)是基于兩個波長的代價而不是單一波長的使用率。類似的結(jié)論可以從MKG(5.3.4)中通過比較圖3(b)和圖4(a)得出。

圖4 采用多波長的MKG(5.3.4)性能考慮(“延遲”的方法)

4 結(jié)論

本文提出了一個基于多層網(wǎng)絡(luò)結(jié)構(gòu)的Kautz圖(MKG)，并且已經(jīng)建模和模擬了使用光分組交換OPS耦合器的MKG網(wǎng)絡(luò)的性能，這種被動的OPS可以將延遲限制到一個可接受的范圍內(nèi)。當(dāng)使用可調(diào)的接收器和發(fā)射器時，性能有明顯改善。提出了可以實(shí)現(xiàn)預(yù)定目標(biāo)的三個調(diào)度爭用解決方案。對一個低負(fù)載的小規(guī)模網(wǎng)絡(luò)，它們沒有表現(xiàn)出明顯的差異。然而，對于一個更大網(wǎng)絡(luò)或更高的負(fù)載，“距離”方法可以用更少的序列步驟提供更多的數(shù)據(jù)包，而“等待時間”方法在一定數(shù)量的步驟以后會變得更快。根據(jù)網(wǎng)絡(luò)的需求，可以選擇恰當(dāng)?shù)姆椒ā?/p>

[1] BANERJEE S， JAIN V， SHAN S.Regular multihop logical topologies for lightware networks[J].IEEE Communications Surveys，1999,2(1): 2-18.

[2] PANCHAPAKESAN G，SENGUPTA A. On multihop optical network topology using Kautz digraphs[J].IEEE INFOCOM’1995, 1995: 675-682.

[3] RAVIKUMAR C P，RAI T，VERMA V.Kautz graphs as attractive logical topologies in multihop lightware networks[J]. ComputerCommunications，1997,20(14): 1259-1270.

[4] COUDET D，F(xiàn)ERREIRA A，PERENNES S.Multiprocessor architectures using multi-hop multi-OPS lightwave networks and distributed control[J]. IEEE International Parallel Processing Symposium, IPPS 1998，1998: 151-155.

[5] GOUDERT D S，MARCHAND P J，HARVEY P，et al.Photorefractive beam splitter for free-space optical interconnections[J].Applied Optics，1998,37(26): 6178-6181.

[6] 藍(lán)曉青,禹繼國.基于Kautz圖的新型多跳光網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[C]. 北京地區(qū)高校研究生學(xué)術(shù)交流會通信與信息技術(shù)會議,2008.

[7] Zhang Zhensheng，ACAMPORA A S. Performance analysis of multihop lightware networks with hot patato routing and distance-age-priorities[C]. IEEE Tenth Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM’91,1994,42(8): 2571-2581.

[8] 王玉林，游紅，李廣軍.基于Kautz圖的服務(wù)覆蓋網(wǎng)帶寬約束路由算法[J].計算機(jī)應(yīng)用，2010，30(6): 1443-1446.

2016-12-21)

鄭羽(1981-)，通信作者，男，碩士研究生，高級工程師，主要研究方向：計算機(jī)網(wǎng)絡(luò)、信息管理與信息系統(tǒng)。E-mail:fangshuan@126.com。

Research on scheduling criteria of multi layer optical packet switchingnetwork based on Kautz diagram and OPS

Zheng Yu1, Hu Jibao2, Dong Jiadong1,2

(1. Modern Education and Techonology Center, Anqing Normal University, Anqing 246133, China； 2. Physics and Electronic Engineering department, Anqing Normal University, Anqing 246133, China)

The multihop optical network is the most suitable scheme to satisfy the growing application of Internet service. This article develops the ordinary Kautz graph from one layer to multiple layers, which can produce more change in frame. Ordinary Kautz graph connecting system is used to connect adjacent layers, and by which a kind of routing algorithm based on its property has been put forward. Optical passive star is employed to achieve new topology. In order to solve the middle joints to be contented, we’ve evaluated and compared three dispatch criterions. The main principle is their ability to raise the possibility for use.

optical packet switching; Kautz graph; passive star coupler; topology design

TP399

A

10.19358/j.issn.1674- 7720.2017.22.019

鄭羽，胡積寶，董甲東.基于Kautz圖和OPS的多層光分組交換網(wǎng)絡(luò)調(diào)度準(zhǔn)則研究J.微型機(jī)與應(yīng)用，2017,36(22)：70-73.

安徽省2016年高校自然科學(xué)基金重點(diǎn)項(xiàng)目(KJ2016A430)；安徽省教育廳教學(xué)研究項(xiàng)目(2016jyxm0628)