基于线性能量函数的服务质量路由预计算算法

摘要

基于线性能量函数的服务质量路由预计算算法属于具有多个服务质量参数的服务质量路由技术领域，其特征在于：它是以采用线性能量函数把多个服务质量(QoS)参数转换成单一能量值为基础的。它先使用多个线性能量函数为每条链路计算出一组能量值，再据此以源节点为树根建立最短路径树，使得从根节点到达任意节点沿着该树的路径具有最小能量值，然后根据最短路径树计算出部分QoS路由表，最后把所有能量函数的这些部分QoS路由表组合在一起形成一个完整的QoS路由表。当能量函数的个数在7～10个之间时，其失效概率已经非常小了。

主权项

1.基于线性能量函数的服务质量路由预计算算法其特征在于：它是借助于路由器硬件平台以采用线性能量函数把多个服务质量(QoS)参数转换成单一的能量值为基础的；它先使用多个线性能量函数为每条链路计算出一组能量值，进而根据这些能量值以源节点为树根，建立最短路径树，使得从树根节点到达任意节点沿着该树的路径具有最小能量值，再根据这些最短能量树计算出部分QoS路由表，最后把所有能量函数的这些部分QoS路由表组合在一起，形成一个完整的QoS路由表，它依次含有以下步骤：(1)初始化输入：每个链路具有k个QoS参数的拓扑图G、根节点s、目标节点t；能量系数a＝(a1，a2，…，ak)，使能量系数分量的个数等于QoS参数，即为每个QoS参数定一个能量系数分量a1∈[0，1]；能量函数的个数为B，它均匀分布在能量系数a的取值范围内，与QoS请求无关；(2)根据拓扑图G，针对B个能量系数向量中某一个尚未使用过的向量计算每条链路的能量值：$g_a\left(e\right)={\Sigma }_{l=1}^k{a}_l{w}_l;$ (3)从根节点s出发，计算从s到每一个节点—包括目标节点t—在内的最短路径树；(4)根据最短路径树产生部分路由表QoSR；(5)判断是否已经使用过了所有的B个向量：若存在没有使用过的向量，则返回步骤(2)；若不存在没有使用过的向量，择把基于B向量产生的所有部分路由表组成一个完整的QoS路由表。