摘 要：網(wǎng)絡(luò)邏輯拓?fù)涞淖顑?yōu)化是光網(wǎng)絡(luò)的設(shè)計(jì)核心。針對分組業(yè)務(wù)的需要，要求光網(wǎng)絡(luò)能夠?qū)崟r(shí)、動態(tài)調(diào)整網(wǎng)絡(luò)的邏輯拓?fù)浣Y(jié)構(gòu)。對小規(guī)模的網(wǎng)絡(luò)進(jìn)行邏輯拓?fù)鋬?yōu)化，可以用混合整數(shù)線性規(guī)劃法（Mixed-Integer Linear Programming，MILP）解決。采用MILP算法對4節(jié)點(diǎn)網(wǎng)絡(luò)進(jìn)行邏輯拓?fù)鋬?yōu)化設(shè)計(jì)仿真，首先設(shè)定約束條件并建立模型，以擁塞率最小化為目標(biāo)函數(shù)做仿真實(shí)驗(yàn)，并對實(shí)驗(yàn)結(jié)果進(jìn)行分析。

關(guān)鍵詞：光網(wǎng)絡(luò)；邏輯拓?fù)洌粨砣?；MILP

中圖分類號：TN915.02 文獻(xiàn)標(biāo)識碼：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 引 言

隨著信息時(shí)代的到來，各種通信業(yè)務(wù)的出現(xiàn)，人們對于通信帶寬的要求越來越高。為了滿足這些要求，波分復(fù)用技術(shù)(WDM)引起了人們的廣泛重視。所謂波分復(fù)用技術(shù)，就是在一根光纖中利用不同的波長作為載波攜帶不同的數(shù)據(jù)流，每個數(shù)據(jù)流以Gbits的速率傳輸。采用波分復(fù)用技術(shù)可以大大增加光纖的傳輸能力。同時(shí)在光通信網(wǎng)中采用波長路由技術(shù)，他是以波長作為標(biāo)識進(jìn)行路由選擇。利用WDM技術(shù)和波長路由技術(shù)，可以在已知物理拓?fù)渲星度肴我獾倪壿嬐負(fù)?。?/p>

Internet業(yè)務(wù)的爆炸性增長使光網(wǎng)絡(luò)在業(yè)務(wù)提供方式上發(fā)生改變，從面向連接的、固定配置的電路業(yè)務(wù)方式轉(zhuǎn)向面向無連接的、動態(tài)提供的分組業(yè)務(wù)，對光網(wǎng)絡(luò)功能提出了新的、更高的要求。針對分組業(yè)務(wù)的面向無連接的特點(diǎn)，要求支持分組業(yè)務(wù)的光傳送網(wǎng)能夠?qū)崟r(shí)、動態(tài)地調(diào)整網(wǎng)絡(luò)的邏輯拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)資源的最佳利用，以適應(yīng)分組業(yè)務(wù)的自相似性、突發(fā)性等特點(diǎn)。設(shè)計(jì)核心是最優(yōu)化網(wǎng)絡(luò)邏輯拓?fù)?，改善網(wǎng)絡(luò)性能。

2 物理拓?fù)浜瓦壿嬐負(fù)洫?/p>

網(wǎng)絡(luò)的物理拓?fù)浼淳W(wǎng)絡(luò)節(jié)點(diǎn)的物理連接關(guān)系，在組成上，他是網(wǎng)絡(luò)節(jié)點(diǎn)與光纜鏈路的集合。物理拓?fù)渑c光纜線路的敷設(shè)路由直接相關(guān)，通常不能隨業(yè)務(wù)改變而改變。邏輯拓?fù)渲傅氖蔷W(wǎng)絡(luò)節(jié)點(diǎn)之間業(yè)務(wù)的分布情況，由一系列端到端的光通道構(gòu)成的拓?fù)浣Y(jié)構(gòu)，即在物理拓?fù)浠A(chǔ)上負(fù)責(zé)分層路由的光層邏輯結(jié)構(gòu)。他與物理拓?fù)溆芯o密關(guān)系，如圖1所示。邏輯拓?fù)淇梢杂绍浖刂票容^容易改變。

邏輯拓?fù)浜臀锢硗負(fù)涞膮^(qū)別有：

（1） 物理拓?fù)涫敲嫦蚬?jié)點(diǎn)的物理連接，邏輯拓?fù)涫敲嫦蚬?jié)點(diǎn)的邏輯連接；

（2） 物理拓?fù)鋱D的頂點(diǎn)是路由節(jié)點(diǎn)，邊是節(jié)點(diǎn)間的光纖鏈路。而邏輯拓?fù)鋱D的頂點(diǎn)是網(wǎng)絡(luò)的各個節(jié)點(diǎn)（指路由節(jié)點(diǎn)結(jié)合其對應(yīng)的接入節(jié)點(diǎn)）。邏輯拓?fù)鋱D的邊是節(jié)點(diǎn)間的光通道，通常是有向的。光通道是光網(wǎng)絡(luò)中由一條或多條鏈路構(gòu)成的端到端的透明信息通道。當(dāng)光網(wǎng)絡(luò)不具備波長轉(zhuǎn)換功能時(shí)，光通道必須滿足波長一致性條件（即一條通道上的波長處處不變）。若網(wǎng)絡(luò)具有波長轉(zhuǎn)換功能，此時(shí)的邏輯拓?fù)鋯栴}類似于ATM網(wǎng)絡(luò)中的虛通路分配問題；

（3） 物理拓?fù)渲泄?jié)點(diǎn)的物理度由與該節(jié)點(diǎn)有鏈路連接的節(jié)點(diǎn)數(shù)目決定，而邏輯拓?fù)渲泄?jié)點(diǎn)的邏輯度由該節(jié)點(diǎn)的光收發(fā)機(jī)數(shù)目決定；

（4） 物理拓?fù)湓O(shè)計(jì)是在保障網(wǎng)絡(luò)傳輸性能的前提下，根據(jù)節(jié)點(diǎn)位置和可用部件選擇建設(shè)費(fèi)用和綜合效益最適合的方案，邏輯拓?fù)湓O(shè)計(jì)是在物理拓?fù)浠A(chǔ)上考慮節(jié)點(diǎn)的業(yè)務(wù)分布情況，建立信息傳送性能達(dá)到最佳的方案。

光網(wǎng)絡(luò)的邏輯拓?fù)渑c波長分配方案相關(guān)，不同的波長分配方案可以形成不同的邏輯拓?fù)?。每根光纖上的最大波長數(shù)W，所以共享一條光纖鏈路的光通道數(shù)不得超過W。從源節(jié)點(diǎn)到宿節(jié)點(diǎn)可能由一條光通道直接連接，一條光通道所提供的路由是單跳路由。但是因?yàn)橐桓饫w上的最大波長數(shù)有限，且網(wǎng)絡(luò)不一定是全連通的，所以不可能所有節(jié)點(diǎn)對之間都有一條光通道連接，源宿節(jié)點(diǎn)對之間可能有多條光通道順序連接，這時(shí)稱為多跳路由?？梢娫谶壿嬐?fù)涞闹С窒拢纸M數(shù)據(jù)由波長一致的光通道傳至宿節(jié)點(diǎn)或盡可能遠(yuǎn)的地方，這里不考慮波長變換；如果一條光通道不能把分組數(shù)據(jù)傳輸至宿節(jié)點(diǎn)，則需要多跳路由傳輸，需要多條光通道。

3 邏輯拓?fù)涞膬?yōu)化

網(wǎng)絡(luò)的邏輯拓?fù)湓O(shè)計(jì)優(yōu)化問題是充分利用有限數(shù)量的光收發(fā)機(jī)和每根光纖的可用波長資源，確定最佳的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和光路徑選路方案，使網(wǎng)絡(luò)的性能指標(biāo)得到優(yōu)化。在節(jié)點(diǎn)的收發(fā)機(jī)和波長數(shù)目受到限制的前提條件下，這里感興趣的問題是怎樣最小化端到端的分組延遲，或考慮盡可能地提高網(wǎng)絡(luò)的吞吐量，以滿足業(yè)務(wù)增長的需要。因此邏輯拓?fù)涞膬?yōu)化設(shè)計(jì)有1個或2個可能的目標(biāo)函數(shù)：

（1） 對給定的業(yè)務(wù)矩陣最小化網(wǎng)絡(luò)范圍的平均分組延遲，即目標(biāo)函數(shù)是最小化平均分組延遲；

（2） 最大化業(yè)務(wù)規(guī)模的擴(kuò)展因素，即最小化網(wǎng)絡(luò)擁塞，即min fmax=max fij，ij ∈V，其中V是給定網(wǎng)絡(luò)的所有節(jié)點(diǎn)的集合。擁塞控制與業(yè)務(wù)的路由選擇緊密相關(guān)，不佳的選徑策略是導(dǎo)致網(wǎng)絡(luò)擁塞增加的主要原因。最小化擁塞指標(biāo)可以提高網(wǎng)絡(luò)的吞吐能力，從而更好地適應(yīng)未來業(yè)務(wù)增長的需要。

邏輯拓?fù)涞膬?yōu)化設(shè)計(jì)需要從網(wǎng)絡(luò)的所有邏輯拓?fù)鋵?shí)現(xiàn)方案中選擇使分組業(yè)務(wù)傳送性能最佳的方案，決定了這類問題復(fù)雜的組合優(yōu)化過程。對于小規(guī)模的網(wǎng)絡(luò)，可以用混合整數(shù)線性規(guī)劃法（Mixed-Integer Linear Programming，MILP）解決；在大規(guī)模網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)中，通常采用啟發(fā)式算法。本文采用MILP算法對4節(jié)點(diǎn)網(wǎng)絡(luò)進(jìn)行邏輯拓?fù)鋬?yōu)化設(shè)計(jì)仿真，并對仿真實(shí)驗(yàn)結(jié)果進(jìn)行分析。

4 MILP模型描述

4.1 已知條件

(1) 光纖網(wǎng)絡(luò)的網(wǎng)絡(luò)物理拓?fù)溆脽o向圖Gp=(V，Ep)表示；V表示頂點(diǎn)集合；Ep代表邊集，“無向”的含義是物理拓?fù)渲忻織l鏈路是雙向的，鏈路可以帶有表征距離和延時(shí)的權(quán)重。

(2) 每根光纖上的最大波長數(shù)W。

(3) 業(yè)務(wù)需求分布用表用一個N×N的矩陣描述，這里N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)；第(i，j)項(xiàng)矩陣元素代表從節(jié)點(diǎn)i到j(luò)的平均業(yè)務(wù)流量(注意業(yè)務(wù)流可以是不對稱的)。為簡便起見，實(shí)驗(yàn)中采用的業(yè)務(wù)流是均勻分布U(0，1)。

(4) 網(wǎng)絡(luò)節(jié)點(diǎn)的收發(fā)機(jī)數(shù)目，決定網(wǎng)絡(luò)的邏輯度。

仿真實(shí)驗(yàn)中用到的參數(shù)：

N：物理網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)；

W：每根光纖的最大波長數(shù)；

ts，d：節(jié)點(diǎn)s到節(jié)點(diǎn)d的平均流量；

hpi，j：節(jié)點(diǎn)i到節(jié)點(diǎn)j的光通道的最大物理跳數(shù)；

hi，j：邏輯拓?fù)渲泄?jié)點(diǎn)i到節(jié)點(diǎn)j的最大邏輯跳數(shù)；

fi，j：節(jié)點(diǎn)i到節(jié)點(diǎn)j的光通道上的總流量；

f(s，d)i，j ：起點(diǎn)終點(diǎn)分別為節(jié)點(diǎn)i，j光通道上源宿節(jié)點(diǎn)對s，d間的流量；

pij：光通道標(biāo)識符，若為1，表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j存在一條光通道；否則為0。

4.2 約束條件

5 仿真結(jié)果及分析

由于環(huán)網(wǎng)是目前城域網(wǎng)和局域網(wǎng)所采用的主要拓?fù)浣Y(jié)構(gòu)，他是光網(wǎng)絡(luò)實(shí)際應(yīng)用時(shí)最先采用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，因此在實(shí)驗(yàn)中設(shè)計(jì)4節(jié)點(diǎn)簡單環(huán)形網(wǎng)的邏輯拓?fù)?。傳輸模式是均勻分布U(0，1)，無波長轉(zhuǎn)換器，目標(biāo)函數(shù)是使擁塞率最小，求解方程組，使得擁塞率fmax最小化。本文所采用的算法忽略時(shí)延約束，只考慮邏輯度約束、流量約束、波長約束、跳轉(zhuǎn)數(shù)約束，使約束條件簡化。仿真數(shù)值結(jié)果如表1所示。求得的邏輯拓?fù)淙鐖D2所示。

從仿真結(jié)果中可以看出當(dāng)每個網(wǎng)絡(luò)節(jié)點(diǎn)收發(fā)器數(shù)目由1個增加到2個時(shí)，擁塞率顯著減小，由3.333 5減小到1.199。而通常情況下，節(jié)點(diǎn)的發(fā)射器數(shù)目稱為節(jié)點(diǎn)的邏輯輸出度，節(jié)點(diǎn)的接受器數(shù)目稱為節(jié)點(diǎn)的邏輯輸入度，當(dāng)節(jié)點(diǎn)發(fā)射器和節(jié)點(diǎn)接收器數(shù)目相等時(shí)，稱為邏輯度。可見增加網(wǎng)絡(luò)的邏輯度可以明顯地緩解的網(wǎng)絡(luò)擁塞現(xiàn)象。同時(shí)，當(dāng)邏輯度增加為2時(shí)，網(wǎng)絡(luò)的邏輯拓?fù)渥優(yōu)殡p環(huán)形結(jié)構(gòu)，光通道數(shù)增加為8。

當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)收發(fā)器數(shù)目（即節(jié)點(diǎn)邏輯度）和最大跳轉(zhuǎn)次數(shù)一定時(shí)，增加最大波長數(shù)，從表1中可以看出，網(wǎng)絡(luò)擁塞率進(jìn)一步減小，如表第1行和第2行擁塞率由3.333 5減小到2.637 7。同樣，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目和最大波長數(shù)一定時(shí)，增加最大跳轉(zhuǎn)次數(shù)，網(wǎng)絡(luò)擁塞率也減小，如表第1行和第3行擁塞率由3.333 5減小到2.793 1。

從仿真結(jié)果還可以看出網(wǎng)絡(luò)節(jié)點(diǎn)的邏輯度、最大波長數(shù)、最大跳轉(zhuǎn)次數(shù)3個參量，對擁塞率的影響程度由強(qiáng)到弱依次為節(jié)點(diǎn)邏輯度、最大波長數(shù)、最大跳轉(zhuǎn)次數(shù)。但是網(wǎng)絡(luò)節(jié)點(diǎn)邏輯度增加需要增加網(wǎng)絡(luò)節(jié)點(diǎn)收發(fā)器數(shù)目，增加網(wǎng)絡(luò)成本，在實(shí)際的網(wǎng)絡(luò)設(shè)計(jì)中網(wǎng)絡(luò)成本是不可忽視的主要因素。實(shí)際應(yīng)用中需要綜合考慮各方面因素，選擇性價(jià)比高的方案。

6 結(jié) 語

文中利用MILP模型算法建立邏輯拓?fù)?，簡化約束條件，不考慮延時(shí)條件，考慮最優(yōu)路由優(yōu)先的情況下，以最小擁塞率為目標(biāo)設(shè)計(jì)邏輯拓?fù)?，?節(jié)點(diǎn)的簡單環(huán)形網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)。

試驗(yàn)結(jié)果表明MILP模型算法可以很好地得到邏輯拓?fù)?，并且可以看出邏輯度、最大波長數(shù)和最大跳轉(zhuǎn)次數(shù)對擁塞率的影響。從MILP模型可以看出方程組變量個數(shù)隨著網(wǎng)絡(luò)節(jié)點(diǎn)個數(shù)增加而迅速增加，即這種方法計(jì)算的復(fù)雜性隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大而增加，因此這種方法只適用于小規(guī)模的網(wǎng)絡(luò)。

參 考 文 獻(xiàn)

［1］龔倩，徐榮，張民，等.光網(wǎng)絡(luò)的組網(wǎng)與優(yōu)化設(shè)計(jì)［M］.北京：北京郵電大學(xué)出版社，2002.

［2］楊淑雯.全光光纖通信網(wǎng)［M］.北京：科學(xué)出版社，2004.

［3］Liu Fengqing，Zeng Qingji，Zhu Xu，et al.Virtual Topology Reconfiguration in WDM Optical Networks［J］.光子學(xué)報(bào):英文版，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］張杰，顧畹儀，李國瑞，等.光傳送網(wǎng)的最優(yōu)虛拓?fù)湓O(shè)計(jì)原理［J］.現(xiàn)代有線傳輸，1999，12(4):29-32.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。