航空信息网络链路代价计算与最短路径算法描述

SDN／IP混合网络中的流量工程问题是非确定性多项式-难（non-deterministic polynomial hard，NP-hard）问题，本章提出一种快速启发式算法对混合网络中流量工程问题进行求解。算法的基本思想是：对于混合SDN／IP航空信息网络，定义链路当前剩余带宽与链路中断概率的综合函数为网络中链路的初始代价函数；基于业务优先级Max-Min Fairness（最大-最小公平原则）分配策略针对业务流进行带宽分配；为了实现链路负载均衡优化，将业务流最短路径集合中链路出现次数定义为链路关键度，根据关键度对链路代价函数进行自适应动态调整，每次带宽分配后动态改变链路代价，延期选择关键度大的链路进行业务带宽分配，最终实现流量负载均衡。

1）初始链路代价的确定

算法根据航空信息网络中链路的剩余带宽及链路中断概率定义链路的初始代价函数，并计算得到各业务流的源-目的节点对之间的最短路径。链路初始代价函数定义为与链路剩余带宽成反比且与链路中断概率成正比的综合函数，即优先选择剩余带宽大、链路可靠性高的链路进行传输，使算法在降低链路拥塞、实现网络链路负载均衡、提高网络鲁棒性方面具有优势。初始链路代价计算表达式为

式中，c（e）为链路e的当前剩余带宽，max（c）为所有链路的最大剩余带宽，p（e）为链路e的中断概率，min（p）为所有链路的最小中断概率；λ1为权重调节因子。因此，剩余带宽越大且中断概率越小的链路所对应的初始链路代价越小。

根据式（7.3）计算链路初始代价后，可以通过最短路径算法（如Dijkstra算法）计算得到业务流节点对之间的最短路径。针对业务流最短路径集合中的链路，将其出现次数定义为链路关键度，链路出现次数越多表示该链路越重要，相应的链路关键度越大。定义所有业务流节点对的最短路径集合中所有链路为链路集合L，有|L|=k；则对于任意链路e∈E，定义链路标识符若链路e在第k个最短路径中，否则关键度定义为(https://www.xing528.com)

2）链路代价的动态调整

在求得链路初始代价后，在流量调度过程中，为避免链路拥塞，优先选择链路关键度小的链路，因此需要动态调整链路代价。令链路代价为链路带宽、中断概率和关键度的综合函数：

式中，δ（e）为链路（u，v）的关键度，λ2为权重调节因子。若某条链路在多个业务流的最短路径中，则该链路关键度较大，相应的链路代价增加，在流量路由过程中则延期选择该链路以避免链路拥塞。