一种多约束服务质量路由新方法

一种多约束服务质量路由新方法

1多约束路由算法为了提供高质量的服务，下一代网络面临着重大挑战，需要提供服务质量和带宽保障。因此，从末端到端等的ip服务质量（qui）是研究的重点。QoSR要求同时考虑多个约束参数,因此QoSR问题又称多约束路径选择问题.寻找一条同时满足多种约束条件的路径具有NP完全的复杂度.因此许多学者试采用启发式算法进行了求解Jaffe算法首先构造线性函数把多约束参数化为单一约束值.TAMCRA算法提出基于通过非线性花费函数计算最短路径,并根据文中从网络约束参数的性质、TAMCRA算法中提出的非线性花费函数、Dijkstra算法不能在非线性花费函数下求解最短路径这三个特点出发,提出一种单播多约束路由算法并进行分析和总结,针对网络中难以解决的加性约束(乘性约束可取对数化简为加性约束)及非线性花费函数是要求先计算出一条完整的源到目的节点路径才能精确求解等问题,设计了该算法,通过仿真分析论证该算法的可行性.22.1多约束路径qos请求为研究路由算法,将网络中的交换节点、链路、链路属性抽象为图,用有向图1多约束路径.假定一个QoS请求的多个约束条件为2非性性花费函数这里2.2源节点到目的节点根据实际网络的拓扑特点及多个约束参数的特征,设计先计算源目的节点间的从最小跳的路径集,在进行多约束计算时可利用非线性函数进行优化.具体算法规则如下:(1)连接分组的初始化设网络(1)=[(1)=[……(1)=[(1)](1)=[式中,分组中元素的初始表达式按照如下定义得到:·当·当节点·当节点(2)连接分组运算及路径计算公式逻辑代数表示路径的规定:用“·”表示“与”逻辑运算关系,用“+”表示“或”逻辑运算关系.“与”逻辑又称为逻辑乘积,多个变量符号的逻辑乘积,表示路径是由这些变量符号代表的链路串联构成的.“或”逻辑又称为逻辑和.在“与或”逻辑表达方式的路径表达式中,有多少个逻辑乘积项求和,就表示同时存在多少条路径.下面求从源节点(求各中间节点到目的节点([((…((2)通过上述两公式来回迭代计算即可求出依次源节点到目的节点串联1～3多约束路径计算步骤从以上算法中可以得出在具体基于新计算方法的多约束路径计算步骤如下:(1)初始化=2,…,(2)(3)根据式(2)计算出(4)将上一步求出的4仿真生成链路和算法仿真从仿真上看,该算法根据TAMCRA/SAMCRAM算法提出的非线性函数可以精确计算出最优路径,从仿真分析得出满足加性约束的路径一般在较短的路径中,而该算法就是从最短链路开始计算,所以根据用户输入的链路约束控制要计算的链路的长度,人为可以控制计算时间.在呼叫次数逐步增加的情况下,对不同网络进行验证时,发现通常满足约束中最优的链路较少的路径中.网络模型采用模拟现实网络的Waxman算法随机产生的拓扑图,连接度数由算法进行控制,上述仿真平均连接度限制在4以内.链路约束根据设置范围随机产生.该算法能准确计算优化路径并且时间复杂度合理.算法时间复杂度方面,假设在网络5仿真结果分析算法思想基于最小跳的计算思路,算法采用非线性花费函数优化后,找到可行路径即退出运算.为了更好地验证算法的性能,第一方面从求满足多约束路径的平均运行时间度上进行比较,第二方面从求最优路径的成功率仿真上分析.为了更好地验证算法的性能,对该算法与HMCOP算法进行对比分析.具体的仿真采用Waxman算法的随机生成图,仿真图节点数分别为30～50,50～70.每个节点数网络仿真次数200.链路状态产生范围1～10请求范围30～40.图1为30～50个节点下平均运行时间的比较,图2为50～70个节点下平均运行时间的比较.为进一步分析算法的性能,在节点数为50～70的网络下,每个网络运行5000次的情况下