基于轮盘赌轮选择的多路径TCP路径选择优化

Multipath TCP path selection optimization based on roulette wheel selection

摘要

多路径传输控制协议（multipath TCP，MPTCP）利用设备的多个网络接口传输数据，通过聚合带宽来提高传输效率。在进行路径选择时MPTCP通常使用不相交路径选择算法，由于优先选择负载小的路径，这种贪心策略容易造成网络拥塞和带宽利用率不足。轮盘赌轮选择通过概率的方式，在路径选择时加入随机性和动态性，能够克服该贪心策略造成的问题。为此，设计了一种基于轮盘赌轮选择的MPTCP路径选择算法，称作基于轮盘赌轮的MPTCP路径选择（roulette wheel based MPTCP path selection，RWSMPS）。RWSMPS通过软件定义网络（software defined network，SDN）控制器监控和分析网络状态信息，基于轮盘赌轮方式进行子流路径选择，用分组检查将子流分配到路径上，充分利用所有可用路径，并保证路径间的负载平衡。在Mininet平台上的实验证明，相比于广泛使用的等价多路径路由（equal cost multi path，ECMP）算法和链路不相交算法，RWSMPS的吞吐量分别提高了43.9%和41.8%，抖动分别减少了41.6%和40.7%。

Abstract

Multipath TCP （MPTCP） uses multiple network interfaces of the device to transmit data， and improves transmission efficiency by aggregating bandwidth. When performing path selection， MPTCP usually uses a disjoint path selection algorithm. Since the path with a small load is preferred， this short-sighted greedy strategy is likely to cause network congestion and insufficient bandwidth utilization. Roulette wheel selection can overcome the problems caused by this greedy strategy by adding randomness and dynamics to path selection through probability. For this reason， a MPTCP path selection algorithm based on roulette wheel selection was designed，which called RWSMPS.RWSMPS monitors and analyzes network status information through the SDN controller， selected sub-flows paths based on the roulette wheel method， used packet inspection to distribute sub-flows to paths， made full use of all available paths， and ensured load balance between paths. Experiments on the Mininet platform prove that compared with the widely used ECMP algorithm and link disjoint algorithm， RWSMPS improves throughput by 43.9% and 41.8%， respectively， and reduces jitter by 41.6% and 40.7%.

关键词

多路径传输控制协议 / 轮盘赌轮选择 / 路径选择 / 软件定义网络 / 负载平衡

Key words

MPTCP / roulette wheel selection / path selection / SDN / load balancing

随着互联网技术的发展，高质量视频对带宽的要求越来越高。多路径传输技术能够使用终端的多个网络接口来聚合带宽^［1］，提高传输性能。互联网工程任务组提出并制定但MPTCP协议的标准，通过使用多个子流在路径上并行传输^［2］来提高吞吐量和稳定性。MPTCP作为传输层协议，不能感知底层网络状态。软件定义网络作为一种控制与转发分离的新型网络架构，通过SDN控制器收集网络状态信息，提供全局状态视图，可以在MPTCP传输时感知网络信息，为优化多路径传输效率提供帮助^［3］。

MPTCP路径选择优化的主要方案有两种：第一种是为不同的子流选择链路不相交的路径^［4］来避免传输过程中不同子流共用同一路径的问题；第二种是在进行路径选择时考虑链路负载^［5］，选择负载较小的路径来分配子流。Barakabitze等^［6］结合分段路由提出了一种不相交的路径选择方式，通过满足特定服务的QoE需求为子流选择不相交的路径，但该方法需要进行子流路径到分段路由路径的映射。Gao等^［7］提出了一种QoS驱动和SDN扩展的路径选择方案，利用网络监测模块收集和分析网络信息，但该方法只考虑了网络中存在MPTCP流，没有考虑存在其他流的情况。Zou等^［8］提出一种虚拟现实视频多路径传输方法，但是只考虑延迟信息，导致当前的最优路径可能在下一时段会发生拥塞。Bagaa等^［9］提出了一种支持QoS配置的多路径转发方法，通过减少过度QoS来提高多路径传输的性能，但需要大量的交换机参与转发。Cao等^［10］提出了一种以接收方为中心的方案，接收方通过获得的信息估计路径负载并选择路径，但此方法需要对接收方进行改进。Nguyen等^［11］利用贪婪算法为子流进行路径选择，通过在路径集中选择K条最短路径来提高性能，但只适用于可选路径数较少的情况。

上述方案在优化MPTCP的路径选择时，通常优先选择负载或者延迟最小的路径，而没有考虑路径间的流量平衡。这种短视的贪心策略导致这一时段的最优路径可能是下一时段的拥塞路径^［12］，造成带宽利用率不足。为了平衡路径间的流量负载，避免出现瓶颈路径的同时提高多路径传输效率，本文设计了一种在软件定义网络中基于轮盘赌轮选择的MPTCP路径选择方案，简称RWSMPS（Roulette Wheel Based MPTCP Path Selection）。RWSMPS利用轮盘赌轮选择的方式将子流确定地分配到路径上，平衡所有路径上的流量，避免在传输期间出现拥塞路径。通过优化MPTCP的路径选择，提高传输的吞吐量和稳定性。

1 问题描述与分析

MPTCP通过使用多个子流来转发数据，提高吞吐量。通常MPTCP与等成本多路径路由（ECMP）^［13］结合使用，ECMP通过随机散列的方式，将子流随机转发到最短路径中。如果多条子流使用相同的网络链路会出现共享瓶颈。共享中的瓶颈链路会出现带宽利用率过高，造成网络拥塞的问题。不相交路径选择算法主要考虑路径负载来分配子流，通过为子流分配明确的路径，保证使用网络中的不同路径进行数据传输。这种不相交路径选择方式可以提高瓶颈处的吞吐量。

现有的不相交路径选择算法在进行子流的路径选择时，总是选择负载最小的路径作为最佳路径。这个过程分为两个阶段：在第一阶段，首先通过最短路径算法寻找源到目的主机之间的一组候选路径；在第二阶段，通过使用贪心策略从候选路径集中选择负载最小的路径。将SDN网络看作一个加权图 G = ( V , E )，其中， V是顶点的集合， E是相互连接的顶点的边的集合。对于每一条边 ( u , v ) \in E， R_l ( u , v )表示边的负载情况。假设存在一条从源到目的节点的路径，该路径的最大负载由路径上负载最大的链路决定。通过最短路径算法获得一组候选路径，然后利用贪心策略从候选路径中选择出负载最小的路径，即 \mathrm{M} \mathrm{I} \mathrm{N} ( R_l ( u , v ) )，其中， ( u , v ) \in E。由于贪心策略追求局部最优的特点，将导致所有子流都在负载最小的路径上进行数据传输，该路径往往成为下一个周期中的瓶颈路径，如图1所示。由于子流路径调整的滞后，即使该路径下一时刻成为瓶颈，子流依然会在该路径上进行传输。盲目选择最优路径会导致原本负载最小的路径出现瓶颈，容易造成网络拥塞和带宽利用率不足等问题。

经过分析，轮盘赌轮选择使用概率的方式，根据累积概率来动态进行选择，这种方式的特点是动态性与随机性。动态性体现为链路带宽利用率和路径选择概率的动态变化。随机性体现为负载较低的路径不一定被选择，而是赋予其较大的被选概率。轮盘赌轮方式可以显著减少使用贪心策略导致的局部最优风险。在多路径选择中，通过路径的负载来确定路径被选择的概率。每个路径被选中的概率和其适应度相关，适应度与路径负载成反比，负载越小的路径被选择的概率越大。假设某一路径 p的负载为 R_l ( p )，适应度 f ( p )，通过式（1）可得

f ( p ) = \frac{\mathrm{1}}{R_l(p)} （1）

该条路径被选择的概率 P ( p )由式（2）可得。其中，累积概率表示每条路径之前所有路径的选择概率之和，路径 p的累积概率通过式（3）计算

P ( p ) = \frac{f(p)}{{\displaystyle \sum _{j=\mathrm{1}}^N}{f}_j} （2）

q ( p ) = {\displaystyle \sum _{j=\mathrm{1}}^i} P(p_j) （3）

使用轮盘赌轮方式动态调整路径，可以充分利用所有可用路径，提高带宽利用率。通过保证路径间的负载平衡，避免瓶颈路径出现。

2 基于轮盘赌轮的路径选择方案

2.1 RWSMPS控制器实现架构

本文提出的RWSMPS路径选择方案主要由运行在Floodlight控制器^［14］上的拓扑管理模块、交换机信息收集模块和RWSMPS路径计算模块组成。目前SDN应用最广泛的协议是OpenFlow协议^［15］，负责控制平面和数据平面之间的交互。RWSMPS的框架如图2所示。

控制器通过OpenFlow协议下发流表，动态控制管理网络^［16］。其中链路发现模块作为控制器中的基础模块，定期收集网络链路和节点信息来生成网络拓扑。拓扑管理模块根据拓扑信息计算出多路径传输的源到目的节点的所有可达路径信息。交换机信息收集模块定期发送请求获取交换机端口流量信息。在RWSMPS路径选择模块中实现轮盘赌轮路径选择算法，根据可达路径信息和路径负载信息来计算最佳路径。控制器通过流表的方式把信息安装到所有交换机中。

2.1.1 拓扑管理模块

该模块主要用来获取源到目的节点之间的可达路径信息。控制器中的链路发现模块使用链路层发现协议（link layer discovery protocol， LLDP）^［17］在控制器和交换机之间通信，从网络中收集链路和节点信息，通过对获得的信息进行整理来生成全局的网络拓扑。根据获得的拓扑信息，拓扑管理模块使用深度优先遍历算法计算可达路径，获得多路径传输的源到目的地址之间的路径集。控制器中保存计算的路径集信息，供路径选择模块使用。

2.1.2 交换机信息收集模块

为获取链路的负载情况，需要对交换机端口流量信息进行监控。交换机信息收集模块通过链路发现模块得到全局网络拓扑，从交换机获取端口流量信息。为保证端口信息的实时性和可靠性，该模块每10 s向所有交换机端口发送请求来获取数据。为了确定端口的带宽利用率，交换机的端口速率 R用式（4）计算

R = \frac{T_{rb}-T_{ra}}{T_{ab}} （4）

式中： T_{rb}为 b时刻交换机端口传输和接收的数据量； T_{ra}为端口 a时刻传输和接收的数据量； T_{ab}为 a时刻到 b时刻的时间。本文采用指数加权移动平均法（exponential weighted moving average， EWMA）^［18］来预测链路的负载。根据前一时刻的端口速率和负载预测值，来计算当前时刻端口的负载预测值。对于所有交换机， t时刻的负载预测值 E ( t )通过式（5）得出

E ( t ) = ( \mathrm{1} - \alpha ) E ( t - \mathrm{\Delta } t ) + \alpha R \mathrm{\Delta } t （5）

式中： \mathrm{\Delta } t为估计周期； R为 \mathrm{\Delta } t的端口速率； \alpha为预测值的加权系数，取值为（0，1）。

2.1.3 RWSMPS路径计算模块

作为整个方案的关键模块，RWSMPS路径计算模块根据拓扑管理模块提供的路径集信息和路径集中所有路径的负载预测值，为子流进行路径选择。该模块实现本文提出的轮盘赌轮路径选择算法，选择路径时不一定选择负载最小的路径，而是赋予负载较小的路径较大的选择概率。通过平衡路径间的流量负载来避免出现拥塞，提高MPTCP传输时的网络利用率。在得到合适的路径后，通过OpenFlow协议以流表的方式安装到选择路径的交换机中。

2.2 轮盘赌轮路径选择算法

本文提出一种基于轮盘赌轮的路径选择算法，应用轮盘赌轮的方式来进行MPTCP子流的路径选择。轮盘赌轮路径选择算法流程如图3所示。

首先获取源到目的节点的路径集，对于每条路径，根据路径上交换机端口的负载预测值，用最小的端口负载预测值来代表路径的负载预测值。整条路径的负载归一化 L ( t )通过式（6）得到

L ( t ) = \frac{E(t)}{C} （6）

式中 : E ( t )为 t时刻路径的负载预测值； C为交换机的端口容量。 L ( t )的值在每个端口定期更新，反映路径的当前负载情况。首先，计算出路径集中每条路径的权重，其中路径的权重负载来确定。用 \frac{\mathrm{1}}{L(t)}来表示路径被选择的权重，负载越小的路径权重越大。当 L ( t )等于0时，假设路径权重为一个足够大的值 M，本文假设 M = \mathrm{10} \mathrm{000}，累加所有路径的权重。每条路径的权重占权重之和的比例就是这条路径被选择的概率。然后随机选择一个在0到1之间的实数 S，遍历所有路径并累加当前路径的概率，直到累加概率大于 S。累加概率大于 S时的当前路径就是要选择的路径。MPTCP传输中多条子流的路径选择都通过轮盘赌轮的方式，使负载较小的路径传输更多流量。

MPTCP在建立连接时，使用RWSMPS路径选择方案进行路径选择。建立第一条子流和添加额外子流的数据包交互过程如图4所示。当交换机收到一个MPTCP客户端发来的数据包时，如果没有指定的流表去处理转发，就会通过OpenFlow协议将该数据包发送到控制器处理。控制器提取数据包的包头信息，检查是否存在表示MPTCP连接的选项MP_CAPABLE或者MP_JOIN。如果不存在表示MPTCP连接的选项，控制器把数据包当作普通TCP数据包处理。如果数据包存在MP_CAPABLE选项，说明该数据包是创建新MPTCP连接的设置包。控制器通过提取源到目的节点的地址，运行RWSMPS方案为子流选择路径，通过流表把选择的路径信息安装到交换机中。交换机通过指定的路径将数据包发送给MPTCP服务器，服务器收到后发送确认信息给MPTCP客户端，此时进行MPTCP传输的第一条子流就建立完成了。如果存在MP_JOIN选项，该数据包表示用来建立额外的子流，控制器通过判断该数据包所属的MPTCP连接信息，再次运行RWSMPS方案为额外的子流选择路径。每条子流通过该方式建立连接后，MPTCP连接创建完成。

3 实验环境与分析

3.1 实验环境

本文通过VMware虚拟机平台搭建实验环境，虚拟机使用Ubuntu18.04操作系统，使用Floodlight作为SDN控制器，使用Mininet作为网络仿真平台。Floodlight和Mininet安装在不同的虚拟机系统中，其中运行Mininet的系统编译并安装了MPTCP v0.95内核，可使用MPTCP进行数据的传输。

3.2 实验设置

本文利用Mininet 2.3.0网络仿真器建立网络拓扑，模拟OpenFlow交换机的软件是OpenvSwitch 2.9.8。实验中使用的OpenFlow协议版本为OpenFlow1.3。利用分布式互联网流量生成器（D-ITG）^［19］来生成网络流量。

实验拓扑及参数如图5所示，拓扑中包含12个OpenFlow交换机、2台服务器和2台客户机。实验通过MPTCP服务器向MPTCP客户机发送带宽为10Mbps的视频数据进行仿真，UDP服务器利用Iperf软件向UDP客户机发送带宽为1Mbps的UDP流量作为背景流量。RWSMPS路径选择时负载预测值中的 \alpha取值为0.8，实验持续1 800 s。将MPTCP的路径管理器设置为fullmesh模式，假设MPTCP的连接不受端点访问链路的限制。在实验中将本文算法与经典的ECMP算法和链路不相交（Disjoint）算法进行性能对比。

3.3 评价指标

为了验证本文所提算法在进行MPTCP多路径传输时，是否能够根据路径负载情况进行路径选择，并通过平衡路径间的流量来提高传输性能。本文选取吞吐量和抖动两个性能指标，统计在不同子流情况下算法之间的性能差异。

3.4 实验结果与分析

以10M带宽传输视频流时，比较不同数量子流在1 800 s内传输视频流的平均吞吐量，结果如图6所示。随着子流数量的增加，吞吐量提高的同时连接开销也随之上升，当子流数大于6时，传输效率开始下降^［20］。因此在实验中，子流数分别设置为4、5和6。ECMP算法和链路不相交算法的表现类似，由于随机分配路径的特性，ECMP子流很容易在链路上发生冲突，而链路不相交算法追求负载最小的路径，追求局部最优容易出现路径的拥塞，因此这两种算法的表现不佳。RWSMPS利用轮盘赌轮的方式动态选择路径，可以平衡路径间的流量负载，避免路径间出现冲突，在平均吞吐量上明显优于ECMP算法和链路不相交算法。图7比较了不同数量的子流在1 800 s内的平均抖动，由于在路径选择时考虑了路径上的负载情况，避免拥塞来保证数据包的有序到达，在抖动上RWSMPS表现优于另两种算法。通过保证较低的抖动，传输获得了更好的稳定性。

图8、9和图10分别表示传输过程中使用不同算法1 000 s到1 200 s时间段内的吞吐量比较。当子流的数量为4时，RWSMPS在吞吐量的表现上比另外两种算法分别提高了38.3%和37.6%，保持较高传输速率而且吞吐量比较稳定。当子流的数量为5时，使用RWSMPS在吞吐量上比另外两种算法分别提高了51.6%和46.9%，但由于路径间的差异，此时RWSMPS传输过程中吞吐量开始出现抖动。当子流的数量为6时，RWSMPS在吞吐量上比另外两种算法分别提高41.9%和40.9%，其中RWSMPS传输中的吞吐量比较稳定，但另两种算法的传输吞吐量开始出现抖动现象，影响传输中的稳定性。因为RWSMPS可以充分利用网络资源，并避免路径上的负载过大，RWSMPS在表现上优于另外两种算法。其中，ECMP算法由于随机的子流分配，容易导致不同子流在相同路径上出现冲突，吞吐量最低。由于没有考虑路径间的负载情况和不同路径间的差异，追求负载最小的路径容易造成拥塞，链路不相交算法在传输过程中吞吐量表现不佳。RWSMPS在进行传输时考虑路径间的负载情况，避免了路径拥塞，因此吞吐量最高。

对于进行多路径传输的设备来说，6条子流已足够满足传输需求。由于路径之间的差异，超出6条子流时，在子流间的协作控制上会付出较大代价，能耗也会越来越大，造成传输效率下降的同时导致网络资源的浪费。

综上，实验结果证明：本文提出RWSMPS算法明显优于ECMP算法和路径不相交算法。ECMP在吞吐量和抖动方面表现最差，路径不相交算法因为没有考虑网络中的负载平衡，盲目追求负载最小的路径导致其表现不佳。RWSMPS通过轮盘赌轮选择的方式在进行子流的路径选择时，考虑路径间的负载情况，避免了路径拥塞和带宽利用率不足等问题。RWSMPS相比另外两种算法在平均吞吐量和抖动上表现更好，提高了MPTCP的传输性能。

4 结论

本文提出了一种基于轮盘赌轮选择的MPTCP路径选择方案（RWSMPS），结合软件定义网络可以感知网络的优势，对子流的路径选择进行了优化。RWSMPS能够利用控制器对交换机的流量信息进行检测，以轮盘赌轮的方式来进行子流的路径选择。通过考虑路径上的负载情况，在选择路径时MPTCP平衡不同路径间的流量负载，提高了多路径传输效率。通过仿真证明了RWSMPS在吞吐量上比ECMP算法和链路不相交算法分别提高了43.9%和41.8%左右，能够有效提高传输效率。RWSMPS在抖动上比另两种算法分别减少了41.6%和40.7%左右，保证了传输的稳定性。

参考文献

[1] Wu J Y， Cheng B， Wang M，et al.Quality-aware energy optimization in wireless video communication with multipath TCP[J].IEEE/ACM Transactions on Networking，2017，25(5)：2701-2718.

[2] Singh S K， Das T， Jukan A.A survey on Internet multipath routing and provisioning[J].IEEE Communications Surveys & Tutorials，2015，17(4)：2157-2175.

[3] Dutra D L C， Bagaa M， Taleb T，et al.Ensuring end-to-end QoS based on multi-paths routing using SDN technology［C］//GLOBECOM 2017-2017 IEEE Global Communications Conference.Singapore City，Singapore：IEEE，2018：1-6.

[4] Kimura B Y L， Lima D C S F， Villas L A，et al.Interpath contention in MultiPath TCP disjoint paths[J].IEEE/ACM Transactions on Networking，2019，27(4)：1387-400.

[5] Jerome A， Yuksel M， Ahmed S H，et al.SDN-based load balancing for multi-path TCP［C］//IEEE INFOCOM 2018-EEE Conference on Computer Communications Workshops （INFOCOM WKSHPS）.Honolulu，USA：IEEE，2018：859-864.

[6] Barakabitze A A， Sun L F， Mkwawa I H，et al.A novel QoE-centric SDN-based multipath routing approach for multimedia services over 5G networks［C］//2018 IEEE International Conference on Communications （ICC）.Kansas City，USA：IEEE，2018：1-7.

[7] Gao K， Xu C Q， Qin J R，et al.QoS-driven path selection for MPTCP：a scalable SDN-assisted approach［C］//2019 IEEE Wireless Communications and Networking Conference （WCNC）.Marrakesh，Morocco：IEEE，2019：1-6.

[8] Zou F Y， Wang Y M， Liu Y.A multipath routing approach for tile-based virtual reality video streaming based on SDN［C］//2021 IEEE 45th Annual Computers，Software，and Applications Conference （COMPSAC）.Madrid，Spain：IEEE，2021：560-565.

[9] Bagaa M， Dutra D L C， Taleb T，et al.On SDN-driven network optimization and QoS aware routing using multiple paths[J].IEEE Transactions on Wireless Communications，2020，19(7)：4700-4714.

[10] Cao Y L， Yu D D， Zeng L，et al.Towards efficient parallel multipathing：a receiver-centric cross-layer solution to aid multipath TCP［C］//2019 IEEE 25th International Conference on Parallel and Distributed Systems （ICPADS）.Tianjin，China：IEEE，2020：790-797.

[11] Nguyen K T， Nguyen L T， Vu H T，et al.Efficient multipath routing scheme for MPTCP-enable software-defined networks［C］//2021 International Conference on Advanced Technologies for Communications （ATC）.Ho Chi Minh City，Vietnam：IEEE，2021：68-72.

[12] 鲁垚光，王兴伟，李福亮，软件定义网络中的动态负载均衡与节能机制[J].计算机学报，2020，43(10)：1969-1982.

[13] Zannettou S， Sirivianos M， Papadopoulos F.Exploiting path diversity in datacenters using MPTCP-aware SDN［C］//2016 IEEE Symposium on Computers and Communication （ISCC）.Messina，Italy：IEEE，2016：539-546.

[14] Deng S H， Gao X， Lu Z B，et al.Packet injection attack and its defense in software-defined networks[J].IEEE Transactions on Information Forensics and Security，2018，13(3)：695-705.

[15] 徐玉华，孙知信.软件定义网络中的异常流量检测研究进展[J].软件学报，2020，31(1)：183-207.

[16] Isyaku B， bin Abu Bakar K， Ghaleb F A，et al.Path selection with critical switch-aware for software defined networking［C］//2021 IEEE Symposium on Wireless Technology & Applications （ISWTA）.Shah Alam，Malaysia：IEEE，2021：22-26.

[17] Chang Y C， Lin H T， Chu H M，et al.Efficient topology discovery for software-defined networks[J].IEEE Transactions on Network and Service Management，2021，18(2)：1375-1388.

[18] Chung T D， Ibrahim R B， Asirvadam V S，et al.Adopting EWMA filter on a fast sampling wired link contention in WirelessHART control system[J].IEEE Transactions on Instrumentation and Measurement，2016，65(4)：836-845.

[19] Malik A， de Fréin R.SLA-aware routing strategy for multi-tenant software-defined networks［C］//2020 IEEE Symposium on Computers and Communications （ISCC）.Rennes，France：IEEE，2020：1-7.

[20] Joshi K D， Kataoka K.SFO：SubFlow optimizer for MPTCP in SDN［C］//2016 26th International Telecommunication Networks and Applications Conference （ITNAC）.Dunedin，New Zealand：IEEE，2017：173-178．

基金资助

国防科工局基础研究项目(JH2021010)

辽宁省教育厅项目(L201626)