網(wǎng)絡(luò)優(yōu)化問題建模

寬帶光纖傳輸與通信網(wǎng)技術(shù)重點(diǎn)實(shí)驗(yàn)室虞紅芳博士副教授第四章網(wǎng)絡(luò)優(yōu)化介紹和建模（IntroductiontoNetworkOptimization）本章主要內(nèi)容14.1網(wǎng)絡(luò)建模基本方法24.2建模技巧一個(gè)思考題將介紹兩種典型的網(wǎng)絡(luò)優(yōu)化問題的描述方法：節(jié)點(diǎn)－鏈路（node-link）和鏈路－路徑（link-path）。Node-link建模和Link-path建模方法的特點(diǎn)和各自的優(yōu)缺點(diǎn)。

一個(gè)例子我們先考慮3節(jié)點(diǎn)的網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)都與其它兩個(gè)節(jié)點(diǎn)相連，網(wǎng)絡(luò)拓?fù)涫且粋€(gè)三角形，如上圖所示。節(jié)點(diǎn)是網(wǎng)絡(luò)中路由器或交換設(shè)備的統(tǒng)稱。網(wǎng)絡(luò)中的業(yè)務(wù)流量業(yè)務(wù)需求量代表節(jié)點(diǎn)對(duì)之間的業(yè)務(wù)量或要求的帶寬。假設(shè)節(jié)點(diǎn)1和2之間的業(yè)務(wù)需求量為7個(gè)單位，節(jié)點(diǎn)1和3之間的業(yè)務(wù)需求量為7個(gè)單位，節(jié)點(diǎn)2和3之間的業(yè)務(wù)需求量為8個(gè)單位。我們假設(shè)業(yè)務(wù)需求和鏈路都是雙向（無向）的，h用來表示業(yè)務(wù)需要量，則有：h12=5,h13=7,h23=8。這里，h的下標(biāo)表示業(yè)務(wù)的兩個(gè)起點(diǎn)和終點(diǎn)。承載業(yè)務(wù)的路徑在上述三節(jié)點(diǎn)網(wǎng)絡(luò)中，節(jié)點(diǎn)對(duì)間的業(yè)務(wù)量都可以通過兩條路徑來路由。如，節(jié)點(diǎn)1和2之間的業(yè)務(wù)需求量可以在路徑1－2上直接路由至2，也可以通過節(jié)點(diǎn)3（1－3－2）進(jìn)行路由。每一條路徑上應(yīng)該分配多少流量由網(wǎng)絡(luò)設(shè)計(jì)的優(yōu)化目標(biāo)決定。流量傳輸?shù)臄?shù)學(xué)表示如果我們用帶下標(biāo)的變量x來表示業(yè)務(wù)在每條路徑上分配的流量，那么對(duì)于需求對(duì)<1,2>，我們可以得到如下等式：這里，x的下標(biāo)表示路由或路徑；上面例子中的下標(biāo)12和132分別表示路徑1－2和1－3－2。同樣地，需求節(jié)點(diǎn)對(duì)＜1,3＞和＜2,3＞，也可以分別寫成下面的等式：鏈路容量限制通信網(wǎng)絡(luò)中的任何鏈路都有容量上限，例子中的3條鏈路的容量分別表示為：鏈路容量限制是指所有業(yè)務(wù)在某條鏈路上使用的容量總和要小于鏈路的實(shí)際容量，因此三條鏈路的容量限制可以表示為：優(yōu)化目標(biāo)網(wǎng)絡(luò)優(yōu)化中有很多優(yōu)化目標(biāo)，如最小化路由開銷、最小化擁塞、流量均衡等。假設(shè)我們的目標(biāo)是使總路由開銷最小。假定單位流量流經(jīng)路徑上每條鏈路的代價(jià)都設(shè)為1，那么總的路由開銷就可以表示為：完整的數(shù)學(xué)模型這就是link-path的建模方式從另外一個(gè)方面來思考同一個(gè)問題Link-path模型中，承載每個(gè)業(yè)務(wù)需求的路徑是給定的，模型需要求解的是每個(gè)業(yè)務(wù)在給定的每條路徑上分配多少流量。那對(duì)于一個(gè)業(yè)務(wù)而言，我們能不能把這個(gè)業(yè)務(wù)在每條鏈路上使用的網(wǎng)絡(luò)流量作為一個(gè)變量來求解呢？為什么要這樣思考？如果我們知道一個(gè)業(yè)務(wù)在網(wǎng)絡(luò)中的每條鏈路上使用了多少流量，那么意味著什么呢？意味著這個(gè)業(yè)務(wù)在網(wǎng)絡(luò)中怎么路由就知道了。那么我們?cè)趺磥砻枋鲆粋€(gè)業(yè)務(wù)在每條鏈路上使用的流量呢？他們應(yīng)該滿足什么約束呢？網(wǎng)絡(luò)模型和符號(hào)

上圖給出的三個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，我們分別用兩條單向（有向）鏈路替代每一條無向（雙向）鏈路，例如，無向鏈路1-2用兩條有向鏈路來表示：1→2，2→1。我們假設(shè)業(yè)務(wù)需求量h12是開始于節(jié)點(diǎn)1，結(jié)束于節(jié)點(diǎn)2。Xmn,ij:表示節(jié)點(diǎn)i→j的業(yè)務(wù)量在鏈路m→n上使用的容量流量守恒如果一個(gè)節(jié)點(diǎn)不是業(yè)務(wù)需求對(duì)的源目節(jié)點(diǎn)，我們把這樣的節(jié)點(diǎn)叫做中間節(jié)點(diǎn)。從中間節(jié)點(diǎn)上看這些鏈路流量，會(huì)發(fā)現(xiàn)進(jìn)來的鏈路總流量等于出去的鏈路總流量，這個(gè)叫做流量守恒定理。如果節(jié)點(diǎn)是業(yè)務(wù)需求對(duì)的源節(jié)點(diǎn)，出去的流量之和減去進(jìn)來的流量和等于業(yè)務(wù)需求量。如果節(jié)點(diǎn)是業(yè)務(wù)需求對(duì)的目的節(jié)點(diǎn)，進(jìn)來的總流量減去出去的流量之和也必等于業(yè)務(wù)需求量。

流量守恒的數(shù)學(xué)模型表述源節(jié)點(diǎn)中間節(jié)點(diǎn)目的節(jié)點(diǎn)x31,12x21,12x31,12x23,12x23,12x21,12完整的模型如果網(wǎng)絡(luò)中還同時(shí)有1到3和2到3的業(yè)務(wù)，那么這個(gè)模型應(yīng)該怎么寫？這就是node-link的模型容量設(shè)計(jì)問題給定網(wǎng)絡(luò)拓?fù)銰（V，E）和網(wǎng)絡(luò)業(yè)務(wù)需求矩陣D。這些給定的業(yè)務(wù)可以在不同的路徑上路由。我們需要在保證使用的代價(jià)最小的情況下，確定網(wǎng)絡(luò)的每條鏈路容量。例子右圖的網(wǎng)絡(luò)有四個(gè)節(jié)點(diǎn)，五條無向鏈路，V=4，E=5。圖上面部分表示有三個(gè)無向業(yè)務(wù)需求對(duì)，D=3。節(jié)點(diǎn)用v（v=1，2，…，V）表示，鏈路用e(e=1,2,…，E)表示，業(yè)務(wù)需求用d(d=1,2,…，D)表示

符號(hào)說明每一個(gè)業(yè)務(wù)需求d都指定了一些能發(fā)送流的路徑。指定的路徑用p=1,2,…pd表示，pd是路徑數(shù)目總和；這些路徑稱為備選路徑集。我們將業(yè)務(wù)需求d的路徑列表寫成下面的形式：，每條路徑連接需求d的源目節(jié)點(diǎn)需求d在路徑p上的數(shù)據(jù)流表示為：ye表示鏈路e上需要配置的容量路徑集合業(yè)務(wù)需求d=1只有一條路徑P11={2，4}，{2，4}的意思是這條路徑包含了標(biāo)號(hào)為2和4的兩條鏈路P1={P11}。業(yè)務(wù)需求d=2有兩條路徑，P21={5}，P22={3，4}。業(yè)務(wù)需求d=3也有兩條路徑，P31={1}，P32={2，3}。業(yè)務(wù)需求約束每一個(gè)業(yè)務(wù)需求的需求量需要通過它的路徑列表中各條路徑上的業(yè)務(wù)流來承載，我們寫出下面的幾個(gè)等式一般化的業(yè)務(wù)需求約束表示假設(shè)我們用矢量來表示指定給業(yè)務(wù)需求d的路徑P=1,2,…Pd上的業(yè)務(wù)流向量，則下面等式成立：對(duì)于每個(gè)業(yè)務(wù)需求d，我們可以寫出下面的等式：容量約束對(duì)于一條鏈路e,它上面的流向量之和不能超過其容量Ce或ye，從而有下面的約束：

鏈路和路徑的關(guān)系我們要得到鏈路負(fù)載，必須清楚鏈路和路徑之間的關(guān)系。他們之間的關(guān)系可以用鏈路-路徑（link-path）的關(guān)聯(lián)系數(shù)表示

一般化的鏈路容量表示在給定路徑列表和每條路徑所包含鏈路的情況下，是一個(gè)定值。因?yàn)檫@個(gè)系數(shù)的引進(jìn)，我們可以將鏈路e上的負(fù)載用下面的式子表示：從而容量約束可以寫成：目標(biāo)函數(shù)目標(biāo)函數(shù)可以寫成：也可以更一般化的寫成：

完整模型

一般化的完整模型

用Node-Link方式來描述Node-Link方式描述，主要包括兩大部分約束：

(1)業(yè)務(wù)路由和業(yè)務(wù)需求量約束

(2)鏈路容量約束

符號(hào)說明

：表示節(jié)點(diǎn)i和j間的業(yè)務(wù)在鏈路(m,n)上使用的容量。ymn:表示鏈路(m,n)上需要配置的容量。業(yè)務(wù)路由和業(yè)務(wù)需求量約束在Node-Link的描述中，每個(gè)業(yè)務(wù)都有這樣一組約束，比如針對(duì)節(jié)點(diǎn)1和節(jié)點(diǎn)2間的業(yè)務(wù)有下列約束：

流量守恒圖示節(jié)點(diǎn)1節(jié)點(diǎn)2節(jié)點(diǎn)3容量約束假設(shè)網(wǎng)絡(luò)中有2個(gè)業(yè)務(wù)，分別為<1,2>和<3,2>,那么針對(duì)鏈路（1，2）的容量約束可以寫成：

優(yōu)化目標(biāo)最小化是使用的鏈路代價(jià)一般化的Node-Link模型流量守恒約束思考Node-Link建模和Link-path建模各自有什么優(yōu)缺點(diǎn)？網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)已知條件優(yōu)化目標(biāo)網(wǎng)絡(luò)中節(jié)點(diǎn)間的業(yè)務(wù)需求hd網(wǎng)絡(luò)中每條鏈路e的單位成本網(wǎng)絡(luò)中每條鏈路的架設(shè)成本業(yè)務(wù)使用的總的網(wǎng)絡(luò)鏈路和總的網(wǎng)絡(luò)架設(shè)成最小.網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)（建模）采用Link-Path建模如下：練習(xí)題使用Node-Link的描述方式求解出節(jié)點(diǎn)1和6間的最短路徑，只需要寫出模型。本章主要內(nèi)容14.1網(wǎng)絡(luò)建?；痉椒?4.2建模技巧3.3建模方法和技巧1234UncapacitatedandCapacitatedproblemRoutingRestrictionsModularFlowsandLinksConvexCostUncapacitatedProblem（容量不受限的設(shè)計(jì)問題）已知條件優(yōu)化目標(biāo)網(wǎng)絡(luò)中節(jié)點(diǎn)間的業(yè)務(wù)需求hd網(wǎng)絡(luò)中每條鏈路e的代價(jià)πe網(wǎng)絡(luò)拓?fù)銰（V，E）通過設(shè)計(jì)業(yè)務(wù)路由和每條路由上的流量分配，使得每條鏈路上容量代價(jià)之和最少符號(hào)說明(Link-path)

需求約束LPFormulationforUncapacitatedProblem（Link-path）LPFormulationforUncapacitatedProblem（Link-path）S.t:符號(hào)說明(Node-link)LPFormulationforUncapacitatedProblem（Node-link）

Node-link和Link-path的比較變量數(shù)目約束個(gè)數(shù)Link-pathNode-linkCapacitatedProblem（容量受限的設(shè)計(jì)問題）已知條件優(yōu)化目標(biāo)網(wǎng)絡(luò)中節(jié)點(diǎn)間的業(yè)務(wù)需求hd網(wǎng)絡(luò)中每條鏈路e的代價(jià)πe網(wǎng)絡(luò)中每條鏈路e的容量Ce網(wǎng)絡(luò)拓?fù)銰（V，E）通過設(shè)計(jì)業(yè)務(wù)路由和每條路由上的流量分配，使得花費(fèi)的代價(jià)最少符號(hào)說明(Link-path)LPFormulationforCapacitatedProblem（Link-path）

思考題如果網(wǎng)絡(luò)中鏈路的容量是不足的，即上面的模型沒有可行解，那么現(xiàn)在要求求解每條鏈路上最少需要增加多少容量ze，應(yīng)該怎么建模？擴(kuò)容問題3.3建模方法和技巧1234UncapacitatedandCapacitatedproblemRoutingRestrictionsModularFlowsandLinksConvexCostRoutingRestrictions（路由限制）已知條件限制條件網(wǎng)絡(luò)中節(jié)點(diǎn)間的業(yè)務(wù)需求hd網(wǎng)絡(luò)中每條鏈路e的代價(jià)πe網(wǎng)絡(luò)中每條鏈路e的容量Ce網(wǎng)絡(luò)拓?fù)銰（V，E）要求每個(gè)業(yè)務(wù)只能在一條路徑上傳輸或者必須分在多條路徑上傳輸RoutingRestrictions（多路徑限制）網(wǎng)絡(luò)中由于流量均衡和生存性要求，所以要求業(yè)務(wù)必須分配到多條路徑上進(jìn)行傳輸要求傳輸?shù)穆窂綌?shù)目必須大于某個(gè)數(shù)值nLPFormulationforPathDiversityConstraint（Multi-path)RoutingRestrictions（單路徑約束）某些網(wǎng)絡(luò)中由于某些協(xié)議的要求，所以要求業(yè)務(wù)只能在一條路徑上進(jìn)行傳輸例如IP網(wǎng)絡(luò)中，為了避免IP包錯(cuò)序LPFormulationforPathDiversityConstraint（SinglePath)

Project3每個(gè)節(jié)點(diǎn)對(duì)間的流量為150M每條鏈路容量如圖中的鏈路所示每條鏈路的代價(jià)為1優(yōu)化目標(biāo)是最小化鏈路使用代價(jià)要求：使用link-path的建模方式，求解出最優(yōu)的業(yè)務(wù)路由和流量分配方案。Link-path方式中，需要為每個(gè)節(jié)點(diǎn)對(duì)找出3條不同的路徑（可以采用三條分離路徑）。1）要求節(jié)點(diǎn)對(duì)間的流量在三條備選路徑上等分流量2）如果業(yè)務(wù)選中了某條路徑，那么在這條路徑上分得的流不能小于50.3.3建模方法和技巧1234UncapacitatedandCapacitatedproblemRoutingRestrictionsModularFlowsandLinksConvexCost

ModularFlows在網(wǎng)絡(luò)中有時(shí)候業(yè)務(wù)的請(qǐng)求是某個(gè)數(shù)值的整數(shù)倍，例如在SDH網(wǎng)絡(luò)中，業(yè)務(wù)請(qǐng)求可能是STM-1（155Mbit/s)的整數(shù)倍.業(yè)務(wù)規(guī)劃時(shí)，不能將模塊化的業(yè)務(wù)流分成多條路徑來傳輸。LPFormulationforModularFlowsDemandmodular業(yè)務(wù)d的第p條路上分得的模塊流量數(shù)目業(yè)務(wù)需求d的模塊化數(shù)目

ModularLinks某些網(wǎng)絡(luò)中，一條鏈路的容量可以而多個(gè)模塊化粒度的容量（比如STM-1，STM-4）組合而成。規(guī)劃業(yè)務(wù)的時(shí)候需要選擇最小成本的組合LPFormulationforModularLinks第k中鏈路的模塊容量鏈路e上需要的第k種鏈路的數(shù)目3.3建模方法和技巧1234Un