【《基于QoS优先级的负载均衡路由算法分析》6400字】

V基于QoS优先级的负载均衡路由算法研究目录TOC\o"1-3"\h\u27591基于QoS优先级的负载均衡路由算法研究 1184201.1网络模型 2230371.2问题描述 319571.2.1流业务分类介绍 333491.2.2边界交换机队列模型与优先级计算 4257261.2.3基于流优先级路由代价函数分析 8118501.2.4基于流优先级的路由约束 928781.2.5路由模型 915441.3基于QoS优先级的负载均衡路由算法 10242311.1.1用户交换机中流量调度方法 10163901.1.2QoS路由算法 11183381.4仿真实验与结果分析 1295521.4.1仿真实验环境设置 1219701.4.2结果分析 12在网络流量爆炸蓬勃发展的今天，用户对网络质量的要求逐步提高，通常采用多个参数来衡量网络的具体性能。面对网络需求的不断变化，本文提出了在软件定义网络（SDN）下基于QoS优先级的多路径负载均衡路由算法。该算法根据多媒体应用中不同的QoS要求，业务被分类并分配它们各自的优先级，全面考虑网络数据流的优先级和链路的实时状态，满足了业务的严格QoS要求。此外，本章算法通过考虑链路带宽、链路延迟和链路负载等实时参数，对链路代价函数进行了优化，从而灵活地分配资源，均衡网络负载，减少了不同业务类之间的影响。通过大量的模拟实验，证明了所提出的算法在提高网络性能方面明显优于其它现有的调度方法。1.1网络模型图1.1基于QoS优先级的网络模型如图1.1所示，本章对各种类型的流进行QOS优先级分级和网络负载均衡路由问题进行了研究。在特定的网络中，终端用户使用不同类型的应用程序，产生各类QoS要求的数据流量，网络由OF交换节点组成，网络流进行接入，到达边缘交换机，数据流经流分级和路由转发，SDN控制器具有全局视图，采集接入网数据流量的类型和相关路由参数以及网络中节点和链路的状态信息。利用图论的原理，可以将QoS网络抽象成一个加权无向图G（V，E），其中V表示QoS网络中的交换机集，也即网络节点集，且，E表示传输线路，也即网络链路集。定义表示网络节点i到网络节点j之间的链路。在现实网络中，一般网络链路都是全双工的，因此如果存在i到j的链路，那么一定存在j到i的链路。不失一般性，假设G是没有任何孤立节点的连通图，链路的带宽容量、传输时延以及丢包率分别表示为、、。令表示SDN控制器是否将链路（i，j）分配给为业务流k进行传输，如果业务流经由链路（i，j），则将置1，否则为0。业务集合K，。业务k主要包括以下几个特征，源节点（进入网络的节点），目的节点（离开网络的节点），带宽需求设为，其他的QoS需求包括传输时延和丢包率，分别由和表示，指代该业务可接受的最高时延和丢包阈值。定义路径r是网络流自源节点（即接入节点）至目的节点的可达路由路径，集合R是所有可达路径集合，。1.2问题描述1.2.1流业务分类介绍由于用户业务的类型不同，可以将网络流量分为不同的类型，每种类型的流都有其自身的质量和性能要求。从网络管理的角度来看，在实际应用中可以根据QoS要求对所有类型的流量进行分类。根据参考文献[27]，根据其QoS要求将应用程序分为三大类：QoS高要求：这些应用程序的流量具有很高的QoS要求。它们是支持最终用户体验的关键途径，例如在数据中心或实时数据库中响应用户的请求。本类流量对数据包丢失和延迟高度敏感，即使响应时间（100ms）的微小增加也会降低用户体验。QoS低要求：这些应用程序不是用户体验的关键路径，但是它们的流量仍然需要及时交付或高带宽。一个典型的例子是数据中心之间的备份流量，此外，VOD服务也属于此类别。无特殊要求（尽力而为即可）：这些应用程序没有QoS要求，例如Web应用程序和不同数据中心的备份数据。根据应用不同的QoS要求，将用户流量划分为不同的优先级，从而减少了业务类之间相互干扰，避免了业务流聚集在同一链路上而造成网络拥塞，从而有效地实现业务类之间网络资源的分配。各个优先级定义如下：高优先级，对应高QoS要求的应用流，如对延迟极度敏感的视频等。低优先级，对应低QoS要求的应用流。QoS是用来保证网路服务的质量的，而网络的质量受到多种因素制约，包括带宽、时延、丢包率、时延抖动等。因此，QoS可以使用这些可度量的参数进行描述。带宽：指的是单位时间内能传输的数据量，用来度量网络传输数据的最大传输速度。对于一个网络来说，网络中的交换机端口和交换机之间的链路介质都有各自的带宽限制，当它们相互连接时，网络链路的带宽将由链路介质和链路两端的交换机端口共同决定。时延：是传输的数据从网络的一端到达另一端所用时间，包括数据在网络设备转发的时间和在链路上的传输时间。丢包率：指的是数据包在网络传输过程中被丢弃的报文数占总报文数的比例。丢包主要由于网络设备的输出缓存不足导致丢弃后来的报文导致，以及传输错误。丢包会严重影响网络的质量。时延抖动：指的是时延的变化，可以用前后两个数据包的时延差异来确定。差异越大时延抖动越大，网络越不稳定，反之，差异越小时延抖动越小，网络越稳定。1.2.2边界交换机队列模型与优先级计算网络中的交换机按照角色可以分为边缘交换机与转发交换机，其中边缘交换机中包含直接与用户交互的交换机，本文对与用户直接交互的边缘交换机（以下使用用户交换机）进行研究。图1.2优先级流量缓存队列（1）用户交换机队列模型如图1.2所示，按照上一节分类，用户交换机中按照优先级维护三个流量缓存队列。用户交换机根据用户的流量需求，将流量分配到不同的优先级队列中。用户交换机按照优先级的顺序转发队列中的流量。流量转发规则如下：（a）只有高优先级的流量转发结束，才会继续转发低优先级的流量。（b）若当前在进行低优先级流量转发，若新进入高优先级流量，则中断低优先级流量的转发，进行高优先级流量的转发。（c）若当前在进行高优先级流量的转发，此时新进入低优先级流量，则低优先级流量按照优先级进入缓存队列中。（2）缓存队列调度算法图1.3流二级分类示意图如图所示，本文采用二级分类的方法，对用户交换机中的流量进行排序与调度。首先，如图1.3所示，首先对用户流量进行优先级大分类，用于根据IPV4报头或源IP地址在到达控制器时根据业务类型（TOS）字段对业务类型进行区分。例如，带有TCP端口号21（为FTP保留）的数据包可以是一个流定义，或者具有RSTP（实时流协议）头的数据包表明流传输语音、视频。根据数据包报头字段中的域，数据包被转发到两个独立的先进先出（FIFO）队列中。为了进一步满足用户的QoS需求对每个队列中的各个流按照模糊层次分析法进行二次优先级计算与排序（即调度顺序），具体过程如下：（a）以调度顺序为最终目标，考虑带宽、时延、丢包率为考虑因素，建立如下层次结构模型[28]：图1.4模糊层次结构模型（b）不同的优先级队列采用不同的三角模糊数据（如下表），并建立一个组三角模糊比较矩阵。表1.1三角模糊数据表模糊语言三角模糊量表三角模糊倒数量表重要性一样（1，1，1）（1，1，1）较重要（1，3/2，2）（1/2，2/3，1）重要（3/2，2，5/2）（2/5，1/2，2/3）更重要（2，5/2，3）（1/3，2/5，1/2）特别重要（5/2，3，7/2）（2/7，1/3，2/5）（1.1）其中，（c）模糊权重计算目前已经存在了许多方法来处理模糊比较矩阵。在文献[29]中，Faran和Kemal对9种流行算法进行了综合性能分析。研究发现，改进的对数最小二乘法（LLSM）（文献[30]-[32]）通常比其他算法具有更好的性能。因此，我们通过构建以下模糊对数最小二乘模型，选择改进的LLSM来计算模糊权重（1.2）等式1.2中给出的模型，其约束都是线性的，是一个受约束的非线性优化模型，可以通过Matlab求解。模型的最佳解直接形成归一化的模糊权重，所得权重不能用来确定综合权重。因此，质心解模糊技术被用来对模糊权重进行解模糊：（1.3）（d）调度顺序计算经过解模糊之后，可以得到最终的队列中的优先级排序：（1.4）（三个参数分别代表时延、带宽、丢包率）1.2.3基于流优先级路由代价函数分析在用户交换机确认转发业务流量之后，控制器根据业务优先级选择不同的代价函数与路由算法。（1）用户有QoS要求路由对于具有QoS要求的流量，综合考虑带宽、时延与丢包率，建立如下代价函数：（1.5）其中分别表示链路的带宽、时延与丢包率。是比例因子，并且允许根据特定流的延迟、带宽以及丢包率的重要性来平衡链路代价。表示惩罚因子，其根据到达的数据流个数N依次从0，1，2…N-1开始依次取值，表示上一条到达的数据流所选取的最优负载均衡路由的链路权重总和。通过上述的公式（1.5）可以看出，通过惩罚因子的设置，其根据数据流到达的个数N依次从0，1，2…N-1开始依次取值，可以阻止当前链路被重复选中，有利于寻找不相交最优路径的路由，从而可以有助于实现负载均衡，提高链路利用率。（2）用户无特殊要求路由对于此时的流来说，选择链路的重要因素就是链路的剩余带宽，因此此时的链路代价函数定义为：（1.6）其中表示链路（i，j）上的最大可用带宽，表示已经使用的带宽。使用该代价函数，采用Dijkstra算法进行路由，得到最短传输路径。在此种情况下，本文采用最大连路带宽与剩余带宽的比率作为代价函数，而不是以剩余带宽作为代价函数，以实现网络业务负载均衡。因此对于有QoS要求的流，本算法总是选择最小代价路径传输，同时尽可能的选择不相交路径以进行负载均衡。而对于无QoS要求的流，本算法则按照剩余带宽情况选择最短路径，考虑了负载均衡策略，避免与有QoS要求的流在路径上进行拥塞。1.2.4基于流优先级的路由约束前述内容为进入网络边缘节点的网络流优先级进行研究计算。网络流进行二次优先级排序，并建立基于优先级流量排序的边界交换机队列模型。通过SDN控制器获取网络节点和链路状态信息，结合网路链路资源使用情况，本小节对进入网络的网络流路由约束进行阐述。（1.7）网络流路由路径r所经过的节点包含源节点、目的节点以及转发节点，源节点是网络流进入网络的入口节点;目的节点是网络流最终路由的目的地，不再进行下一跳转发;中间节点流入的网络流大小与流出的网络流大小一致，因此有流量网络链路中的流量守恒。（1.8）其中表示链路（i，j）的最大带宽容量网络流使用路径r进行转发时，经过的每条网络链路都应符合带宽资源容量约束，即已使用带宽与网络流即将占用带宽资源之和不超过链路带宽容量上限：（1.9）其中表示满足业务k服务质量的最大时延要求，网络中网络流使用路径r进行转发时，业务流的时延要求要满足业务时延上限。（1.10）其中表示满足业务k服务质量的最大丢包率要求，网络中网络流使用路径r进行转发时，业务流的丢包率要求要满足业务丢包率上限。1.2.5路由模型在软件定义网络中，链路资源的负载程度对网络性能有较大影响，当链路资源占用率高时，网络更易发生拥塞或性能下降等问题，本节在保证QoS要求的基础上和上述约束对资源负载问题进行研究，使网络中链路负载均衡及降低路由时产生的总路由开销。即优化目标为：（1.11）其中表示链路（i，j）的带宽利用率，表示网络链路（i.j）上的单位路由开销，为路由路经开销累计，使用参数来调节链路负载和资源开销的比重。是数据流的非负性约束，以确保网络流具有实际意义。综上，以公式（1.11）的网络中链路负载及路由时产生的资源开销为优化目标，考虑用户多QoS要求，网络流分级和链路负载等约束，建立问题优化模型。从上述公式可以看出，由于约束中存在二进制变量，上述优化问题属于NP-hard问题，无法在多项式时间内得到解的结果[47]，难以使用传统的最优化方法求解因此，本章提出基于流量分级的路由算法对该问题进行求解。1.3基于QoS优先级的负载均衡路由算法1.1.1用户交换机中流量调度方法首先针对进入用户交换机的所有数据流进行优先级分类，具有高QoS要求的流进入高优先级队列，否则进入低优先级队列。然后在所进队列中的所有流，采用模糊层次分析法进行二级优先级排序，得到最终的流的优先级排序结果。具体算法过程如下：表1.1流量调度算法输入：网络拓扑、链路实时参数（带宽、链路、丢包率）输出：优先级排序结果、最优路径1：for用户交换机中的所有数据流2：if具有QoS要求then3：分配到高优先级与低优先级缓存队列中4：for各个缓存队列中的所有数据流5：根据QoS需求，采用模糊层次分析法，确定数据流的顺序6：endfor7：按照调度顺序转发数据流，按照算法2的启发式算法进行路由8：elseif没有QoS要求then9：建立剩余带宽代价函数，采用D算法进行路由10：endif11：endfor1.1.2QoS路由算法首先建立QoS代价函数，并根据此代价函数进行迪杰斯特拉算法进行路由，若所得路径满足时延与带宽要求，则采用此路径，并更新网络的链路代价函数（增加相应权重）。若不满足要求，则更新丢包率与QoS代价函数，并重新进行路由。整个算法过程如下所示：表1.2Qos路由算法输入：网络拓扑、链路实时参数（带宽、链路、丢包率）输出：最优路径1：for网络中的所有数据流2：建立QoS代价函数，采用D算法，得到最短路径3：if路径时延小于最大时延，且满足最大带宽then4：返回当前路径，Flag=true5：else更新丢包率，更新链路QoS代价函数6：重新进行D算法路由7：endif8：ifFlag=truethen9：10：endif11：end1.4仿真实验与结果分析1.4.1仿真实验环境设置用Mininet来搭建软件定义网络拓扑结构实验环境。Mininet是一个轻量级的软件定义网络仿真工具，支持Openflow协议和各种版本的软件交换机，采用的是支持Openflow1.3的虚拟交换机openvswitch和Ryu控制器。同时，在动态生成所有网络拓扑结构的节点被连接到远程的Ryu控制器。控制器主要负责流量控制与管理，如信息采集、路由计算、重路由决策等。所提的算法在基于SDN网络拓扑结构基础上通过设置控制器的周期为2秒来监控底层网络，并在控制器上部署不同的流来评估本章算法性能。测试项目包括时延、吞吐量和丢包率。此外，使用iperf流量生成测试工具，测试生成了更多的测试流。该算法与基于全局网络的等代价多径（ECMP）方法，HiQoS算法进行了比较。，与单路径算法相反，ECMP算法平等的将流量分配给多个相等的代价路径，并涉及到网络的所有链路。如Dijkstra和BelmanFord单路径算法，己被广泛应用于当今数据网络的路由中，基于额外的代价特征（跳跃总数）来选择部分路径传输视频流。尽管ECMP可以在一定程度上改善链路的吞吐量和可靠性，但由于哈希表冲突，该算法不能有效地利用可用带宽，也不能根据链路状态的变化来改变流量分布的比例。为了验证算法的各自性能，在QoS参数方面进行了许多实验，并对结果进行了分析。1.4.2结果分析在相同的测试环境中测试丢包率，如图1.5所示。从下图可以看出，使用本文算法测量丢包率的波动相对平稳并且低于10%，这是因为这种方法充分使用了空闲的路径传输，从而减少了单个链路在整个路径传输过程中造成网络拥塞的不利影响。图1.5丢包率对比图从上图可以观察到更多的包丢失原因在于多个流在共享链路上。在实验开始时，由于使用三种