基于ＭＩＬＰ模型的光網絡邏輯拓撲優化算法
2008-04-12 00:00:00魏政霞鞏稼民高新宇
現代電子技術 2008年2期
摘 要：網絡邏輯拓撲的最優化是光網絡的設計核心。針對分組業務的需要，要求光網絡能夠實時、動態調整網絡的邏輯拓撲結構。對小規模的網絡進行邏輯拓撲優化，可以用混合整數線性規劃法（Mixed-Integer Linear Programming，MILP）解決。采用MILP算法對4節點網絡進行邏輯拓撲優化設計仿真，首先設定約束條件并建立模型，以擁塞率最小化為目標函數做仿真實驗，并對實驗結果進行分析。
關鍵詞：光網絡；邏輯拓撲；擁塞率；MILP
中圖分類號：TN915.02 文獻標識碼：B 文章編號：1004-373X(2008)02-134-03
An Algorithm of Logical Topology Design in Optical Network Based on MILP
WEI Zhengxia，GONG Jiamin，GAO Xinyu
(Xi′an University of Post and Telecommunications，Xi′an，710061，China)
Abstract：The logical topology of network optimization is the core of optical network design.To meeting the requirement of packet service，the optical network can adjust logical topology dynamically and in a real-time.MILP(Mixed Integer Linear Programming ) is a solution for logical topology optimization of the small-scale network.In this paper，an simulation design for logical topology optimization of four nodes network.A model has been established according to the constraint conditions，the simulation is based on the objective function which is minimizing the congestion rate.Then the experimental result has beenanalyzed.
Keywords：optical network;logical topology;congestion;MILP
1 引 言
隨著信息時代的到來，各種通信業務的出現，人們對于通信帶寬的要求越來越高。為了滿足這些要求，波分復用技術(WDM)引起了人們的廣泛重視。所謂波分復用技術，就是在一根光纖中利用不同的波長作為載波攜帶不同的數據流，每個數據流以Gbits的速率傳輸。采用波分復用技術可以大大增加光纖的傳輸能力。同時在光通信網中采用波長路由技術，他是以波長作為標識進行路由選擇。利用WDM技術和波長路由技術，可以在已知物理拓撲中嵌入任意的邏輯拓撲。
Internet業務的爆炸性增長使光網絡在業務提供方式上發生改變，從面向連接的、固定配置的電路業務方式轉向面向無連接的、動態提供的分組業務，對光網絡功能提出了新的、更高的要求。針對分組業務的面向無連接的特點，要求支持分組業務的光傳送網能夠實時、動態地調整網絡的邏輯拓撲結構，實現資源的最佳利用，以適應分組業務的自相似性、突發性等特點。設計核心是最優化網絡邏輯拓撲，改善網絡性能。
2 物理拓撲和邏輯拓撲
網絡的物理拓撲即網絡節點的物理連接關系，在組成上，他是網絡節點與光纜鏈路的集合。物理拓撲與光纜線路的敷設路由直接相關，通常不能隨業務改變而改變。邏輯拓撲指的是網絡節點之間業務的分布情況，由一系列端到端的光通道構成的拓撲結構，即在物理拓撲基礎上負責分層路由的光層邏輯結構。他與物理拓撲有緊密關系，如圖1所示。邏輯拓撲可以由軟件控制比較容易改變。
邏輯拓撲和物理拓撲的區別有：
（1） 物理拓撲是面向節點的物理連接，邏輯拓撲是面向節點的邏輯連接；
（2） 物理拓撲圖的頂點是路由節點，邊是節點間的光纖鏈路。而邏輯拓撲圖的頂點是網絡的各個節點（指路由節點結合其對應的接入節點）。邏輯拓撲圖的邊是節點間的光通道，通常是有向的。光通道是光網絡中由一條或多條鏈路構成的端到端的透明信息通道。當光網絡不具備波長轉換功能時，光通道必須滿足波長一致性條件（即一條通道上的波長處處不變）。若網絡具有波長轉換功能，此時的邏輯拓撲問題類似于ATM網絡中的虛通路分配問題；
（3） 物理拓撲中節點的物理度由與該節點有鏈路連接的節點數目決定，而邏輯拓撲中節點的邏輯度由該節點的光收發機數目決定；
（4） 物理拓撲設計是在保障網絡傳輸性能的前提下，根據節點位置和可用部件選擇建設費用和綜合效益最適合的方案，邏輯拓撲設計是在物理拓撲基礎上考慮節點的業務分布情況，建立信息傳送性能達到最佳的方案。
光網絡的邏輯拓撲與波長分配方案相關，不同的波長分配方案可以形成不同的邏輯拓撲。每根光纖上的最大波長數W，所以共享一條光纖鏈路的光通道數不得超過W。從源節點到宿節點可能由一條光通道直接連接，一條光通道所提供的路由是單跳路由。但是因為一根光纖上的最大波長數有限，且網絡不一定是全連通的，所以不可能所有節點對之間都有一條光通道連接，源宿節點對之間可能有多條光通道順序連接，這時稱為多跳路由。可見在邏輯拓撲的支持下，分組數據由波長一致的光通道傳至宿節點或盡可能遠的地方，這里不考慮波長變換；如果一條光通道不能把分組數據傳輸至宿節點，則需要多跳路由傳輸，需要多條光通道。
3 邏輯拓撲的優化
網絡的邏輯拓撲設計優化問題是充分利用有限數量的光收發機和每根光纖的可用波長資源，確定最佳的網絡拓撲結構和光路徑選路方案，使網絡的性能指標得到優化。在節點的收發機和波長數目受到限制的前提條件下，這里感興趣的問題是怎樣最小化端到端的分組延遲，或考慮盡可能地提高網絡的吞吐量，以滿足業務增長的需要。因此邏輯拓撲的優化設計有1個或2個可能的目標函數：
（1） 對給定的業務矩陣最小化網絡范圍的平均分組延遲，即目標函數是最小化平均分組延遲；
（2） 最大化業務規模的擴展因素，即最小化網絡擁塞，即min fmax=max fij，ij ∈V，其中V是給定網絡的所有節點的集合。擁塞控制與業務的路由選擇緊密相關，不佳的選徑策略是導致網絡擁塞增加的主要原因。最小化擁塞指標可以提高網絡的吞吐能力，從而更好地適應未來業務增長的需要。
邏輯拓撲的優化設計需要從網絡的所有邏輯拓撲實現方案中選擇使分組業務傳送性能最佳的方案，決定了這類問題復雜的組合優化過程。對于小規模的網絡，可以用混合整數線性規劃法（Mixed-Integer Linear Programming，MILP）解決；在大規模網絡的優化設計中，通常采用啟發式算法。本文采用MILP算法對4節點網絡進行邏輯拓撲優化設計仿真，并對仿真實驗結果進行分析。
4 MILP模型描述
4.1 已知條件
(1) 光纖網絡的網絡物理拓撲用無向圖Gp=(V，Ep)表示；V表示頂點集合；Ep代表邊集，“無向”的含義是物理拓撲中每條鏈路是雙向的，鏈路可以帶有表征距離和延時的權重。
(2) 每根光纖上的最大波長數W。
(3) 業務需求分布用表用一個N×N的矩陣描述，這里N為網絡節點總數；第(i，j)項矩陣元素代表從節點i到j的平均業務流量(注意業務流可以是不對稱的)。為簡便起見，實驗中采用的業務流是均勻分布U(0，1)。
(4) 網絡節點的收發機數目，決定網絡的邏輯度。
仿真實驗中用到的參數：
N：物理網絡的節點數；
W：每根光纖的最大波長數；
ts，d：節點s到節點d的平均流量；
hpi，j：節點i到節點j的光通道的最大物理跳數；
hi，j：邏輯拓撲中節點i到節點j的最大邏輯跳數；
fi，j：節點i到節點j的光通道上的總流量；
f(s，d)i，j ：起點終點分別為節點i，j光通道上源宿節點對s，d間的流量；
pij：光通道標識符，若為1，表示從節點i到節點j存在一條光通道；否則為0。
4.2 約束條件
5 仿真結果及分析
由于環網是目前城域網和局域網所采用的主要拓撲結構，他是光網絡實際應用時最先采用的網絡拓撲結構，因此在實驗中設計4節點簡單環形網的邏輯拓撲。傳輸模式是均勻分布U(0，1)，無波長轉換器，目標函數是使擁塞率最小，求解方程組，使得擁塞率fmax最小化。本文所采用的算法忽略時延約束，只考慮邏輯度約束、流量約束、波長約束、跳轉數約束，使約束條件簡化。仿真數值結果如表1所示。求得的邏輯拓撲如圖2所示。
從仿真結果中可以看出當每個網絡節點收發器數目由1個增加到2個時，擁塞率顯著減小，由3.333 5減小到1.199。而通常情況下，節點的發射器數目稱為節點的邏輯輸出度，節點的接受器數目稱為節點的邏輯輸入度，當節點發射器和節點接收器數目相等時，稱為邏輯度。可見增加網絡的邏輯度可以明顯地緩解的網絡擁塞現象。同時，當邏輯度增加為2時，網絡的邏輯拓撲變為雙環形結構，光通道數增加為8。
當網絡節點收發器數目（即節點邏輯度）和最大跳轉次數一定時，增加最大波長數，從表1中可以看出，網絡擁塞率進一步減小，如表第1行和第2行擁塞率由3.333 5減小到2.637 7。同樣，當網絡節點數目和最大波長數一定時，增加最大跳轉次數，網絡擁塞率也減小，如表第1行和第3行擁塞率由3.333 5減小到2.793 1。
從仿真結果還可以看出網絡節點的邏輯度、最大波長數、最大跳轉次數3個參量，對擁塞率的影響程度由強到弱依次為節點邏輯度、最大波長數、最大跳轉次數。但是網絡節點邏輯度增加需要增加網絡節點收發器數目，增加網絡成本，在實際的網絡設計中網絡成本是不可忽視的主要因素。實際應用中需要綜合考慮各方面因素，選擇性價比高的方案。
6 結 語
文中利用MILP模型算法建立邏輯拓撲，簡化約束條件，不考慮延時條件，考慮最優路由優先的情況下，以最小擁塞率為目標設計邏輯拓撲，對4節點的簡單環形網絡進行仿真實驗。
試驗結果表明MILP模型算法可以很好地得到邏輯拓撲，并且可以看出邏輯度、最大波長數和最大跳轉次數對擁塞率的影響。從MILP模型可以看出方程組變量個數隨著網絡節點個數增加而迅速增加，即這種方法計算的復雜性隨著網絡規模的擴大而增加，因此這種方法只適用于小規模的網絡。
參 考 文 獻
［1］龔倩，徐榮，張民，等.光網絡的組網與優化設計［M］.北京：北京郵電大學出版社，2002.
［2］楊淑雯.全光光纖通信網［M］.北京：科學出版社，2004.
［3］Liu Fengqing，Zeng Qingji，Zhu Xu，et al.Virtual Topology Reconfiguration in WDM Optical Networks［J］.光子學報:英文版，2003，32(10):1 116-1 180.
［4］Rajiv Ramaswami，Kumar N Sivarajan.Design of Logical Topologies for Wavelength-Routed All-Optical Networks［A］.Proceeding of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies，1995:1 316-1 325.
［5］張杰，顧畹儀，李國瑞，等.光傳送網的最優虛拓撲設計原理［J］.現代有線傳輸，1999，12(4):29-32.
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
