【基于QoS优先级的负载均衡路由算法探究6400字】

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