基于時延約束的廣域網絡 拓撲設計和容量規劃

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

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

1 引言

如何讓IP網絡的拓撲設計和容量規劃高效滿足互聯網業務高速增長需求，是基礎電信運營商基礎網絡建設和運營部門面臨的重大挑戰，包括以下3方面。

·架構設計變革后的評估和優化困難：經典的分層匯聚式網絡架構，面臨核心匯聚節點壓力過大、非核心省份間時延性能差等問題，無法持續；而轉向全面扁平化網絡后，則缺少精確的量化評估手段以實現拓撲的最優化設計和最優化變更。

·路由優化效率較低：運營商IP廣域網的路由設計一般依賴于網絡設備的分布式路由協議，無法滿足面向業務/客戶的、定制化的復雜約束條件，也難以保障網絡利用率的均衡，導致IP骨干網絡利用率一般只能在50%上下，網絡建設成本高。

·多維協同困難：IP廣域網絡的結構設計與成本約束與底層傳輸網絡關系巨大，僅依賴IP網絡層的約束無法實現整體性能和成本的最優。

具體到日常的網絡容量規劃中，存在多種需求場景，包括但不限于以下幾種。

·快速擴容場景：主要滿足突發性業務需求，規模一般較小；實際操作時，約束因素相對較少，可快速滿足業務需求。

·常規擴容場景：運營商根據每年的業務發展預期，按需對現有網絡資源進行增加或調整。

·多約束擴容場景：在擴容過程中，會面臨很多實際的約束，比如投資規模限制、是否允許優化拓撲、是否有特定業務時延要求等。

對運營商的網絡規劃，通常需要考慮時延、帶寬、鏈路利用率和投資成本等方面。隨著低時延網絡應用業務的涌現，例如游戲、直播、高清會議、電子交易等，時延成為網絡規劃任務中的一個重要因素。此外，成本是必須考慮的一個重要方面，需要在保障業務需求的同時，盡可能地降低網絡建設成本。本文從時延/成本優化方面改進傳統的IP骨干網拓撲設計與容量規劃，推動實現廣域IP網絡設計過程的智能化與自動化，以期解決IP網絡演進中面臨的部分挑戰。本文對容量規劃問題進行數學建模，主要考慮傳輸時延的約束，分為拓撲固定和拓撲可變網絡擴容兩類問題，可以覆蓋部分上述業務場景。

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

通常，涉及目標函數為線性的優化問題，可以利用線性規劃求解。傳統上，大量的網絡規劃也可以建模成線性規劃問題從而求得最優解。一般做法是提前對需求給定候選路徑，每一個路徑對應一個待分配流量。但涉及拓撲改變問題時，候選路徑是動態變化的，不應該提前給定。而如果不提前對需求先給定候選路徑，隨著拓撲的增大，潛在的路徑數迅速增加，給求解帶來困難[1]。另外，一旦涉及變量值只能涉及離散值，則線性規劃變成整數規劃，隨著問題規模的增大，求解難度迅速增加，大多是NP-hard問題，只能采用一些啟發式算法來進行求解。本文針對運營商網絡規劃的需求和特點，從實際業務角度出發，定義了帶權重的傳播時延（流量×路徑長度）和全局歸一化時延（原始拓撲下各個需求的最短路徑長度對應時延1），針對拓撲不變和拓撲改變的情形，主要應用了線性規劃和貪婪算法來建模和求解。

相比傳統的做法，在應用線性規劃求解最低時延時，本文不但考慮傳輸時延（路徑長度），還加入需求量的影響，最優化需求量與路徑長度的乘積。在應用貪婪算法尋找新增連接時，考慮了全局歸一化時延的影響。首先研究了相對簡單的拓撲固定情況下的最低時延和滿足時延約束的最低成本的場景。在此基礎上，考慮改變網絡拓撲，新增網絡連接降低整體時延；進一步研究滿足時延約束下成本最低新增網絡連接，即最低成本的新增局向問題。

2 拓撲不變的網絡擴容

將網絡表示為一個無向圖G(V,E)，V表示網絡節點，E表示節點間的鏈路。采用路徑建模（path formulation）的方法來研究網絡規劃問題，即對各個需求，提前確定候選路徑，每個需求的各條路徑對應的流為一個變量[1]。下面研究目標函數為最低時延及最低時延下的最低成本情形，同時滿足各個需求的帶寬要求。其中，這里的“最低”是指給定候選路徑下所能達到的最低。

2.1 求解最低時延

本文中只考慮路徑長度帶來的時延。同時，從網絡運營的角度，更為合理的是考慮需求值的權重，對節點間最短路徑進行加權，即對時延進行加權，用需求的帶寬×需求點之間最短路徑長度來表示。如圖1（a）所示，從A到B的需求是1 Gbit/s，最短路徑長度是1 km，從A到C的需求是99 Gbit/s，最短路徑長度是100 km。圖1（b）中，A到B的需求是99 Gbit/s，A到C的需求是1 Gbit/s，路徑長度和圖1（a）相同。雖然從A點出來的流量都是100 Gbit/s，但從網絡運營的角度，圖1（b）的總體時延要低于圖1（a）的，因為圖1（b）的大部分流量都用了比較短的路徑，而為圖1（a）的大部分流量都用了比較長的路徑。

圖1 不同需求的時延比較

本節研究的最低時延是總體的最低時延，即讓盡量多的流量通過比較短的路徑。所以不但需求對應的節點間路徑長度與時延有關，需求的值也有影響，所以當考慮最低時延時，最小化的是∑需求量×路徑長度，而不是最小化需求中的最大時延。

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

當xdp對應的路徑包含e鏈路時，δedp=1，其余時候為0。

式（1）是目標函數，是加權的需求和路徑長度的乘積，即對應加權的時延。式（2）表示每個需求P條路徑的流量之和等于需求值，需求得到滿足。式（3）表示對每段鏈路，其承載的各個需求的流不超過其新增的容量和固有容量之和的80%。如果對某些鏈路容量有限制，則可以設置相應的鏈路容量變量ye處在某些范圍。

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

圖2 一個需求可能存在多個相等路徑

2.2 求解最低時延下的最低成本

由于本文采用了路徑建模，路徑中可能存在兩條或多條路徑時延相同，但成本不一樣，因此可能在第2.1節中最低時延擴容問題的基礎上進一步求出最低成本。同理，可以在最低成本的基礎上，求解最低時延。在第2.1節中求解出最低時延，將其作為一個約束條件，將目標函數改成鏈路成本，就可以求解出最低時延下的最低成本，ρe為鏈路e的成本系數。線性規劃建模如下：

當xdp對應的路徑包含e鏈路時，δedp=1，其余時候為0。

如果把式（5）最低時延約束修改成其他時延值約束，則該線性規劃是更普遍形式的時延約束下的最低成本問題。當然，該線性規劃求解結果可能和第2.1節單純考慮最低時延情形下的成本一樣，沒有進一步降低。因為可能各個需求的最短路徑就只有一條，而為了達到時延要求則必須選擇這條路徑。不過，在現網中，由于實際的網絡比較復雜，對于一個需求往往存在多條路徑要求，并且滿足時延約束。因此很有可能在滿足時延要求的條件下，增加候選路徑，進一步降低擴容成本。用一個例子進行說明，輸入中國電信某骨干網31省份的部分需求和拓撲，鏈路成本系數ρe只簡單地設置成與鏈路長度成正比，注意在真實規劃中要根據鏈路實際情況設定。應用線性規劃式（4）～式（7），求解不同候選路徑數目下的最低時延下的最低成本，并進行歸一化比較（以候選路徑數為一條情況下的成本為1），如圖3所示。可以看出，在這個例子中，初期隨著候選路徑的增多，擴容成本降低，原因如上所述。當候選路徑數超過12時，成本不再降低，原因在于路徑長度要滿足時延約束要求，否則即使有更多的候選路徑，如果其不滿足時延約束要求，在求解時延約束下的最低成本的過程中也不會選擇這些路徑，因此當路徑數超過一定值時，成本趨近平穩，無法再下降。

圖3 候選路徑數對擴容成本的影響

3 拓撲改變的網絡擴容

在前面的討論中，網絡拓撲是固定不變的。本文求解了擴容滿足需求的情形下的最低時延問題，得出了最低時延下的各個路徑的帶寬分配。但是如果要求進一步降低時延，則需要在原來的拓撲上新增節點間的連接，以縮短某些需求的路徑長度，從而降低總體的時延。

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

類似地，本文采用全連接下的貪婪取走算法來確定新增鏈路。不同的是，這里以全局歸一化時延增量為取走的衡量標準，從全連接的拓撲開始逐步刪除對全局時延影響最小的新增候選鏈路。所謂全連接是指將所有節點互相連接；相比原始拓撲，多出來的鏈路為新增候選鏈路。另外與之前第一部分中的加權時延不同的是，對各個需求的時延分別進行了歸一化：設每個需求在原始拓撲下的時延為1。即原始拓撲下，某個需求demand的最短路徑長度為path_lengthdemand,0，對應時延為1。全連接拓撲下，取走第i-1個鏈路后，新拓撲下該需求的最短路徑長度path_lengthdemand,i-1，則新拓撲下該需求的時延path_lengthdemand,i-1/ path_lengthdemand,0。同樣地，取走第i個鏈路該需求的時延為path_lengthdemand,i/ path_lengthdemand,0，則取走第i個鏈路后，相比上一輪(取走第i-1個鏈路)，所有需求的加權時延增量，即全局歸一化時延增量為：

·對全局各個需求的時延進行了均衡處理：在取走鏈路時，不會只聚集于取走長度比較小的鏈路。例如邊遠省份節點，一般與其連接的鏈路長度都比較大，如果以絕對值來作為取走的標準，它們將大概率被保留，而一些距離比較小的節點間鏈路將更可能被取走。

·能夠方便地調節相關需求的權重。通過歸一化時延，每個需求的最大時延都為1，處于相同水平。在此基礎上，一些質量要求高的需求，可以對其時延乘以一個大的權重，使得該需求保持較低時延。

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

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

步驟1輸入原始拓撲，找出所有節點的全連接，減去原始拓撲下的連接，得出全連接下的新增候選鏈路列表[link1,link2,…,linkn]。delaylast_round初始值為全連接拓撲下的全局歸一化時延：采用Dijkstra算法在原始拓撲下先找出每個需求的最短路徑長度path_lengthdemand,0，對應時延為1；在全連接拓撲下找出每個需求的最短路徑長度path_lengthdemand,last_round，則某需求的歸一化時延為path_lengthdemand,last_round/path_lengthdemand,0，再匯總所有需求的歸一化時延得到全局歸一化時延delaylast_round：

步驟2從候選鏈路列表中逐步去掉一個新增鏈路linki（將候選鏈路列表該位置置空，linki=[]）。先判斷其是否在刪除列表或保留列表中。如果是，則跳過此鏈路，全局歸一化時延增量列表對應位置Δdelay[i]設置為最大時延增量（可設為需求的數量，因為每個需求的時延最大設為1），即Δdelay[i]=N。如果不是，去掉這個新增鏈路linki，計算去掉后新拓撲下的全局歸一化時延增量Δdelayi和歸一化時延delayi。Δdelayi和delayi的計算同樣采用Dijkstra算法先找出每個需求的最短路徑path_lengthdemand,i，分別得到各個需求的歸一化時延 path_lengthdemand,i/ path_lengthdemand,0，再匯總所有需求的歸一化時延得到全局歸一化時延delayi：

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

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

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

步驟5先將[Δdelay1, Δdelay2, …, Δdelayn]中為0的Δdelayi對應的linki去掉(這些鏈路對全局時延沒有影響，也可以設置一定的閾值，Δdelayi低于此閾值對應的鏈路都去掉)，添加進刪除列表，并將為0的Δdelayi重置為Δdelayi=N。再從剩余的全局時延增量列表中，找到Δdelay最小值對應的鏈路，即m= arg min([Δdelay1, Δdelay2, …, Δdelayn])。如果有多個最小值，則取這些最小值中對應鏈路長度最長的m。去掉linkm對全局時延增加影響最小，所以確定刪掉linkm，將其添加進刪除列表。更新去掉linkm后的全局歸一化時延delaylast_round= delaym。

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

3.2 實驗結果及分析

為證明貪婪取走算法的有效性，采用另外一個公開的網絡拓撲GEANT（2001年）[10]進行驗證。在GEANT網絡中，有27個節點，38段鏈路。由于只有節點的經緯度信息，所以直接用節點間的球面距離近似作為節點間鏈路的長度。假設27節點間都存在連接需求，則有27×26=702個需求，全局歸一化時延最大為702。將所有節點都連接，在全連接拓撲下計算時延（每個需求時延=此時最短路徑/原來最短路徑），得到全局歸一化時延最小為516。所以全局歸一化時延最多能下降至516/702=73.5%。全連接下的鏈路總數351，減去現有38條鏈路，候選新增鏈路數為313條。設置歸一化時延約束為原始拓撲下全局歸一化時延的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，將貪婪取走算法與模擬退火算法，以及逐步取走候選新增連接中最長連接的貪婪算法（這里稱為直接貪婪算法）得到的結果進行對比。

直接貪婪算法中，在滿足時延約束要求的情況下，每次取走候選新增連接中長度最長的連接，所以最后會剩下那些相對較短的連接來滿足時延約束。

模擬退火的初始溫度設置為100，溫度衰減系數為0.98，終止溫度為0.001。每個溫度下產生200次新解。新解為隨機產生一個新增鏈路，或者刪除一個新增鏈路。判斷新解優劣的標準是新增鏈路數是否小于舊解并滿足時延約束。滿足歸一化時延約束時，新增鏈路數小于舊解，則新解優于舊解，接受新解，否則以一定概率接受新解。如果新解不滿足歸一化的時延約束，則新解被接受的概率為0。初始解設為所有新增鏈路，即初始解是全連接。

不同歸一化時延約束下，3種算法得到的新增鏈路數如圖4（a）所示。基本上貪婪取走算法得到新增鏈路數略少于模擬退火得到的解，部分情況下得到相等數量的新增鏈路，不過具體的鏈路不一樣，此外貪婪取走算法運行速度比模擬退火算法快很多。而要降到相同的時延，相比模擬退火和貪婪取走算法，直接貪婪算法要增加更多的新增鏈路。

再對比這些新增鏈路的總長度，因為新增鏈路數一樣并且滿足時延約束情況下，從網絡規劃角度，新增鏈路總長度越小越好。在相同時延約束比例，基本上貪婪取走算法得到的新增鏈路總長度比模擬退火和直接貪婪算法得到的要小，如圖4（b）所示。

基于另一個中國電信骨干網的部分拓撲數據，時延約束設置為全部需求的歸一化時延小于原始拓撲下的97%、95%、93%、90%、88%，求滿足這些時延約束的最少新增連接。這個骨干網有31個邏輯節點，原始基礎拓撲約有75條邏輯鏈路。將這些節點全連接，大約有400條新增連接。采用同樣的方法，得到基本類似的結果，如圖4（c）和圖4（d）所示，再次證明貪婪取走算法確定新增連接的有效性和可行性。

圖4 3種算法得到的新增鏈路數和鏈路總長度對比

相比直接貪婪算法，貪婪取走算法在優化效果上取得了較好效果（較少的新增鏈路數和新增鏈路長度）；相比模擬退火，優化效果接近，但貪婪取走算法的計算速度較快。綜合以上兩個例子，證明貪婪取走算法是一種比較有效的指定時延約束下的優化網絡拓撲方法。

網絡規劃中往往還有可靠性的要求，例如規定對每個需求，除了最短路徑，與其邊不相交的第二最短路徑也要保證處于一定的時延約束，進行第二路徑的時延約束。此外，還可以分別對各個省份節點的所有需求進行約束，使其低于一個界限，進行省份時延約束。可以按照實際需求，設置更多層次的QoS約束條件，然后在算法中步驟2中進行添加，其他不變。這樣在刪除候選鏈路時候必須保證QoS約束成立，否則不刪除，最終得到滿足多QoS約束下的新增連接。不過，隨著QoS約束條件的增加，在決定是否刪除候選鏈路時需要進行多次判斷，運算時間也會增加。

3.3 貪婪取走算法+線性規劃的結合

對于一般的、只要求歸一化時延約束下的最少連接問題，貪婪取走算法可以有效解決，并且得到節點之間的新增連接。但是，由于只考慮了使得新增鏈路數量最少，不涉及具體鏈路成本，同時考慮的是歸一化時延，比較適合用于網絡拓撲的優化設計。在本文規劃中，主要用于邏輯節點層面的新增連接。如果要進一步研究擴容問題，則要更精細地考慮物理節點層面的成本問題，需考慮各個需求值的大小，各段鏈路的固有容量及每段鏈路的成本系數。同時，不考慮歸一化時延，而是考慮加權時延約束。然后結合第一節中的線性規劃建模方法，可以求解得到滿足加權時延約束下的最低成本的新增連接。即貪婪取走算法先得到一個候選鏈路集（邏輯節點層面），再將邏輯節點層面的候選鏈路集對應成物理節點層面的鏈路集，再繼續用貪婪取走的思路，結合線性規劃從候選鏈路集中繼續挑選新增鏈路（物理節點層面），使得新增鏈路后，即滿足加權時延約束又達到擴容成本最低。

這里分成兩步得出最終的新增鏈路，而不是用貪婪取走算法結合線性規劃一步得出，是因為在貪婪取走算法中每輪求解多個線性規劃也相對耗時，所以先不考慮線性規劃，可快速地得出比較少數量的候選鏈路集，在此基礎上再用貪婪取走算法+線性規劃，每輪可以求解比較少的線性規劃問題，等于候選鏈路數目。

在線性規劃式（1）～式（3）中，得到最小加權時延delaymin后，想進一步下降delaymin，設下降比例為ratio，即delayneed=delaymin×ratio。注意delaymin和delayneed是加權的時延，不是歸一化的時延。可以先設定歸一化時延的約束delayset，然后用貪婪取走算法先計算得出候選鏈路列表，再運行最低時延的線性規劃算法式（1）～式（3），判斷在候選鏈路列表下是否能滿足加權的時延要求delay≤delayneed。如果不能，說明歸一化時延的約束值設置得較大，需重新將約束值調小，才能產生更多的候選鏈路，從而更有可能使得加權時延降低以滿足約束。如果delay?delayneed則說明候選鏈路過多，說明歸一化時延的約束值設置得較小，需重新將約束值調大，避免產生太多候選鏈路。當delay小于并接近delayneed，繼續考慮貪婪取走算法結合線性規劃算法。每輪去掉一個候選鏈路，基于當前拓撲用線性規劃式（4）～式（7）計算最低成本（目標函數要多加一項新增鏈路開通成本），遍歷后刪除最小成本（成本下降量最大）對應的取走鏈路，直至為滿足加權時延約束，不能再刪除任何一個候選鏈路為止。

僅使用貪婪取走算法屬于“粗調”，貪婪取走算法加上線性規劃算法屬于“細調”。當考慮加權時延約束，并且需要考慮需求流量大小和鏈路成本等時，貪婪取走算法結合線性規劃算法，可以更為合理地解決新增鏈路問題，最終得到新增鏈路下各個需求在各個候選路徑的帶寬分配以及鏈路需要增加的容量。另外，也可以在貪婪取走算法得到的候選連接下，直接進一步考慮線性規劃算法式（4）～式（7），求出成本最低的滿足時延約束的擴容，不再逐輪考慮刪除候選連接，但這樣可能多開通了一些新增連接，成本會比較高。

4 模型效果評估及展望

評估網絡方案的優劣是一個復雜的工作[10]，本文主要從資源優化角度考慮此問題，運營層面的評估不在本文的考慮范圍內，從以下角度來評估資源優化方案。

·資源分配的效率，也就是說能用最少的資源滿足業務需求和各類業務層面的約束條件。資源分配效率的評估指標相對簡單，主要關注總的資源使用量，由于采用了線性規劃模型，那么模型的有效性地關鍵是定義成本函數；既要客觀地評估實際的網絡建設成本，同時還應考慮算法的可收斂性。

·資源分配方案對網絡性能的影響，針對某一個特定的網絡性能指標，不同的資源分配方案對該性能指標的影響；本文主要關注時延數據，評估標準是時延性能的改善程度以及與物理最優時延的逼近效果。

·資源分配的公平性[12－13]，也就是說，當出現資源搶占時，能以一種“公平”的方式合理地分配資源。當然，“公平”的定義方式可以是多樣化、可定制的。

本文主要考慮前兩點，并應用到實際的IP骨干網規劃中。未來計劃在以下幾個方面繼續增強算法能力和模型的全面性，以適應更復雜的業務場景。

·路由優化場景，將容量規劃與路由優化的結合，補充路由優化場景，解決短期內現網資源無法提供業務的場景。

·量化的可靠性模型，現有的資源預留機制采用隨機故障模型，并不能反映底層物理網絡實際的故障概率。未來計劃使用現網故障統計數據建立骨干網故障的概率模型，更加準確地判斷故障特征，并提供資源預留。

·公平性約束問題，當資源受限時，需要根據一定公平性原則進行分配或擴容。計劃研究公平性資源分配/擴容算法在IP骨干網的應用，探索適應互聯網特點的層次化QoS模型，更加公平地為互聯網客戶分配資源。

5 結束語

本文詳細地研究了網絡規劃的兩個關聯場景：給定固定拓撲情況下，求解滿足時延約束的最低成本擴容；拓撲改變情況下，求解滿足時延約束的新增鏈路拓撲設計和擴容。分別作出相關數學描述和提出解決算法，并結合示例以及現網數據進行分析。本文提出的方法可以應用到實際的網絡規劃和優化中，對運營商網絡規劃和優化有一定借鑒和啟發意義。