网络优化问题建模.课件.ppt

1、宽带光纤传输与通信网技术重点实验室虞红芳虞红芳博士博士 副教授副教授14.1网络建模基本方法网络建模基本方法24.2 建模技巧建模技巧我们先考虑我们先考虑3 3节点的网络，每个节点都与其它两个节点相连，节点的网络，每个节点都与其它两个节点相连，网络拓扑是一个三角形，如上图所示。节点是网络中路由器网络拓扑是一个三角形，如上图所示。节点是网络中路由器或交换设备的统称或交换设备的统称。12132125xxh13123137xxh23213238xxh12,13,23ccc121232131210 xxxc132132131310 xxxc132123232315xxxc121323123213132

2、222Fxxxxxx121323123213132min222Fxxxxxx1 21 3 21 31 2 32 32 1 31 21 2 32 1 31 3 21 32 1 31 3 21 2 32 31 21 32 31 2 32 1 31 3 20. :5781 01 01 5,s txxxxxxxxxxxxxxxxxxxxx这就是link-path的建模方式 上图给出的三个节点的网络中，我们分别用两条单向（有上图给出的三个节点的网络中，我们分别用两条单向（有向）链路替代每一条无向（双向）链路，例如，无向链路向）链路替代每一条无向（双向）链路，例如，无向链路1-2用两条有向链路来表示：用两

3、条有向链路来表示：12，21。我们假设业务需求量我们假设业务需求量h12是开始于节点是开始于节点1，结束于节点，结束于节点2 。Xmn,ij:表示节点表示节点i j的业务量在链路的业务量在链路m n上使用的容量上使用的容量w 如果一个节点不是业务需求对的源目节点，我如果一个节点不是业务需求对的源目节点，我们把这样的节点叫做们把这样的节点叫做中间节点中间节点。从中间节点上从中间节点上看这些链路流量，会发现进来的链路总流量等看这些链路流量，会发现进来的链路总流量等于出去的链路总流量，这个叫做于出去的链路总流量，这个叫做流量守恒定理流量守恒定理。w 如果节点是业务需求对的如果节点是业务需求对的源节点

4、源节点，出去的流量出去的流量之和减去进来的流量和等于业务需求量之和减去进来的流量和等于业务需求量。w 如果节点是业务需求对的如果节点是业务需求对的目的节点目的节点，进来的总进来的总流量减去出去的流量之和也必等于业务需求量。流量减去出去的流量之和也必等于业务需求量。12,1213,1221,1231,1212xxxxh13,1223,1231,1232,120 xxxx12,1232,1221,1223,1212xxxxh源节点源节点中间节点中间节点目的节点目的节点x31,12x21,12x31,12x23,12x23,12x21,1212,1221,1213,1231,1223,1232,12

5、12,1213,1221,1231,121213,1223,1231,1232,1212,1232,1221,1223,1212min0 xxxxxxxxxxhxxxxxxxxh如果网络中还同时有如果网络中还同时有1 1到到3 3和和2 2到到3 3的业的业务，那么这个模型应该怎么写？务，那么这个模型应该怎么写？这就是这就是node-node-linklink的模型的模型右图的网络有四个节点，五条无右图的网络有四个节点，五条无向链路，向链路，V=4V=4，E=5E=5。图上面部。图上面部分表示有三个无向业务需求对，分表示有三个无向业务需求对，D=3D=3。节点用节点用v v（v=1v=1，2

6、2，V V）表示，）表示，链路用链路用e(e=1,2,e(e=1,2,，E)E)表示，业务表示，业务需求用需求用d (d=1,2,d (d=1,2,，D)D)表示表示 12(,)dddddPPPPP(1,2,)dpdxpP业务需求业务需求d=1d=1只有一条路径只有一条路径P P1111=2=2，44，22，44的意思是这条路径包含了标号的意思是这条路径包含了标号为为2 2和和4 4的两条链路的两条链路P P1 1=P=P1111 。业务需求业务需求d=2d=2有两条路径，有两条路径，P P2121=5=5，P P2222=3=3，44。业务需求业务需求d=3d=3也有两条路径，也有两条路径，

7、P P3131=1=1，P P3232=2=2，33。1121223132152010 xxxxx12(,)dddddPxxxx12ddddPdxxxh1,1,2,dPdpdpxh dD311113222232311224215xyxxyxxyxxyxyedp1(d)0(d)edpepep如果 属于需求 的路径如果 不属于需求 的路径edp11dPDedpdpdpx,1,2,edpdpedpxy eE11223344551234523Fyyyyyyyyyy1EeeeeeeFyyeeeFy,1,2,dpdpxh dD,1,2,edpdpedpxy eE0,0 xyijmnx12121212123

8、2212312xxxxh12121212313213230 xxxx121212121232212312xxxxh节点节点1节点节点2节点节点31232121212xxy121221211313313123233232minyyyyyy最小化是使用的链路代价最小化是使用的链路代价(, )( , )(, )(, )( ,)( , )( , ),min,0,mnmnm nEijijininiji nEm iEijijmnnmm nEn mEijijnjjnijn jEj nEijmnmni jDyxxhi jDxxi jD mijxxhi jDxy 流量守恒约束流量守恒约束已知条件已知条件优化目标

9、优化目标网络中节点间的业务需求网络中节点间的业务需求h hd d网络中每条链路网络中每条链路e的单位成本的单位成本网络中每条链路的架设成本网络中每条链路的架设成本业务使用的总的网络链路和总的网络架设业务使用的总的网络链路和总的网络架设成最小成最小. .min : 0,0eeeeeedpdpedpdpedpeeFyk usubjecttoxhxyyC uxy 使用使用Node-LinkNode-Link的描述方式求解出节点的描述方式求解出节点1 1和和6 6间的最短路径，只需要写出模型。间的最短路径，只需要写出模型。14.1网络建模基本方法网络建模基本方法24.2 建模技巧建模技巧3.3 3.3

10、 建模方法和技巧建模方法和技巧1234Uncapacitated and Capacitated problem Routing Restrictions Modular Flows and Links Convex Cost Uncapacitated ProblemUncapacitated Problem（容量不受（容量不受限的设计问题）限的设计问题）已知条件已知条件优化目标优化目标网络中节点间的业务需求网络中节点间的业务需求h hd d网络中每条链路网络中每条链路e的代价的代价 e e网络拓扑网络拓扑G G（V V，E E）通过设计业务路由和每条路由上的流量分通过设计业务路由和每条路由

11、上的流量分配，使得每条链路上容量代价之和最少配，使得每条链路上容量代价之和最少需求约束LP Formulation for Uncapacitated ProblemLP Formulation for Uncapacitated Problem（Link-pathLink-path） LP Formulation for Uncapacitated Problem LP Formulation for Uncapacitated Problem（Link-pathLink-path）,1,2,.dpdpxhdDmineedpdpdpeedpdpdpedpdpedpFxxL x S.t:LP

12、Formulation for Uncapacitated LP Formulation for Uncapacitated ProblemProblem（Node-linkNode-link）21(1)()2PDEP V VkvO V21(1)()2DEV Vk VO V311(1)()22EDEk VV Vk VO V231(1)(1)()2D VEVVV VO VCapacitated ProblemCapacitated Problem（容量受限的（容量受限的设计问题）设计问题）已知条件已知条件优化目标优化目标网络中节点间的业务需求网络中节点间的业务需求h hd d网络中每条链路网络中

13、每条链路e的代价的代价 e e网络中每条链路网络中每条链路e e的容量的容量C Ce e网络拓扑网络拓扑G G（V V，E E）通过设计业务路由和每条路由上的流量分通过设计业务路由和每条路由上的流量分配，使得花费的代价最少配，使得花费的代价最少LP Formulation for Capacitated ProblemLP Formulation for Capacitated Problem（Link-Link-pathpath）3.3 3.3 建模方法和技巧建模方法和技巧1234Uncapacitated and Capacitated problem Routing Restrictio

14、ns Modular Flows and Links Convex Cost Routing RestrictionsRouting Restrictions（路由限制）（路由限制）已知条件已知条件限制条件限制条件网络中节点间的业务需求网络中节点间的业务需求h hd d网络中每条链路网络中每条链路e的代价的代价 e e网络中每条链路网络中每条链路e e的容量的容量C Ce e网络拓扑网络拓扑G G（V V，E E）要求每个业务只能在要求每个业务只能在一条一条路径上传输或者路径上传输或者必须分在多条路径上传输必须分在多条路径上传输Routing RestrictionsRouting Restr

15、ictions（多路径限制）（多路径限制）LP Formulation for Path Diversity LP Formulation for Path Diversity ConstraintConstraint（Multi-path)Multi-path)Routing RestrictionsRouting Restrictions（单路径约束）（单路径约束）LP Formulation for Path Diversity LP Formulation for Path Diversity ConstraintConstraint（Single Path)Single Path)m

16、in, 1,.,1,.,1, 1,.,1,2,eedpdpdddppedpdpedpFyxu hdD pPudDxCeE w每个节点对间的流量为150Mw每条链路容量如图中的链路所示w每条链路的代价为1w优化目标是最小化链路使用代价w要求：w使用link-path的建模方式，求解出最优的业务路由和流量分配方案。wLink-path方式中，需要为每个节点对找出3条不同的路径（可以采用三条分离路径）。1）要求节点对间的流量在三条备选路径上等分流量2）如果业务选中了某条路径，那么在这条路径上分得的流不能小于50.3.3 3.3 建模方法和技巧建模方法和技巧1234Uncapacitated and

17、Capacitated problem Routing Restrictions Modular Flows and Links Convex Cost LP Formulation for Modular FlowsLP Formulation for Modular Flowsmin, 1,.,1,., 1,.,1,2,eedpddpddpddpedpdpedpFyxL ndD pPxL HdDxCeE Demand modular业务d的第p条路上分得的模块流量数目业务需求d的模块化数目LP Formulation for Modular LinksLP Formulation for Modular Linksmin, 1,.,1,2,kekekdpdpedpdpkekdpkFM yxhdDxM yeE 第第k k中链路的中链路的模块容量模块容量链路链路e e上需要上需要的第的第k k种链路种链路的数目的数目3.3 3.3 建模方法和技巧建模方法和技巧1234Uncapacitated and Capacitated problem Routing Restrictions Modular Flows and Links Convex Cost 1212( )(1) ()(1)af za f zf aza z其中，01ae1min, 0y1eeeFcy