鄭 羽，胡積寶，董甲東,

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

基于Kautz圖和OPS的多層光分組交換網絡調度準則研究*

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

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

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

光分組交換；Kautz圖；無源星形耦合器；拓撲設計

0 引言

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

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

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

1 網絡模型和運用

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

圖1 KG(3，2)Kautz圖

節(jié)點數/N平均跳數/h鏈路負載/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網絡用于光分組交換網絡，這樣可以以類似Kautz圖的方式定義路由規(guī)則。對于同一層的兩個節(jié)點，可以使用一個Kautz圖的最優(yōu)路由算法，這在新的結構中也是最優(yōu)的。當源節(jié)點(ls，x)和目的節(jié)點(ld，x)根據層的位置判斷處于不同層時，可以把路由算法分成兩種情況。假設在一個單一Kautz圖上的最優(yōu)路由線路從一個節(jié)點x到節(jié)點y是 (x1，x2，…，xn，y1，y2，…，yk)，跳數等于n，這樣就知道:

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

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

以MKG(4，2，3)中節(jié)點(4，121)到節(jié)點(3，101)的路由為例，在KG(2，3)中，從(121)到(101)的最短路由是由跳數n為2的路由串(12101)決定的。在MKG(4，2，3)中，(4，121)到(3，101)的層差異是3(即(ld-ls+m) modm=(3-4+4) mod 4)，這個值比2大，因此，新的路由串是(12101)的擴展，會把跳數增加到至少3。因為新的路由串的左端和右端分別就是源節(jié)點和目的節(jié)點，這是不會變化的，最短的新的路由串的形式將變成121…101。因為源節(jié)點121的最后一個字母和目標節(jié)點的首字母101是相同的，一個不同于字母“1”的冗余的字母需要插入兩者之間，所以新的路由串是跳數等于4的(1212101)。表2說明了一些MKG的典型性能結果。

表2 一些MKG的性能

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

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

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

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

2.1控制問題

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

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

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

(2)“距離”法：距離目標節(jié)點路徑最短的數據包將獲得最高優(yōu)先級。

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

2.2使用單波長OPS耦合器

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

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

3 性能評估

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

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

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

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

4 結論

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

[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] 藍曉青,禹繼國.基于Kautz圖的新型多跳光網絡拓撲結構[C]. 北京地區(qū)高校研究生學術交流會通信與信息技術會議,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圖的服務覆蓋網帶寬約束路由算法[J].計算機應用，2010，30(6): 1443-1446.

2016-12-21)

鄭羽(1981-)，通信作者，男，碩士研究生，高級工程師，主要研究方向：計算機網絡、信息管理與信息系統(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的多層光分組交換網絡調度準則研究J.微型機與應用，2017,36(22)：70-73.

安徽省2016年高校自然科學基金重點項目(KJ2016A430)；安徽省教育廳教學研究項目(2016jyxm0628)