一種基於環路的混合交換光網絡的構造方法
2023-09-17 11:13:40 5
專利名稱：一種基於環路的混合交換光網絡的構造方法
技術領域：
本發明屬於光通信技術領域，它特別涉及光混合交換系統的交換結構設計技術。
背景技術：
波分復用技術(Wavelength Division Multiplexing)的出現開創了太比特傳輸帶寬的先河。至此，所需帶寬已不再成為決定網絡花費的首要因素。最初的光網絡是點與點之間光纖鏈路的互聯，光信號在網絡中的每一個節點都要轉化為電信號進行電處理，因此具有高的帶寬資源共享率。然而由於骨幹網絡的物理拓撲的連通度很低，網絡的電路由器處理的所有業務中，有大約70％的業務是轉發業務——仍然需要傳送一跳或多跳才能到達其目的節點的業務，這些轉發業務需要在途經的每一個節點處進行電處理。目前的情況是電域的處理速度遠遠低於網絡的傳輸速度，因此電域成為了光網絡的瓶頸。面對這個問題，研究者們提出了一些解決方案，由此，產生了WDM光網絡的三種基本交換技術——光電路交換(Optical Circuit Switching，OCS)，光分組交換(Optical Packet Switching，OPS)，光突發交換(Optical Burst Switching，OBS)。
光電路交換OCS通過動態尋路和波長分配建立端到端的光路(lightpath)。數據不需要光-電-光的轉換而直接通過光路(lightpath)到達目的節點，實現端到端的透明傳輸。但是，它不能實現光路的統計復用，帶寬利用率不高。由於受到波長連續性的限制，即便網絡中配置了波長變換器，所建的光路仍然會受到波長數目的限制。此外，光路的建立和拆除需要一定的時間，對於突發性強，變化頻繁的IP業務來說，OCS並不適用。
光分組交換OPS與傳統的分組交換網路類似，採用存儲轉發技術，能夠實現真正的光域交換，並且具有高的統計復用率和帶寬利用率，適合用於傳輸IP那樣突發性強的業務。但是，全光的分組交換在實現上存在若干難點，許多關鍵技術的突破有待於光器件技術的成熟，如靈活有效的光邏輯器件、光存儲器件，以及光域的同步技術等。
光突發交換OBS技術是兩種交換技術的折中。OBS網絡按照IP數據的目的地址和服務質量QoS(Quality of Service)匯聚成突發包Burst，並生成一個突發頭分組(Burst Head Packet)。突發頭分組BHP先於突發包Burst發送到獨立的控制信道，在途經的每一個交換節點處為突發包Burst預約波長資源。網絡中的節點一旦收到BHP，就會在Burst到達的時刻配置好交換矩陣，引導Burst到正確的出埠以到達其目的節點。由此，Burst實現了全光交換。相比波長路由光網絡而言，OBS網絡可以提供更好的帶寬利用率，相比OPS網絡而言，OBS網絡不需要光緩存或分組的分離，通過在網絡的邊緣節點匯聚合適的突發包，它能夠有效的應對網絡中動態變化的業務。
目前，研究者們不再追求一種網絡交換方式的單方面的性能指標，而是研究如何結合上述交換方式的優點，儘量避免或減少其缺點，協調好光域和電域的匹配，共同實現網絡交換。因此，提出了混合交換的概念 「如果一個光網絡同時結合了兩種或兩種以上的基本網絡技術，這個光網絡就被稱為混合交換光網絡。」 現有的混合交換光網絡大致分為三種類型——主從型，平行型和集成型。在主從型的混合交換光網絡中，Client層採用OBS/OPS交換，Server層採用波長交換，下層通過構建由光路組成的虛拓撲為上層提供服務。突發包/分組包只能在上層交換，而網絡中某些固定的業務流則通過下層的光路傳輸。這種模型的優點在於，由於Client層的一部分業務通過光路直接傳輸，因此減少了OBS/OPS的衝突，提高了處理效率。其缺點是該模型存在如何構建虛拓撲的問題，OBS/OPS對鏈路的利用率很高，而在虛拓撲問題中，隨著虛拓撲連通度的增加，鏈路利用率逐漸減少。如果構建密集的虛拓撲就需要在端節點增加額外的資源來補償減少的利用率，所以需要構建合適的虛拓撲來減少全網花費。此外，如何傳送突發頭分組BHP也是這種混合交換技術的問題所在。(見文獻Biao Chen，and JianpingWang，「Hybrid Switching and P-Routing for Optical Burst Switching Networks」，IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS，VOL.21，NO.7，SEPTEMBER 2003，pp.1071-1080.) 平行型的混合光網絡有OBS和OCS兩種傳輸方式，根據客戶服務需求的不同，使用不同的傳輸方式提供服務。邊緣節點根據業務流的特性，如帶寬、持續時間和QoS，將業務流區分為適合OBS傳輸和適合OCS傳輸的兩種業務。持續時間短(short-lived)、QoS要求較低的業務適合OBS傳輸，而持續時間長(long-lived)、佔用較多帶寬、QoS要求嚴格的業務適合OCS傳輸。邊緣節點決定業務用哪種方式傳輸，在傳輸過程中不會改變該業務的傳輸方式。對適用於OBS傳輸的業務，邊緣節點將業務流匯聚成突發數據，核心節點根據BHP對突發數據進行交換；而對適用於OCS傳輸的業務，則根據網絡中的資源使用情況為業務流分配波長和建立光路，因此，要求核心節點具備OBS交換和OCS交換的能力。平行型混合光網絡中的主要問題有 A邊緣節點如何有效的對業務流進行分類。
B資源分配問題。如何在OBS、OCS兩種傳輸方式之間合理的分配或動態的調整有限的網絡資源，是這種交換技術的難點所在。
集成型混合光網絡與前面兩種混合模型相比，把集成進一步深入。在集成型混合光網絡中，兩種技術同時享有相同的帶寬資源，每個節點都有OCS和OBS/OPS能力，並且每個節點都能決定數據的傳送模式。目前的集成型混合光網絡只有兩種，一種是ORION(Overspill Routing in Optical Network)(見文獻E.Van Breusegem，J.Cheyns，D.De Winter，D.Colle，M.Pickavet and P.Demeester，「A Broad view on Overspill Routing In Optical networksa real synthesis of packetand circuit switching」，Optical Switching and Networking，invited publication，toappear end 2004.)，另一種是OpMiGua(見文獻S.Bjornstad，M.Nord，D.R.Hjelme＂QoS differentiation and header/payload separation in optical packet switching usingpolarisation multiplexing＂，in proceedings of ECOC 2003，Rimini(Italy)，Sept.2003，Mo 3.4.6，pp.28，29.)，它們主要在實現上有所不同。兩種方式的共同特徵是每個節點都需要探測經過它每個數據包的當前狀態，並且在不影響光路上存在的採用波長交換的業務的情況下插入或提取OPS的數據包。兩種方式採用不同的調製技術在數據包上打光標籤，並在光路中間節點逐跳探測，並且還需要在光路上對數據進行直接插入，這些所需技術使光網絡實現的複雜度顯著增加。
上述的混合交換方式存在虛拓撲的構建，網絡實現困難以及如何合理的利用資源進行數據傳輸等問題，怎樣解決這些問題並充分利用基本交換技術的優點從而使網絡性能有更好的表現，成為一個有待解決的問題。
發明內容
本發明的目的是為了克服現有技術的不足，提供了一種基於環路的混合交換光網絡(Cycle-based Hybrid Switching Optical Network，CHSON)的構建方法。該方法有效的結合了OCS和OBS兩種交換方式，通過構建CHSON特有的虛拓撲以及設計網絡業務的處理流程，使網絡業務能夠靈活地根據網絡的狀況利用網絡資源。該方法不僅能夠有效地降低網絡的實現複雜度，而且在應對突發業務方面有良好的性能表現，增強了網絡的健壯性。
為了方便地描述本發明方案，首先將相關概念做如下定義 物理拓撲指由網絡中的一些節點/路由器和連接這些節點/路由器的光纖鏈路組成。
光路通過路由選擇和波長配置建立端到端的連接。
虛拓撲基於物理拓撲建立的所有光路的集合構成了網絡的虛拓撲。
H集合H集合是由1，…，n的無重複數字組成的長度小於等於n+1的數字串構成的集合，僅當長度為n+1時首尾數字可以相同。
H矩陣由H集合作為元素M(i，j)構成的矩陣M＝(M(i，j))n×m稱為H矩陣。
連接積設M＝{mi|i＝1，…，r}，N＝{nj|j＝1，…，s}均是H集合，則H集合M和N的連接積P仍是一個H集合 P＝M*N＝{mi*N|將N中數字串拼接到mi後的結果，mi∈M，拼接時，mi和N中數串無公共數字(除非連接後結果長度為n+1時，首尾數字可相同)或均不為空串，否則，結果為空串。} H鄰接矩陣設G＝(V，E)是有n個頂點的圖，E(G)是其邊集，V(G)是其頂點集。圖G的H鄰接矩陣被定義成這樣一個n階H矩陣M＝(M(i，j))n×n。其中 圖的H鄰接矩陣和圖的一般鄰接矩陣具有相似的性質。
通路矩陣n個頂點的圖G的長度為k的通路矩陣定義為 Mk＝Mk-1*M k＝2，...，n 這裡的M1為圖G的H鄰接矩陣，而M是將M1中不為空集Φ的集合元素中的數串刪去左邊首字符而得到的矩陣。
迴路是圖G＝(V，E)中的一條路徑(G有n個頂點，E(G)是其邊集，V(G)是其頂點集)，該路徑的起點和終點由一條邊相連，即為圖中的一條從起點出發最終可以回到起點的路徑。
迴路相等假設圖G＝(V，E)中兩條迴路A、B，如果A迴路上的所有節點組成的集合和B迴路上的所有節點組成的集合相等，並且A迴路從某個節點開始按照順時針(或逆時針)方向回到該節點的過程中所經歷的節點的順序與B迴路從某個節點開始到回到該節點的過程中經歷的節點的順序一致，則認為A迴路和B迴路相等。
Hamilton迴路一條能夠經過圖G＝(V，E)中每個節點恰好一次的迴路。
HLDA算法WDM光網絡的虛拓撲設計算法，具體內容參見文獻RajivRamaswami，Kumar N.Sivarajan，「Design of Logical Topologies forWavelength-Routed Optical Networks」，IEEE JOURNAL ON SELECTED AREASIN COMMUNICATIONS，VOL.14，NO.5，JUNE 1996. 混合時間和長度門限算法OBS突發包匯聚算法，具體內容參見文獻Xiaojun Cao，Jikai Li，Yang Chen，Chunming Qiao，「Assembling TCP/IP Packets inOptical Burst Switched Networks」，Proc.IEEE Globecom，2002. LAUC-VF算法OBS突發包的調度算法，具體內容參見文獻Yijun Xiong，Marc Vandenhoute and Hakki C.Cankaya，「Control Architecture in OpticalBurst-Switched WDM Networks」，IEEE Journal on Selected Areas inCommunications，vol.18，no.10(October 2000)，pp.1838-1851. Dijkstra算法經典的最短路算法，具體內容參見文獻Lu Feng，「Shortest PathAlgorithmsTaxonomy and Advance in Research」，Acta Geodaeticaet CartographicaSinica，vol.30，no.8，pp.269-275，2001(in Chinese). 光路表記錄從每個節點出發的由HLDA算法計算得出的所有光路的標號的表格。
路由轉發表根據OBS的虛拓撲和Dijkstra最短路路由算法計算出OBS網絡所有的數據包所需的在其途經的每個節點處的轉發埠，並將計算結果記錄於表格中。
光路緩存基於環路的混合交換光網絡的每一個節點都配備有一個電緩存，該電緩存分為光路緩存和溢出緩存兩個部分，其中，光路緩存的功能是為接入網數據流中的那些存在對應光路的數據提供緩存，並記錄光路緩存的存儲狀況。具體來說，就是通過查看光路表和光路緩存的存儲狀況，決定對進入本節點的數據包進行不同的處理——將數據包送入光路緩存並以OCS的交互方式發送數據包或者將數據包送至溢出緩存進行突發包的匯聚。
溢出緩存基於環路的混合交換光網絡的每一個節點都配備有一個電緩存，該電緩存分為光路緩存和溢出緩存兩個部分，其中，溢出緩存用於存儲來自光路緩存的數據包，並負責將這些數據包按照混合時間和長度門限算法匯聚成突發包，以OBS的交換方式將突發包發送入OBS網絡中。
Offset Time偏移時間，OBS網絡的突發頭分組BHP與其相應的突發包Burst之間的發送時間之差，用於彌補BHP在電域的處理延時。
業務量矩陣一個N×N的矩陣，N為網絡中節點的總數，第(i，j)個元素代表需要從節點i傳送到節點j的業務流的平均速率。注意該業務量矩陣為非對稱矩陣，即從節點i到節點j的業務流速率不一定等於從節點j到節點i的業務流速率。
節點業務流進入基於環路的混合交換光網絡的節點的業務流分為兩類，一類是核心網絡業務流，一類是接入網業務流。
接入網業務流針對基於環路的混合交換光網絡的節點業務流提出的，指從本地網絡進入CHSON網絡的IP分組業務流。
核心網業務流針對基於環路的混合交換光網絡的節點業務流提出的，指從CHSON網絡中的其他節點發送到本交換節點的業務流，它包含三種業務類型——BHP，Burst和IP分組。
本地地址每一個節點在網絡中都有自己的編號，這個編號就是其對應節點的本地地址。
本發明提供一種基於環路的混合交換光網絡構建方法，其特徵是它包括光突發交換OBS網絡虛拓撲的構建過程，光電路交換OCS網絡虛拓撲的構建過程，網絡節點對接入網業務流的處理過程，網絡節點對核心網業務流的處理過程，所述的光突發交換OBS網絡虛拓撲的構建過程，光電路交換OCS網絡虛拓撲的構建過程，網絡節點對接入網業務流的處理過程，網絡節點對核心網業務流的處理過程分別採用下面的步驟實現 光突發交換OBS網絡虛拓撲的構建過程採用以下步驟 步驟1 對給定N個節點構成的網絡的物理拓撲圖G的H鄰接矩陣M1，N為正整數，判斷H鄰接矩陣M1是否有全空的行或列，如果H鄰接矩陣M1有全空的行或列，則轉步驟10；如果H鄰接矩陣M1無全空的行或列，則由H鄰接矩陣M1構造矩陣M，轉步驟2；構造矩陣M的方法是將H鄰接矩陣M1中不為空集Φ的集合元素中的字符串刪去左邊首字符得到的矩陣M； 步驟2 按照通路矩陣的定義構造出長度為k的通路矩陣Mk＝Mk-1*M，k＝2，並轉步驟4； 步驟3 按照通路矩陣的定義構造出長度為k的通路矩陣Mk＝Mk-1*M； 步驟4 判斷通路矩陣Mk中的每行每列是否都有非空元素並且k是否小於N？如是，則k＝k+1，並轉步驟3；如否，則轉步驟5； 步驟5 判斷k是否等於N？如果k＝N，則將通路矩陣Mk主對角線上的元素放入集合A中，得到物理拓撲圖G的全部Hamilton迴路，並轉步驟6；否則轉步驟10； 步驟6 按照迴路相等的定義，找出集合A中的元素所代表的迴路中所有相等的迴路，在代表相等迴路的元素中，只保留其中的一個，其餘的全部刪除；得到集合A中所有的元素所代表的迴路均不相等，並轉步驟7； 步驟7 判斷集合A中的元素的個數，如果等於1，則轉步驟9；否則，則轉步驟8； 步驟8 對集合A中的所有元素所代表的迴路進行選擇，方法是 a)計算集合A中元素的數量，並記為I(I>1，且I為正整數)； b)根據已知的業務量矩陣T，計算集合A中每一個元素所代表的迴路的衡量值Ci(i為正整數，且i＝1，…，I)，衡量值Ci的計算方法如下 其中，N表示網絡的節點總數，Lij表示第i個環路上第j段鏈路實際承載的業務量；Tsd表示從節點s到節點d的業務量。Lij的計算方法如下
業務按照何種方向沿迴路傳送完全根據路由策略決定，這裡使用最短路路由策略，由Dijkstra算法計算出OBS網絡中所有節點對之間的最短路，業務沿著最短路傳送到其目的節點。
c)清空集合A，選取最小的衡量值Ci值所對應的元素放入集合A中； 步驟9 集合A中元素所代表的迴路即為OBS的虛拓撲； 步驟10 算法結束； 該過程的算法流程如圖2所示。
光電路交換OCS網絡虛拓撲的構建過程採用以下步驟 步驟1 計算OCS網絡的波長資源。由網絡中所有光纖鏈路的波長數量之和減去OBS網絡佔用的波長數量，得到OCS網絡的波長數量； 步驟2 根據步驟1的計算結果和已知的業務量矩陣T，利用HLDA算法建立OCS網絡的虛拓撲並生成相應的光路表； 該過程的算法流程如圖3所示。
網絡節點對接入網業務流的處理過程採用以下步驟 步驟1 針對進入網絡節點的數據包查看光路表(由OCS虛拓撲構建過程產生)，判斷是否存在以本地地址為起始節點、以數據包的目的地址為終節點的光路；如果存在，則轉步驟2，否則，將進入網絡節點的數據包送入溢出緩存並轉步驟3； 步驟2 判斷光路緩存是否由於存儲數據包的總量已經到達其容量上限而無法再存儲任何數據包；如果光路緩存不能再存儲任何數據包，則將該數據包送入溢出緩存並轉步驟3，否則，將數據包放入光路緩存並轉步驟5； 步驟3 將溢出緩存中的數據包利用混合時間和長度門限算法組裝成突發包，組裝完成後生成突發頭分組BHP，並轉步驟4； 步驟4 查找埠轉發表確定步驟3生成的突發頭分組BHP的轉發埠並且按照LAUC-VF算法在該埠的波長上進行突發包Burst的調度。如果調度成功，記錄波長的佔用時刻，發送突發頭分組BHP至控制信道並於Offset Time之後發送突發包Burst至數據信道；如果調度失敗，則銷毀突發頭分組BHP。
步驟5 判斷由步驟1找出的光路在當前時刻是否可以傳送該數據包？如是，則發送數據包；否則，數據包在光路緩存中繼續等待； 該過程的算法流程如圖4所示。
網絡節點對核心網業務流的處理過程採用以下步驟 步驟1 查看突發頭分組BHP的目的地址(雖然核心網絡業務包含三種類型，但是需要處理的業務只有突發頭分組BHP)。如果突發頭分組BHP的目的地址是本地地址，說明突發頭分組BHP的資源預約任務已經完成，只需銷毀突發頭分組BHP；如果突發頭分組BHP的目的地址不是本地地址，則從轉發表查找出該突發頭分組BHP的轉發埠； 步驟2 突發頭分組BHP在由步驟1找出的埠的所有波長上按照LAUC-VF算法調度其對應的突發包Burst。如果調度成功，則在記錄波長的佔用時間並修改突發頭分組BHP中的Offset Time之後發送突發頭分組BHP；如果調度失敗，則丟棄突發頭分組BHP； 該過程的算法流程如圖4所示。
以上四個過程構成了基於環路的混合交換光網絡的構造方法。
將網絡構造成為由OBS環路與OCS光路組合而成的虛拓撲，並利用一定的處理策略在其虛拓撲上實現網絡業務的傳送，是本發明實質性的創新內容。
本發明的創新點 相對於主從型，集成型和平行型等混合交換網絡，本發明的核心思想是將網絡構造成一種環形拓撲結構的OBS網絡和OCS網絡的結合體，將網絡中的大部分業務經一跳到達目的節點，滿足大多數情況下網絡的通信需求，當網絡業務發生小範圍變化的時候，光路無法承載的業務將沿著環形拓撲採用OBS的交換方式繼續傳送。該方法可以在一定範圍內應對網絡的突發性，使網絡穩定可靠。此外，該方法簡單有效，切實可行。
本發明提供的基於環路的混合交換光網絡，具有以下特點 1)基於環路的混合交換光網絡很好的集成了OCS和OBS兩種傳統的傳送方式，使得網絡既具有OCS的高效率又具有OBS的靈活性，對突發業務流，動態業務有較好的傳送能力。
2)基於環路的混合交換光網絡需要傳送的業務中超出OCS光路承載容量的那部分業務利用該網絡的環路資源進行傳送，提高了網絡的健壯性，使網絡更加穩定。
3)基於環路的混合交換光網絡靜態配置網絡節點以及IP業務的兩種傳送模式(OCS傳送和OBS傳送)，使得基於環路的混合交換光網絡方案實現容易，對器件要求低。
綜上所述，與傳統的混合交換光網絡的構造方法相比，本發明的組網技術更簡單有效，並且由網絡動態變化引起的網絡性能的惡化程度小，網絡運行更加穩定，具有較高的通信能力。此外，網絡算法的實現難度低，具有較高的實用價值。
圖1是本發明設計的基於環路的混合交換光網絡CHSON的結構示意圖 其中，基於環路的混合交換光網絡CHSON邏輯上分為兩層，光突發交換OBS層和光電路交換OCS層，一個CHSON節點由一個光突發交換OBS交換節點和一個光電路交換OCS交換節點構成； 其中，A、B、C、D表示光突發交換OBS交換節點，a、b、c、d表示光電路交換OCS交換節點。————表示CHSON網絡的物理拓撲，
是OBS節點和OCS節點的連接線，表示兩個節點的邏輯關係，
表示一個CHSON網絡節點的組成，…………表示由OCS網絡虛拓撲的構建過程建立起來的OCS網絡的虛拓撲，
表示由OBS網絡虛拓撲構建過程建立起來的OBS網絡的虛拓撲。
圖2是本發明光突發交換OBS網絡虛拓撲的構建過程的算法流程圖 圖3是本發明光電路交換OCS網絡虛拓撲的構建過程的算法流程圖 圖4是本發明網絡節點對業務流的處理流程圖
具體實施例方式 以下，我們通過一個實例，具體說明本發明的內容。
圖1是由四個節點A、B、C和D組成的網絡，網絡中的鏈路均為雙向鏈路，假定網絡中每根光纖上有四個波長，網絡的業務量矩陣根據本發明的設計方案，首先按照OBS虛拓撲的構建過程計算出一個迴路A-B-C-D-A並為迴路上的每條邊分配兩個波長，然後根據OCS虛拓撲的構建過程建立起12條光路，分別是a-b，a-b-c，a-d，b-a，b-c，b-a-d，c-d-a，c-b，c-d，d-a，d-c-b，d-c。
在大多數情況下，這12條光路能夠滿足網絡業務的傳輸需求(因為光路是根據網絡的業務量矩陣建立的，而業務量矩陣表示的是網絡業務的時間平均值)。當網絡的業務量發生變化的時候，即某一時刻的網絡的業務量不等於網絡業務量的平均值，這些光路有可能無法滿足某些業務的傳輸請求。假定某時刻光路a-d已經滿載，即光路的傳輸速率低於進入光路緩存的IP分組的速率而導致光路緩存已被佔滿，但是A點仍然有IP業務需要傳送到D點，那麼這些光路所不能承載的業務就稱為溢出業務。單純的OCS網絡不能及時有效地處理溢出業務，只能丟棄。而基於環路的混合交換光網絡採用網絡節點對接入網業務流的處理過程，通過切換到OBS的交換方式，利用環路A-B-C-D-A的容量傳送溢出業務，從而在一定程度上解決了網絡由於業務量的變化所帶來的丟包率問題，提高了網絡的穩定性。
權利要求
1.一種基於環路的混合交換光網絡構建方法，其特徵是它包括光突發交換OBS網絡虛拓撲的構建過程、光電路交換OCS網絡虛拓撲的構建過程、網絡節點對接入網業務流的處理過程、網絡節點對核心網業務流的處理過程；所述的光突發交換OBS網絡虛拓撲的構建過程、光電路交換OCS網絡虛拓撲的構建過程、網絡節點對接入網業務流的處理過程、網絡節點對核心網業務流的處理過程分別採用下面的步驟實現
所述的光突發交換OBS網絡虛拓撲的構建過程採用以下步驟
步驟1 對給定N個節點構成的網絡的物理拓撲圖G的H鄰接矩陣M1，N為正整數，判斷H鄰接矩陣M1是否有全空的行或列，如果H鄰接矩陣M1有全空的行或列，則轉步驟10；如果H鄰接矩陣M1無全空的行或列，則由H鄰接矩陣M1構造矩陣M，轉步驟2；構造矩陣M的方法是將H鄰接矩陣M1中不為空集Φ的集合元素中的字符串刪去左邊首字符得到的矩陣M；
步驟2 按照通路矩陣的定義構造出長度為k的通路矩陣Mk＝Mk-1*M，k＝2，並轉步驟4；
步驟3 按照通路矩陣的定義構造出長度為k的通路矩陣Mk＝Mk-1*M；
步驟4 判斷通路矩陣Mk中的每行每列是否都有非空元素並且k是否小於N？如是，則k＝k+1，並轉步驟3；如否，則轉步驟5；
步驟5 判斷k是否等於N？如果k＝N，則將通路矩陣Mk主對角線上的元素放入集合A中，得到物理拓撲圖G的全部Hamilton迴路，並轉步驟6；否則轉步驟10；
步驟6 按照迴路相等的定義，找出集合A中的元素所代表的迴路中所有相等的迴路，在代表相等迴路的元素中，只保留其中的一個，其餘的全部刪除；得到集合A中所有的元素所代表的迴路均不相等，並轉步驟7；
步驟7 判斷集合A中的元素的個數，如果等於1，則轉步驟9；否則，則轉步驟8；
步驟8 對集合A中的所有元素所代表的迴路進行選擇，方法是
a)計算集合A中元素的數量，並記為I；I>1，且I為正整數；
b)根據已知的業務量矩陣T，計算集合A中每一個元素所代表的迴路的衡量值Ci(i為正整數，且i＝1，…，I)，衡量值Ci的計算方法如下
其中，N表示網絡的節點總數，Lij表示第i個環路上第j段鏈路實際承載的業務量；Tsd表示從節點s到節點d的業務量；Lij的計算方法如下
業務按照何種方向沿迴路傳送完全根據路由策略決定，這裡使用最短路路由策略，由Dijkstra算法計算出OBS網絡中所有節點對之間的最短路，業務沿著最短路傳送到其目的節點；
c)清空集合A，選取最小的衡量值Ci值所對應的元素放入集合A中；
步驟9 集合A中元素所代表的迴路即為OBS的虛拓撲；
步驟10 算法結束；
所述的光電路交換OCS網絡虛拓撲的構建過程採用以下步驟
步驟1 計算OCS網絡的波長資源；由網絡中所有光纖鏈路的波長數量之和減去OBS網絡佔用的波長數量，得到OCS網絡的波長數量；
步驟2 根據步驟1的計算結果和已知的業務量矩陣T，利用HLDA算法建立OCS網絡的虛拓撲並生成相應的光路表；
所述的網絡節點對接入網業務流的處理過程採用以下步驟
步驟1 針對進入網絡節點的數據包查看由OCS虛拓撲構建過程產生的光路表，判斷是否存在以本地地址為起始節點、以數據包的目的地址為終節點的光路；如果存在，則轉步驟2，否則，將進入網絡節點的數據包送入溢出緩存並轉步驟3；
步驟2 判斷光路緩存是否由於存儲數據包的總量已經到達其容量上限而無法再存儲任何數據包；如果光路緩存不能再存儲任何數據包，則將該數據包送入溢出緩存並轉步驟3，否則，將數據包放入光路緩存並轉步驟5；
步驟3 將溢出緩存中的數據包利用混合時間和長度門限算法組裝成突發包，組裝完成後生成突發頭分組BHP，並轉步驟4；
步驟4 查找埠轉發表確定步驟3生成的突發頭分組BHP的轉發埠並且按照LAUC-VF算法在該埠的波長上進行突發包Burst的調度；如果調度成功，記錄波長的佔用時刻，發送突發頭分組BHP至控制信道並於Offset Time之後發送突發包Burst至數據信道；如果調度失敗，則銷毀突發頭分組BHP；
步驟5 判斷由步驟1找出的光路在當前時刻是否可以傳送該數據包？如是，則發送數據包；否則，數據包在光路緩存中繼續等待；
所述的網絡節點對核心網業務流的處理過程採用以下步驟
步驟1 查看突發頭分組BHP的目的地址；如果突發頭分組BHP的目的地址是本地地址，說明突發頭分組BHP的資源預約任務已經完成，只需銷毀突發頭分組BHP；如果突發頭分組BHP的目的地址不是本地地址，則從轉發表查找出該突發頭分組BHP的轉發埠；
步驟2 突發頭分組BHP在由步驟1找出的埠的所有波長上按照LAUC-VF算法調度其對應的突發包Burst；如果調度成功，則在記錄波長的佔用時間並修改突發頭分組BHP中的Offset Time之後發送突發頭分組BHP；如果調度失敗，則丟棄突發頭分組BHP。
全文摘要
本發明提供了一種基於環路的混合交換光網絡的構建方法。該方法有效的結合了OCS和OBS兩種交換方式，它是通過將網絡構造成一種環形拓撲結構的OBS網絡和OCS網絡的結合體，將網絡中的大部分業務經一跳到達目的節點，滿足大多數情況下網絡的通信需求，當網絡業務發生小範圍變化的時候，光路無法承載的業務將沿著環形拓撲採用OBS的交換方式繼續傳送。本發明的組網技術更簡單有效，並且由網絡動態變化引起的網絡性能的惡化程度小，網絡運行更加穩定，具有較高的通信能力，此外，網絡算法的實現難度低，具有較高的實用價值。
文檔編號H04Q11/00GK101370312SQ20071004977
公開日2009年2月18日 申請日期2007年8月17日 優先權日2007年8月17日
發明者晟 王, 媛 薛, 徐世中 申請人:電子科技大學