基于時(shí)延約束的廣域網(wǎng)絡(luò) 拓?fù)湓O(shè)計(jì)和容量規(guī)劃

徐曉青，唐宏，阮科，武娟，劉曉軍

（中國(guó)電信股份有限公司研究院，廣東 廣州 510630）

1 引言

如何讓IP網(wǎng)絡(luò)的拓?fù)湓O(shè)計(jì)和容量規(guī)劃高效滿(mǎn)足互聯(lián)網(wǎng)業(yè)務(wù)高速增長(zhǎng)需求，是基礎(chǔ)電信運(yùn)營(yíng)商基礎(chǔ)網(wǎng)絡(luò)建設(shè)和運(yùn)營(yíng)部門(mén)面臨的重大挑戰(zhàn)，包括以下3方面。

·架構(gòu)設(shè)計(jì)變革后的評(píng)估和優(yōu)化困難：經(jīng)典的分層匯聚式網(wǎng)絡(luò)架構(gòu)，面臨核心匯聚節(jié)點(diǎn)壓力過(guò)大、非核心省份間時(shí)延性能差等問(wèn)題，無(wú)法持續(xù)；而轉(zhuǎn)向全面扁平化網(wǎng)絡(luò)后，則缺少精確的量化評(píng)估手段以實(shí)現(xiàn)拓?fù)涞淖顑?yōu)化設(shè)計(jì)和最優(yōu)化變更。

·路由優(yōu)化效率較低：運(yùn)營(yíng)商IP廣域網(wǎng)的路由設(shè)計(jì)一般依賴(lài)于網(wǎng)絡(luò)設(shè)備的分布式路由協(xié)議，無(wú)法滿(mǎn)足面向業(yè)務(wù)/客戶(hù)的、定制化的復(fù)雜約束條件，也難以保障網(wǎng)絡(luò)利用率的均衡，導(dǎo)致IP骨干網(wǎng)絡(luò)利用率一般只能在50%上下，網(wǎng)絡(luò)建設(shè)成本高。

·多維協(xié)同困難：IP廣域網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計(jì)與成本約束與底層傳輸網(wǎng)絡(luò)關(guān)系巨大，僅依賴(lài)IP網(wǎng)絡(luò)層的約束無(wú)法實(shí)現(xiàn)整體性能和成本的最優(yōu)。

具體到日常的網(wǎng)絡(luò)容量規(guī)劃中，存在多種需求場(chǎng)景，包括但不限于以下幾種。

·快速擴(kuò)容場(chǎng)景：主要滿(mǎn)足突發(fā)性業(yè)務(wù)需求，規(guī)模一般較?。粚?shí)際操作時(shí)，約束因素相對(duì)較少，可快速滿(mǎn)足業(yè)務(wù)需求。

·常規(guī)擴(kuò)容場(chǎng)景：運(yùn)營(yíng)商根據(jù)每年的業(yè)務(wù)發(fā)展預(yù)期，按需對(duì)現(xiàn)有網(wǎng)絡(luò)資源進(jìn)行增加或調(diào)整。

·多約束擴(kuò)容場(chǎng)景：在擴(kuò)容過(guò)程中，會(huì)面臨很多實(shí)際的約束，比如投資規(guī)模限制、是否允許優(yōu)化拓?fù)?、是否有特定業(yè)務(wù)時(shí)延要求等。

對(duì)運(yùn)營(yíng)商的網(wǎng)絡(luò)規(guī)劃，通常需要考慮時(shí)延、帶寬、鏈路利用率和投資成本等方面。隨著低時(shí)延網(wǎng)絡(luò)應(yīng)用業(yè)務(wù)的涌現(xiàn)，例如游戲、直播、高清會(huì)議、電子交易等，時(shí)延成為網(wǎng)絡(luò)規(guī)劃任務(wù)中的一個(gè)重要因素。此外，成本是必須考慮的一個(gè)重要方面，需要在保障業(yè)務(wù)需求的同時(shí)，盡可能地降低網(wǎng)絡(luò)建設(shè)成本。本文從時(shí)延/成本優(yōu)化方面改進(jìn)傳統(tǒng)的IP骨干網(wǎng)拓?fù)湓O(shè)計(jì)與容量規(guī)劃，推動(dòng)實(shí)現(xiàn)廣域IP網(wǎng)絡(luò)設(shè)計(jì)過(guò)程的智能化與自動(dòng)化，以期解決IP網(wǎng)絡(luò)演進(jìn)中面臨的部分挑戰(zhàn)。本文對(duì)容量規(guī)劃問(wèn)題進(jìn)行數(shù)學(xué)建模，主要考慮傳輸時(shí)延的約束，分為拓?fù)涔潭ê屯負(fù)淇勺兙W(wǎng)絡(luò)擴(kuò)容兩類(lèi)問(wèn)題，可以覆蓋部分上述業(yè)務(wù)場(chǎng)景。

在一些網(wǎng)絡(luò)規(guī)劃文獻(xiàn)中，時(shí)延的定義比較復(fù)雜，除了鏈路上的流量，還與鏈路所剩容量或者負(fù)載相關(guān)[1-3]。在骨干網(wǎng)網(wǎng)絡(luò)規(guī)劃中，時(shí)延影響最大的是傳輸時(shí)延，占據(jù)光網(wǎng)絡(luò)電路時(shí)延的90%以上[4]。所以從運(yùn)營(yíng)商網(wǎng)絡(luò)規(guī)劃的角度，用路徑長(zhǎng)度來(lái)表征時(shí)延是一種比較合理和直觀的方式，在本文中只考慮路徑長(zhǎng)度對(duì)應(yīng)的傳輸時(shí)延。在降低網(wǎng)絡(luò)時(shí)延的研究中，參考文獻(xiàn)[5-6]提出通過(guò)升級(jí)節(jié)點(diǎn)或者鏈路方法，認(rèn)為升級(jí)后的節(jié)點(diǎn)或鏈路會(huì)有一定比例的時(shí)延下降，從而降低整個(gè)網(wǎng)絡(luò)的時(shí)延。但是升級(jí)前后各個(gè)節(jié)點(diǎn)時(shí)延下降比例難以比較合理地確定。參考文獻(xiàn)[7]提出了在候選鏈路集中添加k個(gè)鏈路來(lái)降低所有需求對(duì)的平均最短路徑，但這樣只考慮了新增鏈路前后的所有需求的路徑絕對(duì)長(zhǎng)度的變化，沒(méi)有考慮具體鏈路成本的不同。

通常，涉及目標(biāo)函數(shù)為線性的優(yōu)化問(wèn)題，可以利用線性規(guī)劃求解。傳統(tǒng)上，大量的網(wǎng)絡(luò)規(guī)劃也可以建模成線性規(guī)劃問(wèn)題從而求得最優(yōu)解。一般做法是提前對(duì)需求給定候選路徑，每一個(gè)路徑對(duì)應(yīng)一個(gè)待分配流量。但涉及拓?fù)涓淖儐?wèn)題時(shí)，候選路徑是動(dòng)態(tài)變化的，不應(yīng)該提前給定。而如果不提前對(duì)需求先給定候選路徑，隨著拓?fù)涞脑龃?，潛在的路徑?shù)迅速增加，給求解帶來(lái)困難[1]。另外，一旦涉及變量值只能涉及離散值，則線性規(guī)劃變成整數(shù)規(guī)劃，隨著問(wèn)題規(guī)模的增大，求解難度迅速增加，大多是NP-hard問(wèn)題，只能采用一些啟發(fā)式算法來(lái)進(jìn)行求解。本文針對(duì)運(yùn)營(yíng)商網(wǎng)絡(luò)規(guī)劃的需求和特點(diǎn)，從實(shí)際業(yè)務(wù)角度出發(fā)，定義了帶權(quán)重的傳播時(shí)延（流量×路徑長(zhǎng)度）和全局歸一化時(shí)延（原始拓?fù)湎赂鱾€(gè)需求的最短路徑長(zhǎng)度對(duì)應(yīng)時(shí)延1），針對(duì)拓?fù)洳蛔兒屯負(fù)涓淖兊那樾危饕獞?yīng)用了線性規(guī)劃和貪婪算法來(lái)建模和求解。

相比傳統(tǒng)的做法，在應(yīng)用線性規(guī)劃求解最低時(shí)延時(shí)，本文不但考慮傳輸時(shí)延（路徑長(zhǎng)度），還加入需求量的影響，最優(yōu)化需求量與路徑長(zhǎng)度的乘積。在應(yīng)用貪婪算法尋找新增連接時(shí)，考慮了全局歸一化時(shí)延的影響。首先研究了相對(duì)簡(jiǎn)單的拓?fù)涔潭ㄇ闆r下的最低時(shí)延和滿(mǎn)足時(shí)延約束的最低成本的場(chǎng)景。在此基礎(chǔ)上，考慮改變網(wǎng)絡(luò)拓?fù)洌略鼍W(wǎng)絡(luò)連接降低整體時(shí)延；進(jìn)一步研究滿(mǎn)足時(shí)延約束下成本最低新增網(wǎng)絡(luò)連接，即最低成本的新增局向問(wèn)題。

2 拓?fù)洳蛔兊木W(wǎng)絡(luò)擴(kuò)容

將網(wǎng)絡(luò)表示為一個(gè)無(wú)向圖G(V,E)，V表示網(wǎng)絡(luò)節(jié)點(diǎn)，E表示節(jié)點(diǎn)間的鏈路。采用路徑建模（path formulation）的方法來(lái)研究網(wǎng)絡(luò)規(guī)劃問(wèn)題，即對(duì)各個(gè)需求，提前確定候選路徑，每個(gè)需求的各條路徑對(duì)應(yīng)的流為一個(gè)變量[1]。下面研究目標(biāo)函數(shù)為最低時(shí)延及最低時(shí)延下的最低成本情形，同時(shí)滿(mǎn)足各個(gè)需求的帶寬要求。其中，這里的“最低”是指給定候選路徑下所能達(dá)到的最低。

2.1 求解最低時(shí)延

本文中只考慮路徑長(zhǎng)度帶來(lái)的時(shí)延。同時(shí)，從網(wǎng)絡(luò)運(yùn)營(yíng)的角度，更為合理的是考慮需求值的權(quán)重，對(duì)節(jié)點(diǎn)間最短路徑進(jìn)行加權(quán)，即對(duì)時(shí)延進(jìn)行加權(quán)，用需求的帶寬×需求點(diǎn)之間最短路徑長(zhǎng)度來(lái)表示。如圖1（a）所示，從A到B的需求是1 Gbit/s，最短路徑長(zhǎng)度是1 km，從A到C的需求是99 Gbit/s，最短路徑長(zhǎng)度是100 km。圖1（b）中，A到B的需求是99 Gbit/s，A到C的需求是1 Gbit/s，路徑長(zhǎng)度和圖1（a）相同。雖然從A點(diǎn)出來(lái)的流量都是100 Gbit/s，但從網(wǎng)絡(luò)運(yùn)營(yíng)的角度，圖1（b）的總體時(shí)延要低于圖1（a）的，因?yàn)閳D1（b）的大部分流量都用了比較短的路徑，而為圖1（a）的大部分流量都用了比較長(zhǎng)的路徑。

圖1 不同需求的時(shí)延比較

本節(jié)研究的最低時(shí)延是總體的最低時(shí)延，即讓盡量多的流量通過(guò)比較短的路徑。所以不但需求對(duì)應(yīng)的節(jié)點(diǎn)間路徑長(zhǎng)度與時(shí)延有關(guān)，需求的值也有影響，所以當(dāng)考慮最低時(shí)延時(shí)，最小化的是∑需求量×路徑長(zhǎng)度，而不是最小化需求中的最大時(shí)延。

下面考慮目標(biāo)函數(shù)為總體時(shí)延最低的網(wǎng)絡(luò)擴(kuò)容問(wèn)題：假設(shè)有D個(gè)需求，對(duì)每個(gè)需求d先算出P條（例如P=4）最短路徑為候選路徑，每條路徑長(zhǎng)度為ldp，每條路徑分配帶寬為xdp，下標(biāo)d表示第d個(gè)需求，hd表示該需求的值，p表示這個(gè)需求P條候選路徑中的第p條路徑。鏈路原有容量ce，鏈路新增容量變量ye，e表示第e條鏈路，共有E條鏈路。在網(wǎng)絡(luò)規(guī)劃中，為了考慮現(xiàn)網(wǎng)需求存在的突發(fā)性和波動(dòng)性，往往要求鏈路的利用率低于一定水平，這里設(shè)置為80%。最小化總體時(shí)延，該問(wèn)題的線性規(guī)劃建模如下：

當(dāng)xdp對(duì)應(yīng)的路徑包含e鏈路時(shí)，δedp=1，其余時(shí)候?yàn)?。

式（1）是目標(biāo)函數(shù)，是加權(quán)的需求和路徑長(zhǎng)度的乘積，即對(duì)應(yīng)加權(quán)的時(shí)延。式（2）表示每個(gè)需求P條路徑的流量之和等于需求值，需求得到滿(mǎn)足。式（3）表示對(duì)每段鏈路，其承載的各個(gè)需求的流不超過(guò)其新增的容量和固有容量之和的80%。如果對(duì)某些鏈路容量有限制，則可以設(shè)置相應(yīng)的鏈路容量變量ye處在某些范圍。

這樣可以求解出固定拓?fù)淝樾蜗碌臐M(mǎn)足需求并且時(shí)延最低的擴(kuò)容問(wèn)題的解，即各個(gè)需求的路徑及帶寬分配。其實(shí)，最低時(shí)延問(wèn)題，本質(zhì)上是對(duì)各個(gè)需求從候選路徑表中挑選出一條最短路徑（關(guān)于距離），然后讓該需求要求的帶寬都由該路徑承擔(dān)。這樣，可以計(jì)算出該條路徑上每段鏈路需要分擔(dān)的帶寬，把所有需求在該段鏈路的帶寬相加，也就確定了該段鏈路的容量。這稱(chēng)為最短路徑分配的方法[1]，可以不用求解上述的線性規(guī)劃問(wèn)題。但是，這種方法比較適用于鏈路容量從0開(kāi)始設(shè)計(jì)擴(kuò)容問(wèn)題。真實(shí)的網(wǎng)絡(luò)規(guī)劃中，鏈路中已經(jīng)有一些容量ce，更適合用上述的線性規(guī)劃求解。原因在于，最短路徑分配的方法只用到一條路徑，而上述線性規(guī)劃中采用多條路徑，還有鏈路利用率的約束，假設(shè)一個(gè)需求存在兩條同樣長(zhǎng)度路徑，采用上述線性規(guī)劃，可能會(huì)用到兩條路徑，可以充分利用現(xiàn)有的鏈路容量，提高鏈路的利用率，不必新增太多容量，降低成本。如圖2所示，所有鏈路的長(zhǎng)度都是1 km，固有容量1 Gbit/s。從A到D有路徑A-B-D和路徑A-C-D相等。如果A-D的需求為4 Gbit/s，如果候選路徑取一個(gè)路徑A-B-D，則該路徑需要擴(kuò)容3 Gbit/s，而該路徑有兩段鏈路總共需要擴(kuò)容3×2 = 6 Gbit/s。而如果選取兩個(gè)路徑，每個(gè)路徑只需擴(kuò)容1 Gbit/s，兩個(gè)路徑共有4段鏈路，需擴(kuò)容1×4 = 4 Gbit/s，相比單路徑情形減少了2 Gbit/s擴(kuò)容，降低了成本。

圖2 一個(gè)需求可能存在多個(gè)相等路徑

2.2 求解最低時(shí)延下的最低成本

由于本文采用了路徑建模，路徑中可能存在兩條或多條路徑時(shí)延相同，但成本不一樣，因此可能在第2.1節(jié)中最低時(shí)延擴(kuò)容問(wèn)題的基礎(chǔ)上進(jìn)一步求出最低成本。同理，可以在最低成本的基礎(chǔ)上，求解最低時(shí)延。在第2.1節(jié)中求解出最低時(shí)延，將其作為一個(gè)約束條件，將目標(biāo)函數(shù)改成鏈路成本，就可以求解出最低時(shí)延下的最低成本，ρe為鏈路e的成本系數(shù)。線性規(guī)劃建模如下：

當(dāng)xdp對(duì)應(yīng)的路徑包含e鏈路時(shí)，δedp=1，其余時(shí)候?yàn)?。

如果把式（5）最低時(shí)延約束修改成其他時(shí)延值約束，則該線性規(guī)劃是更普遍形式的時(shí)延約束下的最低成本問(wèn)題。當(dāng)然，該線性規(guī)劃求解結(jié)果可能和第2.1節(jié)單純考慮最低時(shí)延情形下的成本一樣，沒(méi)有進(jìn)一步降低。因?yàn)榭赡芨鱾€(gè)需求的最短路徑就只有一條，而為了達(dá)到時(shí)延要求則必須選擇這條路徑。不過(guò)，在現(xiàn)網(wǎng)中，由于實(shí)際的網(wǎng)絡(luò)比較復(fù)雜，對(duì)于一個(gè)需求往往存在多條路徑要求，并且滿(mǎn)足時(shí)延約束。因此很有可能在滿(mǎn)足時(shí)延要求的條件下，增加候選路徑，進(jìn)一步降低擴(kuò)容成本。用一個(gè)例子進(jìn)行說(shuō)明，輸入中國(guó)電信某骨干網(wǎng)31省份的部分需求和拓?fù)?，鏈路成本系?shù)ρe只簡(jiǎn)單地設(shè)置成與鏈路長(zhǎng)度成正比，注意在真實(shí)規(guī)劃中要根據(jù)鏈路實(shí)際情況設(shè)定。應(yīng)用線性規(guī)劃式（4）～式（7），求解不同候選路徑數(shù)目下的最低時(shí)延下的最低成本，并進(jìn)行歸一化比較（以候選路徑數(shù)為一條情況下的成本為1），如圖3所示?？梢钥闯?，在這個(gè)例子中，初期隨著候選路徑的增多，擴(kuò)容成本降低，原因如上所述。當(dāng)候選路徑數(shù)超過(guò)12時(shí)，成本不再降低，原因在于路徑長(zhǎng)度要滿(mǎn)足時(shí)延約束要求，否則即使有更多的候選路徑，如果其不滿(mǎn)足時(shí)延約束要求，在求解時(shí)延約束下的最低成本的過(guò)程中也不會(huì)選擇這些路徑，因此當(dāng)路徑數(shù)超過(guò)一定值時(shí)，成本趨近平穩(wěn)，無(wú)法再下降。

圖3 候選路徑數(shù)對(duì)擴(kuò)容成本的影響

3 拓?fù)涓淖兊木W(wǎng)絡(luò)擴(kuò)容

在前面的討論中，網(wǎng)絡(luò)拓?fù)涫枪潭ú蛔兊?。本文求解了擴(kuò)容滿(mǎn)足需求的情形下的最低時(shí)延問(wèn)題，得出了最低時(shí)延下的各個(gè)路徑的帶寬分配。但是如果要求進(jìn)一步降低時(shí)延，則需要在原來(lái)的拓?fù)渖闲略龉?jié)點(diǎn)間的連接，以縮短某些需求的路徑長(zhǎng)度，從而降低總體的時(shí)延。

有約束的網(wǎng)絡(luò)拓?fù)鋬?yōu)化問(wèn)題往往是NP-hard或者NP-complete問(wèn)題，即隨著問(wèn)題規(guī)模的增大一般無(wú)法在多項(xiàng)式時(shí)間內(nèi)求得精確解，只能用啟發(fā)式算法例如遺傳算法、模擬退火等求得近似解[1]。在時(shí)延約束的骨干網(wǎng)拓?fù)湟?guī)劃中，一般要求新增的鏈路數(shù)為最少。最小生成樹(shù)算法能夠求解最少連接問(wèn)題，但是無(wú)法同時(shí)滿(mǎn)足指定的時(shí)延要求。參考文獻(xiàn)[7]提出了新增鏈路來(lái)降低整體平均最短路徑的方法，但不是降低全局歸一化時(shí)延。同時(shí)，其證明了該問(wèn)題是NP-hard問(wèn)題。其中，選擇新增鏈路采用的貪婪方法是每次從候選鏈路集中添加選擇鏈路，使得所有需求的平均路徑長(zhǎng)度下降最多。另外，離散選址的p中值問(wèn)題中，研究從候選設(shè)備點(diǎn)集中挑選p個(gè)設(shè)備點(diǎn)，每個(gè)需求點(diǎn)連接到一個(gè)設(shè)備點(diǎn)，使得需求點(diǎn)與設(shè)備點(diǎn)距離或運(yùn)輸成本最小，也是NP-hard問(wèn)題，其中貪婪取走算法被證明是一種有效求解方法[8-9]。

類(lèi)似地，本文采用全連接下的貪婪取走算法來(lái)確定新增鏈路。不同的是，這里以全局歸一化時(shí)延增量為取走的衡量標(biāo)準(zhǔn)，從全連接的拓?fù)溟_(kāi)始逐步刪除對(duì)全局時(shí)延影響最小的新增候選鏈路。所謂全連接是指將所有節(jié)點(diǎn)互相連接；相比原始拓?fù)?，多出?lái)的鏈路為新增候選鏈路。另外與之前第一部分中的加權(quán)時(shí)延不同的是，對(duì)各個(gè)需求的時(shí)延分別進(jìn)行了歸一化：設(shè)每個(gè)需求在原始拓?fù)湎碌臅r(shí)延為1。即原始拓?fù)湎拢硞€(gè)需求demand的最短路徑長(zhǎng)度為path_lengthdemand,0，對(duì)應(yīng)時(shí)延為1。全連接拓?fù)湎?，取走第i-1個(gè)鏈路后，新拓?fù)湎略撔枨蟮淖疃搪窂介L(zhǎng)度path_lengthdemand,i-1，則新拓?fù)湎略撔枨蟮臅r(shí)延path_lengthdemand,i-1/ path_lengthdemand,0。同樣地，取走第i個(gè)鏈路該需求的時(shí)延為path_lengthdemand,i/ path_lengthdemand,0，則取走第i個(gè)鏈路后，相比上一輪(取走第i-1個(gè)鏈路)，所有需求的加權(quán)時(shí)延增量，即全局歸一化時(shí)延增量為：

·對(duì)全局各個(gè)需求的時(shí)延進(jìn)行了均衡處理：在取走鏈路時(shí)，不會(huì)只聚集于取走長(zhǎng)度比較小的鏈路。例如邊遠(yuǎn)省份節(jié)點(diǎn)，一般與其連接的鏈路長(zhǎng)度都比較大，如果以絕對(duì)值來(lái)作為取走的標(biāo)準(zhǔn)，它們將大概率被保留，而一些距離比較小的節(jié)點(diǎn)間鏈路將更可能被取走。

·能夠方便地調(diào)節(jié)相關(guān)需求的權(quán)重。通過(guò)歸一化時(shí)延，每個(gè)需求的最大時(shí)延都為1，處于相同水平。在此基礎(chǔ)上，一些質(zhì)量要求高的需求，可以對(duì)其時(shí)延乘以一個(gè)大的權(quán)重，使得該需求保持較低時(shí)延。

3.1 貪婪取走算法確定新增鏈路

根據(jù)上面所述，采用歸一化時(shí)延，以全部需求歸一化時(shí)延的增加程度為刪除標(biāo)準(zhǔn)，能夠刪掉對(duì)全局影響最小的鏈路，只保留下重要的鏈路。假設(shè)歸一化時(shí)延約束值為delayset，需求數(shù)量為N。滿(mǎn)足特定時(shí)延約束的貪婪取走鏈路算法的流程和具體步驟如下。

步驟1輸入原始拓?fù)?，找出所有?jié)點(diǎn)的全連接，減去原始拓?fù)湎碌倪B接，得出全連接下的新增候選鏈路列表[link1,link2,…,linkn]。delaylast_round初始值為全連接拓?fù)湎碌娜謿w一化時(shí)延：采用Dijkstra算法在原始拓?fù)湎孪日页雒總€(gè)需求的最短路徑長(zhǎng)度path_lengthdemand,0，對(duì)應(yīng)時(shí)延為1；在全連接拓?fù)湎抡页雒總€(gè)需求的最短路徑長(zhǎng)度path_lengthdemand,last_round，則某需求的歸一化時(shí)延為path_lengthdemand,last_round/path_lengthdemand,0，再匯總所有需求的歸一化時(shí)延得到全局歸一化時(shí)延delaylast_round：

步驟2從候選鏈路列表中逐步去掉一個(gè)新增鏈路linki（將候選鏈路列表該位置置空，linki=[]）。先判斷其是否在刪除列表或保留列表中。如果是，則跳過(guò)此鏈路，全局歸一化時(shí)延增量列表對(duì)應(yīng)位置Δdelay[i]設(shè)置為最大時(shí)延增量（可設(shè)為需求的數(shù)量，因?yàn)槊總€(gè)需求的時(shí)延最大設(shè)為1），即Δdelay[i]=N。如果不是，去掉這個(gè)新增鏈路linki，計(jì)算去掉后新拓?fù)湎碌娜謿w一化時(shí)延增量Δdelayi和歸一化時(shí)延delayi。Δdelayi和delayi的計(jì)算同樣采用Dijkstra算法先找出每個(gè)需求的最短路徑path_lengthdemand,i，分別得到各個(gè)需求的歸一化時(shí)延 path_lengthdemand,i/ path_lengthdemand,0，再匯總所有需求的歸一化時(shí)延得到全局歸一化時(shí)延delayi：

相比上一輪的增量為 Δ delayi= delayi- delaylast_round。如果delayi＞delayset，不滿(mǎn)足時(shí)延約束，則直接設(shè)置Δdelayi為最大，Δdelayi=N。更新全局歸一化時(shí)延增量列表對(duì)應(yīng)位置Δdelay[i]= Δdelayi。再把這個(gè)已刪除的新增鏈路linki重新添加回候選鏈路列表。

步驟3重復(fù)步驟2，i=i+1，直至遍歷所有n個(gè)候選新增鏈路，得到此輪全局時(shí)延增量列表Δdelay =[Δdelay1, Δdelay2, …, Δdelayn]。

步驟4判斷是否滿(mǎn)足delay≤delayset，即是否[Δdelay1,Δdelay2, …, Δdelayn]中每個(gè)元素都等于N，若是則算法結(jié)束，候選鏈路列表中剩下的新增鏈路即為所求，否則進(jìn)行下一步。

步驟5先將[Δdelay1, Δdelay2, …, Δdelayn]中為0的Δdelayi對(duì)應(yīng)的linki去掉(這些鏈路對(duì)全局時(shí)延沒(méi)有影響，也可以設(shè)置一定的閾值，Δdelayi低于此閾值對(duì)應(yīng)的鏈路都去掉)，添加進(jìn)刪除列表，并將為0的Δdelayi重置為Δdelayi=N。再?gòu)氖Ｓ嗟娜謺r(shí)延增量列表中，找到Δdelay最小值對(duì)應(yīng)的鏈路，即m= arg min([Δdelay1, Δdelay2, …, Δdelayn])。如果有多個(gè)最小值，則取這些最小值中對(duì)應(yīng)鏈路長(zhǎng)度最長(zhǎng)的m。去掉linkm對(duì)全局時(shí)延增加影響最小，所以確定刪掉linkm，將其添加進(jìn)刪除列表。更新去掉linkm后的全局歸一化時(shí)延delaylast_round= delaym。

步驟6重復(fù)步驟2～步驟5，直至為滿(mǎn)足delay≤delayset不能再繼續(xù)刪掉新增連接，算法結(jié)束，候選鏈路列表中剩下的新增鏈路即所求。

3.2 實(shí)驗(yàn)結(jié)果及分析

為證明貪婪取走算法的有效性，采用另外一個(gè)公開(kāi)的網(wǎng)絡(luò)拓?fù)銰EANT（2001年）[10]進(jìn)行驗(yàn)證。在GEANT網(wǎng)絡(luò)中，有27個(gè)節(jié)點(diǎn)，38段鏈路。由于只有節(jié)點(diǎn)的經(jīng)緯度信息，所以直接用節(jié)點(diǎn)間的球面距離近似作為節(jié)點(diǎn)間鏈路的長(zhǎng)度。假設(shè)27節(jié)點(diǎn)間都存在連接需求，則有27×26=702個(gè)需求，全局歸一化時(shí)延最大為702。將所有節(jié)點(diǎn)都連接，在全連接拓?fù)湎掠?jì)算時(shí)延（每個(gè)需求時(shí)延=此時(shí)最短路徑/原來(lái)最短路徑），得到全局歸一化時(shí)延最小為516。所以全局歸一化時(shí)延最多能下降至516/702=73.5%。全連接下的鏈路總數(shù)351，減去現(xiàn)有38條鏈路，候選新增鏈路數(shù)為313條。設(shè)置歸一化時(shí)延約束為原始拓?fù)湎氯謿w一化時(shí)延的95%、90%、85%、80%、75%，即702×0.95=666.9，702×0.9=631.8、702×0.85=596.7、702×0.8=561.6、702×0.75=526.5，將貪婪取走算法與模擬退火算法，以及逐步取走候選新增連接中最長(zhǎng)連接的貪婪算法（這里稱(chēng)為直接貪婪算法）得到的結(jié)果進(jìn)行對(duì)比。

直接貪婪算法中，在滿(mǎn)足時(shí)延約束要求的情況下，每次取走候選新增連接中長(zhǎng)度最長(zhǎng)的連接，所以最后會(huì)剩下那些相對(duì)較短的連接來(lái)滿(mǎn)足時(shí)延約束。

模擬退火的初始溫度設(shè)置為100，溫度衰減系數(shù)為0.98，終止溫度為0.001。每個(gè)溫度下產(chǎn)生200次新解。新解為隨機(jī)產(chǎn)生一個(gè)新增鏈路，或者刪除一個(gè)新增鏈路。判斷新解優(yōu)劣的標(biāo)準(zhǔn)是新增鏈路數(shù)是否小于舊解并滿(mǎn)足時(shí)延約束。滿(mǎn)足歸一化時(shí)延約束時(shí)，新增鏈路數(shù)小于舊解，則新解優(yōu)于舊解，接受新解，否則以一定概率接受新解。如果新解不滿(mǎn)足歸一化的時(shí)延約束，則新解被接受的概率為0。初始解設(shè)為所有新增鏈路，即初始解是全連接。

不同歸一化時(shí)延約束下，3種算法得到的新增鏈路數(shù)如圖4（a）所示?；旧县澙啡∽咚惴ǖ玫叫略鲦溌窋?shù)略少于模擬退火得到的解，部分情況下得到相等數(shù)量的新增鏈路，不過(guò)具體的鏈路不一樣，此外貪婪取走算法運(yùn)行速度比模擬退火算法快很多。而要降到相同的時(shí)延，相比模擬退火和貪婪取走算法，直接貪婪算法要增加更多的新增鏈路。

再對(duì)比這些新增鏈路的總長(zhǎng)度，因?yàn)樾略鲦溌窋?shù)一樣并且滿(mǎn)足時(shí)延約束情況下，從網(wǎng)絡(luò)規(guī)劃角度，新增鏈路總長(zhǎng)度越小越好。在相同時(shí)延約束比例，基本上貪婪取走算法得到的新增鏈路總長(zhǎng)度比模擬退火和直接貪婪算法得到的要小，如圖4（b）所示。

基于另一個(gè)中國(guó)電信骨干網(wǎng)的部分拓?fù)鋽?shù)據(jù)，時(shí)延約束設(shè)置為全部需求的歸一化時(shí)延小于原始拓?fù)湎碌?7%、95%、93%、90%、88%，求滿(mǎn)足這些時(shí)延約束的最少新增連接。這個(gè)骨干網(wǎng)有31個(gè)邏輯節(jié)點(diǎn)，原始基礎(chǔ)拓?fù)浼s有75條邏輯鏈路。將這些節(jié)點(diǎn)全連接，大約有400條新增連接。采用同樣的方法，得到基本類(lèi)似的結(jié)果，如圖4（c）和圖4（d）所示，再次證明貪婪取走算法確定新增連接的有效性和可行性。

圖4 3種算法得到的新增鏈路數(shù)和鏈路總長(zhǎng)度對(duì)比

相比直接貪婪算法，貪婪取走算法在優(yōu)化效果上取得了較好效果（較少的新增鏈路數(shù)和新增鏈路長(zhǎng)度）；相比模擬退火，優(yōu)化效果接近，但貪婪取走算法的計(jì)算速度較快。綜合以上兩個(gè)例子，證明貪婪取走算法是一種比較有效的指定時(shí)延約束下的優(yōu)化網(wǎng)絡(luò)拓?fù)浞椒ā?/p>

網(wǎng)絡(luò)規(guī)劃中往往還有可靠性的要求，例如規(guī)定對(duì)每個(gè)需求，除了最短路徑，與其邊不相交的第二最短路徑也要保證處于一定的時(shí)延約束，進(jìn)行第二路徑的時(shí)延約束。此外，還可以分別對(duì)各個(gè)省份節(jié)點(diǎn)的所有需求進(jìn)行約束，使其低于一個(gè)界限，進(jìn)行省份時(shí)延約束?？梢园凑諏?shí)際需求，設(shè)置更多層次的QoS約束條件，然后在算法中步驟2中進(jìn)行添加，其他不變。這樣在刪除候選鏈路時(shí)候必須保證QoS約束成立，否則不刪除，最終得到滿(mǎn)足多QoS約束下的新增連接。不過(guò)，隨著QoS約束條件的增加，在決定是否刪除候選鏈路時(shí)需要進(jìn)行多次判斷，運(yùn)算時(shí)間也會(huì)增加。

3.3 貪婪取走算法+線性規(guī)劃的結(jié)合

對(duì)于一般的、只要求歸一化時(shí)延約束下的最少連接問(wèn)題，貪婪取走算法可以有效解決，并且得到節(jié)點(diǎn)之間的新增連接。但是，由于只考慮了使得新增鏈路數(shù)量最少，不涉及具體鏈路成本，同時(shí)考慮的是歸一化時(shí)延，比較適合用于網(wǎng)絡(luò)拓?fù)涞膬?yōu)化設(shè)計(jì)。在本文規(guī)劃中，主要用于邏輯節(jié)點(diǎn)層面的新增連接。如果要進(jìn)一步研究擴(kuò)容問(wèn)題，則要更精細(xì)地考慮物理節(jié)點(diǎn)層面的成本問(wèn)題，需考慮各個(gè)需求值的大小，各段鏈路的固有容量及每段鏈路的成本系數(shù)。同時(shí)，不考慮歸一化時(shí)延，而是考慮加權(quán)時(shí)延約束。然后結(jié)合第一節(jié)中的線性規(guī)劃建模方法，可以求解得到滿(mǎn)足加權(quán)時(shí)延約束下的最低成本的新增連接。即貪婪取走算法先得到一個(gè)候選鏈路集（邏輯節(jié)點(diǎn)層面），再將邏輯節(jié)點(diǎn)層面的候選鏈路集對(duì)應(yīng)成物理節(jié)點(diǎn)層面的鏈路集，再繼續(xù)用貪婪取走的思路，結(jié)合線性規(guī)劃從候選鏈路集中繼續(xù)挑選新增鏈路（物理節(jié)點(diǎn)層面），使得新增鏈路后，即滿(mǎn)足加權(quán)時(shí)延約束又達(dá)到擴(kuò)容成本最低。

這里分成兩步得出最終的新增鏈路，而不是用貪婪取走算法結(jié)合線性規(guī)劃一步得出，是因?yàn)樵谪澙啡∽咚惴ㄖ忻枯喦蠼舛鄠€(gè)線性規(guī)劃也相對(duì)耗時(shí)，所以先不考慮線性規(guī)劃，可快速地得出比較少數(shù)量的候選鏈路集，在此基礎(chǔ)上再用貪婪取走算法+線性規(guī)劃，每輪可以求解比較少的線性規(guī)劃問(wèn)題，等于候選鏈路數(shù)目。

在線性規(guī)劃式（1）～式（3）中，得到最小加權(quán)時(shí)延delaymin后，想進(jìn)一步下降delaymin，設(shè)下降比例為ratio，即delayneed=delaymin×ratio。注意delaymin和delayneed是加權(quán)的時(shí)延，不是歸一化的時(shí)延?？梢韵仍O(shè)定歸一化時(shí)延的約束delayset，然后用貪婪取走算法先計(jì)算得出候選鏈路列表，再運(yùn)行最低時(shí)延的線性規(guī)劃算法式（1）～式（3），判斷在候選鏈路列表下是否能滿(mǎn)足加權(quán)的時(shí)延要求delay≤delayneed。如果不能，說(shuō)明歸一化時(shí)延的約束值設(shè)置得較大，需重新將約束值調(diào)小，才能產(chǎn)生更多的候選鏈路，從而更有可能使得加權(quán)時(shí)延降低以滿(mǎn)足約束。如果delay?delayneed則說(shuō)明候選鏈路過(guò)多，說(shuō)明歸一化時(shí)延的約束值設(shè)置得較小，需重新將約束值調(diào)大，避免產(chǎn)生太多候選鏈路。當(dāng)delay小于并接近delayneed，繼續(xù)考慮貪婪取走算法結(jié)合線性規(guī)劃算法。每輪去掉一個(gè)候選鏈路，基于當(dāng)前拓?fù)溆镁€性規(guī)劃式（4）～式（7）計(jì)算最低成本（目標(biāo)函數(shù)要多加一項(xiàng)新增鏈路開(kāi)通成本），遍歷后刪除最小成本（成本下降量最大）對(duì)應(yīng)的取走鏈路，直至為滿(mǎn)足加權(quán)時(shí)延約束，不能再刪除任何一個(gè)候選鏈路為止。

僅使用貪婪取走算法屬于“粗調(diào)”，貪婪取走算法加上線性規(guī)劃算法屬于“細(xì)調(diào)”。當(dāng)考慮加權(quán)時(shí)延約束，并且需要考慮需求流量大小和鏈路成本等時(shí)，貪婪取走算法結(jié)合線性規(guī)劃算法，可以更為合理地解決新增鏈路問(wèn)題，最終得到新增鏈路下各個(gè)需求在各個(gè)候選路徑的帶寬分配以及鏈路需要增加的容量。另外，也可以在貪婪取走算法得到的候選連接下，直接進(jìn)一步考慮線性規(guī)劃算法式（4）～式（7），求出成本最低的滿(mǎn)足時(shí)延約束的擴(kuò)容，不再逐輪考慮刪除候選連接，但這樣可能多開(kāi)通了一些新增連接，成本會(huì)比較高。

4 模型效果評(píng)估及展望

評(píng)估網(wǎng)絡(luò)方案的優(yōu)劣是一個(gè)復(fù)雜的工作[10]，本文主要從資源優(yōu)化角度考慮此問(wèn)題，運(yùn)營(yíng)層面的評(píng)估不在本文的考慮范圍內(nèi)，從以下角度來(lái)評(píng)估資源優(yōu)化方案。

·資源分配的效率，也就是說(shuō)能用最少的資源滿(mǎn)足業(yè)務(wù)需求和各類(lèi)業(yè)務(wù)層面的約束條件。資源分配效率的評(píng)估指標(biāo)相對(duì)簡(jiǎn)單，主要關(guān)注總的資源使用量，由于采用了線性規(guī)劃模型，那么模型的有效性地關(guān)鍵是定義成本函數(shù)；既要客觀地評(píng)估實(shí)際的網(wǎng)絡(luò)建設(shè)成本，同時(shí)還應(yīng)考慮算法的可收斂性。

·資源分配方案對(duì)網(wǎng)絡(luò)性能的影響，針對(duì)某一個(gè)特定的網(wǎng)絡(luò)性能指標(biāo)，不同的資源分配方案對(duì)該性能指標(biāo)的影響；本文主要關(guān)注時(shí)延數(shù)據(jù)，評(píng)估標(biāo)準(zhǔn)是時(shí)延性能的改善程度以及與物理最優(yōu)時(shí)延的逼近效果。

·資源分配的公平性[12－13]，也就是說(shuō)，當(dāng)出現(xiàn)資源搶占時(shí)，能以一種“公平”的方式合理地分配資源。當(dāng)然，“公平”的定義方式可以是多樣化、可定制的。

本文主要考慮前兩點(diǎn)，并應(yīng)用到實(shí)際的IP骨干網(wǎng)規(guī)劃中。未來(lái)計(jì)劃在以下幾個(gè)方面繼續(xù)增強(qiáng)算法能力和模型的全面性，以適應(yīng)更復(fù)雜的業(yè)務(wù)場(chǎng)景。

·路由優(yōu)化場(chǎng)景，將容量規(guī)劃與路由優(yōu)化的結(jié)合，補(bǔ)充路由優(yōu)化場(chǎng)景，解決短期內(nèi)現(xiàn)網(wǎng)資源無(wú)法提供業(yè)務(wù)的場(chǎng)景。

·量化的可靠性模型，現(xiàn)有的資源預(yù)留機(jī)制采用隨機(jī)故障模型，并不能反映底層物理網(wǎng)絡(luò)實(shí)際的故障概率。未來(lái)計(jì)劃使用現(xiàn)網(wǎng)故障統(tǒng)計(jì)數(shù)據(jù)建立骨干網(wǎng)故障的概率模型，更加準(zhǔn)確地判斷故障特征，并提供資源預(yù)留。

·公平性約束問(wèn)題，當(dāng)資源受限時(shí)，需要根據(jù)一定公平性原則進(jìn)行分配或擴(kuò)容。計(jì)劃研究公平性資源分配/擴(kuò)容算法在IP骨干網(wǎng)的應(yīng)用，探索適應(yīng)互聯(lián)網(wǎng)特點(diǎn)的層次化QoS模型，更加公平地為互聯(lián)網(wǎng)客戶(hù)分配資源。

5 結(jié)束語(yǔ)

本文詳細(xì)地研究了網(wǎng)絡(luò)規(guī)劃的兩個(gè)關(guān)聯(lián)場(chǎng)景：給定固定拓?fù)淝闆r下，求解滿(mǎn)足時(shí)延約束的最低成本擴(kuò)容；拓?fù)涓淖兦闆r下，求解滿(mǎn)足時(shí)延約束的新增鏈路拓?fù)湓O(shè)計(jì)和擴(kuò)容。分別作出相關(guān)數(shù)學(xué)描述和提出解決算法，并結(jié)合示例以及現(xiàn)網(wǎng)數(shù)據(jù)進(jìn)行分析。本文提出的方法可以應(yīng)用到實(shí)際的網(wǎng)絡(luò)規(guī)劃和優(yōu)化中，對(duì)運(yùn)營(yíng)商網(wǎng)絡(luò)規(guī)劃和優(yōu)化有一定借鑒和啟發(fā)意義。