多路径流量调度算法及链路代价更新函数详解

算法设计主要包括链路代价更新和业务流分配两部分，对于不可控流则根据OSPF最短路径进行路由，最终目标是通过多径传输在业务之间共享带宽，实现网络中流量的负载均衡和网络资源的高效利用。基于优先级的动态流量调度算法的总体流程在算法1中给出，算法1中包括业务流分配和链路代价更新两个子函数，算法的输入信息包括网络拓扑信息、链路OSPF权重（考虑到路由稳定性，设链路OSPF权重均为1）。

算法中首先根据初始链路代价计算每个业务的最短路径，通过找到最短路径中的SDN控制器节点，计算得到每个SDN控制器节点上的可控流。利用SDN控制器可以对该节点上的可控流进行流量调度，将业务流量分配在多个路径上进行传输，然后通过运行业务流分配函数，得到业务的流量调度结果。业务流分配函数的具体流程在算法2中给出，根据算法2的多路径流量调度结果，可以得到业务数据的分配路径和业务量，进一步可以计算获得网络中所有链路的链路利用率。本次业务的流量调度结束后，运行链路代价更新函数，计算当前链路剩余容量和链路关键度，根据计算结果更新链路代价，链路代价更新子函数如算法3所示。算法最后判断是否满足循环条件，若有业务未被调度且存在可选路径，则转入循环，否则算法结束返回业务流分配结果。

1）业务流分配函数

业务流分配函数如算法2所示，在每个业务最短路径中的第一个SDN控制器节点上运行业务流分配子函数。为了实现流量的均衡传输，基于业务优先级采用了最大-最小公平分配原则分配策略进行计算。算法中首先根据链路代价计算业务最短路径，然后根据业务数据量及业务优先级，可计算得到每一条链路上传输的所有业务的公平分配份额：

式中，Ii为业务i的数据量，Pi为业务i的优先级；通过该链路上传输业务的公平分配份额和该链路当前可用带宽约束，可以计算得到该链路上可传输完成和不可传输完成的业务集合Tcomplete，Tincomplete以及本次迭代中该链路上传输的公平分配份额fe；基于最大-最小公平分配原则的思想，网络中本次传输的公平分配份额为所有链路上公平分配份额的最小值；根据本次传输的公平分配份额和业务优先级最短路径，计算得到每个业务本次迭代中的传输路径和业务量。由链路代价函数的定义可知，每次迭代中优先选择利用率低且可靠性高的链路。业务流分配函数循环迭代直到所有的业务均通过多路径传输实现分配调度。(www.xing528.com)

算法2中，设链路e上传输的业务总个数为为链路e上剩余容量，为业务i的已传份额，fileft为业务i的剩余待传输份额，Ik为链路e上第k个业务的数据量，Pj和Pk为第j／k个业务的优先级。

2）链路代价更新函数

链路代价更新函数具体流程如算法3中所示，该算法首先通过业务流的最短路径计算链路关键度，基于初始链路代价和链路关键度，对链路代价进行更新计算得到新的链路代价。根据链路代价更新表达式可知，当某条链路同时存在于多个业务流的最短路径中时，该链路的关键度＞0。关键度越大表明该链路利用率越高，出现拥塞的可能性越大。因此在链路代价更新过程中，对关键度大的链路增加其链路代价，以减小传输路径选择的可能性。这样可以改善网络中链路负载失衡，进一步降低网络拥塞。

续表