网络优化问题建模.ppt

宽带光纤传输与通信网技术重点实验室
虞红芳
博士副教授
第四章网络优化介绍和建模
(Introduction work Optimization)
本章主要内容
1

2
建模技巧
一个思考题
将介绍两种典型的网络优化问题的描述方法:节点-链路(node-link)和链路-路径(link-path)。
Node-link建模和Link-path建模方法的特点和各自的优缺点。
一个例子
我们先考虑3节点的网络,每个节点都与其它两个节点相连,网络拓扑是一个三角形,如上图所示。节点是网络中路由器或交换设备的统称。
网络中的业务流量
业务需求量代表节点对之间的业务量或要求的带宽。
假设节点1和2之间的业务需求量为7个单位,节点1和3之间的业务需求量为7个单位,节点2和3之间的业务需求量为8个单位。我们假设业务需求和链路都是双向(无向)的,h用来表示业务需要量,则有:
h12=5, h13=7, h23=8。
这里,h的下标表示业务的两个起点和终点。
承载业务的路径
在上述三节点网络中,节点对间的业务量都可以通过两条路径来路由。如,节点1和2之间的业务需求量可以在路径1-2上直接路由至2,也可以通过节点3(1-3-2)进行路由。
每一条路径上应该分配多少流量由网络设计的优化目标决定。
流量传输的数学表示
如果我们用带下标的变量x来表示业务在每条路径上分配的流量,那么对于需求对<1,2>,我们可以得到如下等式:
这里,x的下标表示路由或路径;上面例子中的下标12和132分别表示路径1-2和1-3-2。同样地,需求节点对<1,3>和<2,3>,也可以分别写成下面的等式:
链路容量限制
通信网络中的任何链路都有容量上限,例子中的3条链路的容量分别表示为:
链路容量限制是指所有业务在某条链路上使用的容量总和要小于链路的实际容量,因此三条链路的容量限制可以表示为:
优化目标
网络优化中有很多优化目标,如最小化路由开销、最小化拥塞、流量均衡等。
假设我们的目标是使总路由开销最小。假定单位流量流经路径上每条链路的代价都设为1,那么总的路由开销就可以表示为:
完整的数学模型
这就是link-path的建模方式