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

寬帶光纖傳輸與通信網(wǎng)技術(shù)重點(diǎn)實(shí)驗(yàn)室虞紅芳博士副教授第四章網(wǎng)絡(luò)優(yōu)化介紹和建模（IntroductiontoNetworkOptimization）寬帶光纖傳輸與通信網(wǎng)技術(shù)重點(diǎn)實(shí)驗(yàn)室虞紅芳第四章網(wǎng)絡(luò)優(yōu)化介紹本章主要內(nèi)容14.1網(wǎng)絡(luò)建?；痉椒?4.2建模技巧本章主要內(nèi)容14.1網(wǎng)絡(luò)建?；痉椒?4.2建模技一個(gè)思考題將介紹兩種典型的網(wǎng)絡(luò)優(yōu)化問(wèn)題的描述方法：節(jié)點(diǎn)－鏈路（node-link）和鏈路－路徑（link-path）。Node-link建模和Link-path建模方法的特點(diǎn)和各自的優(yōu)缺點(diǎn)。一個(gè)思考題將介紹兩種典型的網(wǎng)絡(luò)優(yōu)化問(wè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)稱。一個(gè)例子我們先考慮3節(jié)點(diǎn)的網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)都與其它兩個(gè)節(jié)網(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ù)需求和鏈路都是雙向（無(wú)向）的，h用來(lái)表示業(yè)務(wù)需要量，則有：h12=5,h13=7,h23=8。這里，h的下標(biāo)表示業(yè)務(wù)的兩個(gè)起點(diǎn)和終點(diǎn)。網(wǎng)絡(luò)中的業(yè)務(wù)流量業(yè)務(wù)需求量代表節(jié)點(diǎn)對(duì)之間的業(yè)務(wù)量或要求承載業(yè)務(wù)的路徑在上述三節(jié)點(diǎn)網(wǎng)絡(luò)中，節(jié)點(diǎn)對(duì)間的業(yè)務(wù)量都可以通過(guò)兩條路徑來(lái)路由。如，節(jié)點(diǎn)1和2之間的業(yè)務(wù)需求量可以在路徑1－2上直接路由至2，也可以通過(guò)節(jié)點(diǎn)3（1－3－2）進(jìn)行路由。每一條路徑上應(yīng)該分配多少流量由網(wǎng)絡(luò)設(shè)計(jì)的優(yōu)化目標(biāo)決定。承載業(yè)務(wù)的路徑在上述三節(jié)點(diǎn)網(wǎng)絡(luò)中，節(jié)點(diǎn)對(duì)間的業(yè)務(wù)量都可流量傳輸?shù)臄?shù)學(xué)表示如果我們用帶下標(biāo)的變量x來(lái)表示業(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＞，也可以分別寫成下面的等式：流量傳輸?shù)臄?shù)學(xué)表示如果我們用帶下標(biāo)的變量x來(lái)表示業(yè)務(wù)在鏈路容量限制通信網(wǎng)絡(luò)中的任何鏈路都有容量上限，例子中的3條鏈路的容量分別表示為：鏈路容量限制是指所有業(yè)務(wù)在某條鏈路上使用的容量總和要小于鏈路的實(shí)際容量，因此三條鏈路的容量限制可以表示為：鏈路容量限制通信網(wǎng)絡(luò)中的任何鏈路都有容量上限，例子中的3條優(yōu)化目標(biāo)網(wǎng)絡(luò)優(yōu)化中有很多優(yōu)化目標(biāo)，如最小化路由開銷、最小化擁塞、流量均衡等。假設(shè)我們的目標(biāo)是使總路由開銷最小。假定單位流量流經(jīng)路徑上每條鏈路的代價(jià)都設(shè)為1，那么總的路由開銷就可以表示為：優(yōu)化目標(biāo)網(wǎng)絡(luò)優(yōu)化中有很多優(yōu)化目標(biāo)，如最小化路由開銷完整的數(shù)學(xué)模型這就是link-path的建模方式完整的數(shù)學(xué)模型這就是link-path的建模方式從另外一個(gè)方面來(lái)思考同一個(gè)問(wèn)題Link-path模型中，承載每個(gè)業(yè)務(wù)需求的路徑是給定的，模型需要求解的是每個(gè)業(yè)務(wù)在給定的每條路徑上分配多少流量。那對(duì)于一個(gè)業(yè)務(wù)而言，我們能不能把這個(gè)業(yè)務(wù)在每條鏈路上使用的網(wǎng)絡(luò)流量作為一個(gè)變量來(lái)求解呢？從另外一個(gè)方面來(lái)思考同一個(gè)問(wèn)題Link-path模型中，承載為什么要這樣思考？如果我們知道一個(gè)業(yè)務(wù)在網(wǎng)絡(luò)中的每條鏈路上使用了多少流量，那么意味著什么呢？意味著這個(gè)業(yè)務(wù)在網(wǎng)絡(luò)中怎么路由就知道了。那么我們?cè)趺磥?lái)描述一個(gè)業(yè)務(wù)在每條鏈路上使用的流量呢？他們應(yīng)該滿足什么約束呢？為什么要這樣思考？如果我們知道一個(gè)業(yè)務(wù)在網(wǎng)絡(luò)中的每條鏈網(wǎng)絡(luò)模型和符號(hào)

上圖給出的三個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，我們分別用兩條單向（有向）鏈路替代每一條無(wú)向（雙向）鏈路，例如，無(wú)向鏈路1-2用兩條有向鏈路來(lái)表示：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上使用的容量網(wǎng)絡(luò)模型和符號(hào)上圖給出的三個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，我們流量守恒如果一個(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)來(lái)的鏈路總流量等于出去的鏈路總流量，這個(gè)叫做流量守恒定理。如果節(jié)點(diǎn)是業(yè)務(wù)需求對(duì)的源節(jié)點(diǎn)，出去的流量之和減去進(jìn)來(lái)的流量和等于業(yè)務(wù)需求量。如果節(jié)點(diǎn)是業(yè)務(wù)需求對(duì)的目的節(jié)點(diǎn)，進(jìn)來(lái)的總流量減去出去的流量之和也必等于業(yè)務(wù)需求量。

流量守恒如果一個(gè)節(jié)點(diǎn)不是業(yè)務(wù)需求對(duì)的源目節(jié)點(diǎn)，我們把這

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

例子右圖的網(wǎng)絡(luò)有四個(gè)節(jié)點(diǎn)，五條無(wú)向鏈路，V=4，E=符號(hào)說(shuō)明每一個(gè)業(yè)務(wù)需求d都指定了一些能發(fā)送流的路徑。指定的路徑用p=1,2,…pd表示，pd是路徑數(shù)目總和；這些路徑稱為備選路徑集。我們將業(yè)務(wù)需求d的路徑列表寫成下面的形式：，每條路徑連接需求d的源目節(jié)點(diǎn)需求d在路徑p上的數(shù)據(jù)流表示為：ye表示鏈路e上需要配置的容量符號(hào)說(shuō)明每一個(gè)業(yè)務(wù)需求d都指定了一些能發(fā)送流的路徑。指定的路徑集合業(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ù)需求d=1只有一條路徑P11={2，4}，業(yè)務(wù)需求約束每一個(gè)業(yè)務(wù)需求的需求量需要通過(guò)它的路徑列表中各條路徑上的業(yè)務(wù)流來(lái)承載，我們寫出下面的幾個(gè)等式業(yè)務(wù)需求約束每一個(gè)業(yè)務(wù)需求的需求量需要通過(guò)它的路徑列表中各一般化的業(yè)務(wù)需求約束表示假設(shè)我們用矢量來(lái)表示指定給業(yè)務(wù)需求d的路徑P=1,2,…Pd上的業(yè)務(wù)流向量，則下面等式成立：對(duì)于每個(gè)業(yè)務(wù)需求d，我們可以寫出下面的等式：一般化的業(yè)務(wù)需求約束表示假設(shè)我們用矢量容量約束對(duì)于一條鏈路e,它上面的流向量之和不能超過(guò)其容量Ce或ye，從而有下面的約束：

容量約束對(duì)于一條鏈路e,它上面的流向量之和不能超過(guò)其容量Ce鏈路和路徑的關(guān)系我們要得到鏈路負(fù)載，必須清楚鏈路和路徑之間的關(guān)系。他們之間的關(guān)系可以用鏈路-路徑（link-path）的關(guān)聯(lián)系數(shù)表示

鏈路和路徑的關(guān)系我們要得到鏈路負(fù)載，必須清楚鏈路和路

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

目標(biāo)函數(shù)目標(biāo)函數(shù)可以寫成：完整模型完整模型

一般化的完整模型一般化的完整模型

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

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

(2)鏈路容量約束用Node-Link方式來(lái)描述Node-Link方式描

符號(hào)說(shuō)明

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

業(yè)務(wù)路由和業(yè)務(wù)需求量約束在Node-Link的描述中，每個(gè)業(yè)流量守恒圖示節(jié)點(diǎn)1節(jié)點(diǎn)2節(jié)點(diǎn)3流量守恒圖示節(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）的容量約束可以寫成：

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

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

Node-link和Link-path的比較變量數(shù)目約束個(gè)數(shù)Link-pathNode-linkNode-link和Link-path的比較變量數(shù)目約束CapacitatedProblem（容量受限的設(shè)計(jì)問(wèn)題）已知條件優(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）通過(guò)設(shè)計(jì)業(yè)務(wù)路由和每條路由上的流量分配，使得花費(fèi)的代價(jià)最少CapacitatedProblem（容量受限的設(shè)計(jì)問(wèn)題）符號(hào)說(shuō)明(Link-path)符號(hào)說(shuō)明(Link-path)LPFormulationforCapacitatedProblem（Link-path）

LPFormulationforCapacitated思考題如果網(wǎng)絡(luò)中鏈路的容量是不足的，即上面的模型沒有可行解，那么現(xiàn)在要求求解每條鏈路上最少需要增加多少容量ze，應(yīng)該怎么建模？思考題如果網(wǎng)絡(luò)中鏈路的容量是不足的，即上面的模型沒擴(kuò)容問(wèn)題擴(kuò)容問(wèn)題3.3建模方法和技巧1234UncapacitatedandCapacitatedproblemRoutingRestrictionsModularFlowsandLinksConvexCost3.3建模方法和技巧1234UncapacitatedaRoutingRestrictions（路由限制）已知條件限制條件網(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（路由限制）已知條件RoutingRestrictions（多路徑限制）網(wǎng)絡(luò)中由于流量均衡和生存性要求，所以要求業(yè)務(wù)必須分配到多條路徑上進(jìn)行傳輸要求傳輸?shù)穆窂綌?shù)目必須大于某個(gè)數(shù)值nRoutingRestrictions（多路徑限制）網(wǎng)絡(luò)中LPFormulationforPathDiversityConstraint（Multi-path)LPFormulationforPathDiversRoutingRestrictions（單路徑約束）某些網(wǎng)絡(luò)中由于某些協(xié)議的要求，所以要求業(yè)務(wù)只能在一條路徑上進(jìn)行傳輸例如IP網(wǎng)絡(luò)中，為了避免IP包錯(cuò)序RoutingRestrictions（單路徑約束）某些網(wǎng)LPFormulationforPathDiversityConstraint（SinglePath)LPFormulationforPathDivers

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.Project33.3建模方法和技巧1234UncapacitatedandCapacitatedproblemRoutingRestrictionsModularFlowsandLinksConvexCost3.3建模方法和技巧1234Uncapacitateda

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ù)流分成多條路徑來(lái)傳輸。ModularFlows在網(wǎng)絡(luò)中有時(shí)候業(yè)務(wù)的請(qǐng)求是某