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

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

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

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

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

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

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

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

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

一般化的鏈路容量表示在給定路徑列表和每條路徑所包含鏈路的情況下，是一個定值。因為這個系數(shù)的引進，我們可以將鏈路e上的負載用下面的式子表示：從而容量約束可以寫成：一般化的鏈路容量表示在給定路徑列表和每條路徑所包含鏈路目標函數(shù)目標函數(shù)可以寫成：也可以更一般化的寫成：

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

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

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

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

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

符號說明

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

業(yè)務(wù)路由和業(yè)務(wù)需求量約束在Node-Link的描述中，每個業(yè)流量守恒圖示節(jié)點1節(jié)點2節(jié)點3流量守恒圖示節(jié)點1節(jié)點2節(jié)點3容量約束假設(shè)網(wǎng)絡(luò)中有2個業(yè)務(wù)，分別為<1,2>和<3,2>,那么針對鏈路（1，2）的容量約束可以寫成：

容量約束假設(shè)網(wǎng)絡(luò)中有2個業(yè)務(wù)，分別為<1,2>和<3,優(yōu)化目標最小化是使用的鏈路代價優(yōu)化目標最小化是使用的鏈路代價一般化的Node-Link模型流量守恒約束一般化的Node-Link模型流量守恒約束思考Node-Link建模和Link-path建模各自有什么優(yōu)缺點？思考Node-Link建模和Link-path建模各自有網(wǎng)絡(luò)拓撲設(shè)計已知條件優(yōu)化目標網(wǎng)絡(luò)中節(jié)點間的業(yè)務(wù)需求hd網(wǎng)絡(luò)中每條鏈路e的單位成本網(wǎng)絡(luò)中每條鏈路的架設(shè)成本業(yè)務(wù)使用的總的網(wǎng)絡(luò)鏈路和總的網(wǎng)絡(luò)架設(shè)成最小.網(wǎng)絡(luò)拓撲設(shè)計已知條件優(yōu)化目標網(wǎng)絡(luò)中節(jié)點間的業(yè)務(wù)需求hd業(yè)務(wù)使網(wǎng)絡(luò)拓撲設(shè)計（建模）采用Link-Path建模如下：網(wǎng)絡(luò)拓撲設(shè)計（建模）采用Link-Path建模如下：練習(xí)題使用Node-Link的描述方式求解出節(jié)點1和6間的最短路徑，只需要寫出模型。練習(xí)題使用Node-Link的描述方式求解出節(jié)點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è)計問題）已知條件優(yōu)化目標網(wǎng)絡(luò)中節(jié)點間的業(yè)務(wù)需求hd網(wǎng)絡(luò)中每條鏈路e的代價πe網(wǎng)絡(luò)拓撲G（V，E）通過設(shè)計業(yè)務(wù)路由和每條路由上的流量分配，使得每條鏈路上容量代價之和最少UncapacitatedProblem（容量不受限的設(shè)計符號說明(Link-path)符號說明(Link-path)

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

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

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

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

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