学文网摘 要：网络逻辑拓扑的最优化是光网络的设计核心。针对分组业务的需要，要求光网络能够实时、动态调整网络的逻辑拓扑结构。对小规模的网络进行逻辑拓扑优化，可以用混合整数线性规划法（Mixed-Integer Linear Programming，MILP）解决。采用MILP算法对4节点网络进行逻辑拓扑优化设计仿真，首先设定约束条件并建立模型，以拥塞率最小化为目标函数做仿真实验，并对实验结果进行分析。
关键词：光网络；逻辑拓扑；拥塞率；MILP
中***分类号：TN915.02 文献标识码：B 文章编号：1004-373X(2008)02-134-03
An Algorithm of Logical Topology Design in Optical Network Based on MILP
WEI Zhengxia,GONG Jiamin,GAO Xinyu
(Xi′an University of Post and Telecommunications,Xi′an,710061,China)オ
Abstract：The logical topology of network optimization is the core of optical network design.To meeting the requirement of packet service,the optical network can adjust logical topology dynamically and in a real-time.MILP(Mixed Integer Linear Programming ) is a solution for logical topology optimization of the small-scale network.In this paper,an simulation design for logical topology optimization of four nodes network.A model has been established according to the constraint conditions,the simulation is based on the objective function which is minimizing the congestion rate.Then the experimental result has beenanalyzed.
Keywords：optical network;logical topology;congestion;MILPオ
1 引 言
随着信息时代的到来,各种通信业务的出现,人们对于通信带宽的要求越来越高。为了满足这些要求,波分复用技术(WDM)引起了人们的广泛重视。所谓波分复用技术,就是在一根光纤中利用不同的波长作为载波携带不同的数据流,每个数据流以Gbits的速率传输。采用波分复用技术可以大大增加光纤的传输能力。同时在光通信网中采用波长路由技术,他是以波长作为标识进行路由选择。利用WDM技术和波长路由技术,可以在已知物理拓扑中嵌入任意的逻辑拓扑。
Internet业务的爆炸性增长使光网络在业务提供方式上发生改变，从面向连接的、固定配置的电路业务方式转向面向无连接的、动态提供的分组业务，对光网络功能提出了新的、更高的要求。针对分组业务的面向无连接的特点，要求支持分组业务的光传送网能够实时、动态地调整网络的逻辑拓扑结构，实现资源的最佳利用，以适应分组业务的自相似性、突发性等特点。设计核心是最优化网络逻辑拓扑，改善网络性能。
2 物理拓扑和逻辑拓扑
网络的物理拓扑即网络节点的物理连接关系，在组成上，他是网络节点与光缆链路的集合。物理拓扑与光缆线路的敷设路由直接相关，通常不能随业务改变而改变。逻辑拓扑指的是网络节点之间业务的分布情况，由一系列端到端的光通道构成的拓扑结构，即在物理拓扑基础上负责分层路由的光层逻辑结构。他与物理拓扑有紧密关系，如***1所示。逻辑拓扑可以由软件控制比较容易改变。
逻辑拓扑和物理拓扑的区别有：
（1） 物理拓扑是面向节点的物理连接，逻辑拓扑是面向节点的逻辑连接；
（2） 物理拓扑***的顶点是路由节点，边是节点间的光纤链路。而逻辑拓扑***的顶点是网络的各个节点（指路由节点结合其对应的接入节点）。逻辑拓扑***的边是节点间的光通道，通常是有向的。光通道是光网络中由一条或多条链路构成的端到端的透明信息通道。当光网络不具备波长转换功能时，光通道必须满足波长一致性条件（即一条通道上的波长处处不变）。若网络具有波长转换功能，此时的逻辑拓扑问题类似于ATM网络中的虚通路分配问题；
（3） 物理拓扑中节点的物理度由与该节点有链路连接的节点数目决定，而逻辑拓扑中节点的逻辑度由该节点的光收发机数目决定；
（4） 物理拓扑设计是在保障网络传输性能的前提下，根据节点位置和可用部件选择建设费用和综合效益最适合的方案，逻辑拓扑设计是在物理拓扑基础上考虑节点的业务分布情况，建立信息传送性能达到最佳的方案。
光网络的逻辑拓扑与波长分配方案相关，不同的波长分配方案可以形成不同的逻辑拓扑。每根光纤上的最***长数W，所以共享一条光纤链路的光通道数不得超过WА4釉唇诘愕剿藿诘憧赡苡梢惶豕馔ǖ乐苯恿接，一条光通道所提供的路由是单跳路由。但是因为一根光纤上的最***长数有限，且网络不一定是全连通的，所以不可能所有节点对之间都有一条光通道连接，源宿节点对之间可能有多条光通道顺序连接，这时称为多跳路由。可见在逻辑拓扑的支持下，分组数据由波长一致的光通道传至宿节点或尽可能远的地方，这里不考虑波长变换；如果一条光通道不能把分组数据传输至宿节点，则需要多跳路由传输，需要多条光通道。
3 逻辑拓扑的优化
网络的逻辑拓扑设计优化问题是充分利用有限数量的光收发机和每根光纤的可用波长资源，确定最佳的网络拓扑结构和光路径选路方案，使网络的性能指标得到优化。在节点的收发机和波长数目受到限制的前提条件下，这里感兴趣的问题是怎样最小化端到端的分组延迟，或考虑尽可能地提高网络的吞吐量，以满足业务增长的需要。因此逻辑拓扑的优化设计有1个或2个可能的目标函数：
（1） 对给定的业务矩阵最小化网络范围的平均分组延迟，即目标函数是最小化平均分组延迟；
（2） 最大化业务规模的扩展因素，即最小化网络拥塞，即Иmin fmax=max fij,ij ∈V，其中V是给定网络的所有节点的集合。拥塞控制与业务的路由选择紧密相关，不佳的选径策略是导致网络拥塞增加的主要原因。最小化拥塞指标可以提高网络的吞吐能力，从而更好地适应未来业务增长的需要。
逻辑拓扑的优化设计需要从网络的所有逻辑拓扑实现方案中选择使分组业务传送性能最佳的方案，决定了这类问题复杂的组合优化过程。对于小规模的网络，可以用混合整数线性规划法（Mixed-Integer Linear Programming，MILP）解决；在大规模网络的优化设计中，通常采用启发式算法。本文采用MILP算法对4节点网络进行逻辑拓扑优化设计仿真，并对仿真实验结果进行分析。
4 MILP模型描述
4.1 已知条件
(1) 光纤网络的网络物理拓扑用无向***Gp=(V,Ep)表示；V表示顶点集合；Ep代表边集，“无向”的含义是物理拓扑中每条链路是双向的，链路可以带有表征距离和延时的权重。
(2) 每根光纤上的最***长数W。
(3) 业务需求分布用表用一个N×N的矩阵描述，这里N为网络节点总数；第(i,j)项矩阵元素代表从节点i到j的平均业务流量(注意业务流可以是不对称的)。为简便起见，实验中采用的业务流是均匀分布U(0，1)。
(4) 网络节点的收发机数目，决定网络的逻辑度。
仿真实验中用到的参数：
N：物理网络的节点数；
W：每根光纤的最***长数；
ts,d：节点s到节点d的平均流量；
hpi,j：节点i到节点j的光通道的最大物理跳数；
hi,j：逻辑拓扑中节点i到节点j的最大逻辑跳数；
fi,j：节点i到节点j的光通道上的总流量；
f(s,d)i,j ：起点终点分别为节点i,j光通道上源宿节点对s,d间的流量；
pij：光通道标识符，若为1，表示从节点i到节点j存在一条光通道；否则为0。
4.2 约束条件
5 仿真结果及分析
由于环网是目前城域网和局域网所采用的主要拓扑结构，他是光网络实际应用时最先采用的网络拓扑结构，因此在实验中设计4节点简单环形网的逻辑拓扑。传输模式是均匀分布U(0,1)，无波长转换器，目标函数是使拥塞率最小，求解方程组，使得拥塞率fmaxё钚。本文所采用的算法忽略时延约束，只考虑逻辑度约束、流量约束、波长约束、跳转数约束，使约束条件简化。仿真数值结果如表1所示。求得的逻辑拓扑如***2所示。
从仿真结果中可以看出当每个网络节点收发器数目由1个增加到2个时，拥塞率显著减小，由3.333 5减小到1.199。而通常情况下，节点的发射器数目称为节点的逻辑输出度，节点的接受器数目称为节点的逻辑输入度，当节点发射器和节点接收器数目相等时，称为逻辑度。可见增加网络的逻辑度可以明显地缓解的网络拥塞现象。同时，当逻辑度增加为2时，网络的逻辑拓扑变为双环形结构，光通道数增加为8。
当网络节点收发器数目（即节点逻辑度）和最大跳转次数一定时，增加最***长数，从表1中可以看出，网络拥塞率进一步减小，如表第1行和第2行拥塞率由3.333 5减小到2.637 7。同样，当网络节点数目和最***长数一定时，增加最大跳转次数，网络拥塞率也减小，如表第1行和第3行拥塞率由3.333 5减小到2.793 1。
从仿真结果还可以看出网络节点的逻辑度、最***长数、最大跳转次数3个参量，对拥塞率的影响程度由强到弱依次为节点逻辑度、最***长数、最大跳转次数。但是网络节点逻辑度增加需要增加网络节点收发器数目，增加网络成本，在实际的网络设计中网络成本是不可忽视的主要因素。实际应用中需要综合考虑各方面因素，选择性价比高的方案。
6 结 语
文中利用MILP模型算法建立逻辑拓扑，简化约束条件，不考虑延时条件，考虑最优路由优先的情况下，以最小拥塞率为目标设计逻辑拓扑，对4节点的简单环形网络进行仿真实验。
试验结果表明MILP模型算法可以很好地得到逻辑拓扑，并且可以看出逻辑度、最***长数和最大跳转次数对拥塞率的影响。从MILP模型可以看出方程组变量个数随着网络节点个数增加而迅速增加，即这种方法计算的复杂性随着网络规模的扩大而增加，因此这种方法只适用于小规模的网络。
参 考 文 献
［1］龚倩，徐荣，张民,等.光网络的组网与优化设计［M］.北京：北京邮电大学出版社，2002.
［2］杨淑雯.全光光纤通信网［M］.北京：科学出版社，2004.
［3］Liu Fengqing,Zeng Qingji,Zhu Xu,et al.Virtual Topology Reconfiguration in WDM Optical Networks［J］.光子学报:英文版，2003,32(10):1 116-1 180.
［4］Rajiv Ramaswami,Kumar N Sivarajan.Design of Logical Topologies for Wavelength-Routed All-Optical Networks［A］.Proceeding of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies,1995:1 316-1 325.
［5］张杰，顾畹仪，李国瑞，等.光传送网的最优虚拓扑设计原理［J］.现代有线传输，1999,12(4):29-32.
注：本文中所涉及到的***表、注解、公式等内容请以PDF格式阅读原文。
转载请注明出处学文网 » 基于MILP模型的光网络逻辑拓扑优化算法