软件定义网络多路径公平带宽分配路由算法设计

假设已知某软件定义网络的数据转发平面的拓扑结构为 G = (V, L)，其中 G 是无向图，V 为转发设备节点集合，L 为物理链路集合。每条物理链路 l(u, v) 的可用带宽量为 bw(u, v)，物理链路 l(u, v) 的时延为 delay(u, v)，其中 u，v 分别表示转发设备节点。网络中数据流请求动态到达，每个数据流表示为 f(S, T, bw(S, T), priority, delay(S, T))，其中 S，T 为该数据流的源和目的节点，priority 为该数据流的优先级，bw(S, T) 为该数据流请求的带宽量，delay(S, T) 为该数据流的时延约束。假设数据流可采用多条传输路径（路径数最大为 4，带宽请求等额分配到每条路径）进行数据传输。

本文将设计一个路由算法，使控制器能根据网络的全局视图信息，公平地为数据流分配相应的带宽量。

算法设计思路：

建立网络拓扑结构的图模型，并初始化每个节点的流量需求为 0。
对每个数据流进行处理：
1. 通过最短路径算法（如 Dijkstra 算法）计算出源节点到目的节点的所有可行路径，得到一个路径集合 P。
2. 对路径集合 P 中的每条路径，计算其可分配带宽量 bw_p = min(bw(S,T), bw(u,v))，其中 (u,v) 是路径上的一条物理链路。
3. 根据每条路径的时延，将路径集合按照时延从小到大排序。
4. 对于每个优先级，按照权重从大到小的顺序，依次为每个数据流分配带宽量：
  
  a) 对于路径集合 P 中的每条路径，如果该路径上的可用带宽量大于等于带宽请求，就将该路径的带宽分配给该数据流，并更新路径上的流量需求。
  
  b) 如果路径集合 P 中所有可用路径的带宽之和小于带宽请求，就将所有可用带宽分配给该数据流。
5. 将已分配的带宽量按照优先级加权累加到每个节点的流量需求中。
循环处理所有数据流，直到所有数据流的带宽需求都得到满足。
对于每个节点，将其流量需求均匀地分配到其可用带宽量上，实现权重最大-最小公平带宽分配。
输出每个数据流分配到的带宽量和每个节点的流量需求和可用带宽量。

算法优势：

该算法可以公平地为数据流分配带宽量，并且能够在多条可行路径中选择带宽利用率高的路径，以尽可能地利用网络资源。