本发明属于计算机网络流量调度领域，尤其涉及一种基于qos的路由并且完成流传输路径一致性更新的方法。
背景技术：
随着数据中心的发展，用户请求的网络业务不断增多，网络中流量迅猛增加，然而整个网络所能提供的带宽资源往往是有限的，当用户对网络资源的需求超过网络所能提供的上限时，网络可能会发生拥塞，引起丢包或时延增大。传统的流量调度技术主要包括nativeip和mpls-te。前者基于dijkstra算法，根据跳数等约束选择一条最短路径，因此会造成局部链路拥塞。后者基于cspf算法，选路时综合了链路带宽资源信息，改善了拥塞问题。由于传统网络节点总是以自我为中心计算最短路径，得到的往往是一个局部最优的结果，而且在技术较为复杂的情况下，由于传统网络的分布式结构，有时需要逐交换机进行部署，过程相当繁琐。
sdn网络架构的核心思想是控制与转发分离，底层的设备只需要关注转发速率的提高，控制层则负责复杂的控制功能和协议更新，这种设计思想为我们处理数据中心流量调度提供了新的解决思路。逻辑上集中的控制器拥有全局视角，通过开放的北向接口，开发者获得全局网络资源和网络状态信息，流量调度技术可以根据这些基础信息和用户的需求灵活的分配、整合网络资源，提供服务质量保障，提高带宽利用率。现有的sdn环境下流量调度相关研究主要考虑了在一个或者多个约束条件下，尽可能地均衡使用全网带宽资源，在网络较为拥塞，链路资源碎片化较多的场景中，采取已有的调度算法，新的业务流可能无法直接加入网络。
sdn架构下流的传输路径发生改变时，控制器需要指示数据平面进行路径的更新，数据流传输路径的更新包括删除旧流表和安装新流表。然而，更新sdn交换上的流表通常是任意的选择交换机的顺序进行更新，这可能会产生很多问题，例如数据平面的不一致性问题会导致流量黑洞、流量环路、死锁、链路拥塞等问题。现有的一致性更新算法无法在保证低丢包率的情况下解决上述问题。
技术实现要素：
本发明所要解决的技术问题在于提出一种流量调度方法，可以整合网络中的碎片化带宽，提升带宽利用率，使网络中可以容纳更多数目的流。同时，利用petri网建模，解决流迁移过程中的一致性更新问题。
本发明采用的技术方案为：
一种sdn环境下保证服务质量的流量调度方法，包括以下步骤：
(1)当接收到用户预约的新业务流时，如果无法直接加入网络，则重新计算网络中所有业务流的传输路径信息，确定流量调度方案；
(2)确定流量调度方案后，根据计算出的传输路径信息和原始传输路径信息构建依赖图，决策流表更新顺序；
(3)进行依赖图更新，若更新过程中发现死锁环路的问题，则通过环路检测，将产生死锁的交换机节点提交至控制器协助转发，同时将链路带宽信息进行更新。
其中，步骤(1)具体包括以下步骤：
(101)用户预约的新业务流s进入网络时，计算新业务流s的最短路径，并判断是否可以直接加入网络，如果可以，则结束，否则执行步骤(102)；
(102)将包括新业务流在内的所有业务流进行全排列，并将网络中所有链路带宽资源设为初始值；其中全排列顺序为带宽从大到小，全排列序列中第一条业务流为父节点，其余业务流为叶子节点，首先按全排列序列指定的流顺序进行处理；
(103)对于第i条流，计算源节点到目的节点的最短路径；设其所需带宽为bi，源交换机为ui，目的交换机为vi，前i-1条流加入网络之后，对于网络拓扑上的任意一条链路e(u,v)，设be(u,v)为该链路被前i-1条流已经占用的带宽，则该链路满足公式ce(u,v)-be(u,v)≥bi约束：其中
(104)对于第i条流，如果存在源节点到目的节点的满足带宽的传输路径，则更新链路带宽使用情况，执行步骤(105)；如果否，则将叶子节点进行重新排列得到新的全排列序列，将新的全排列序列中父节点的下一个叶子节点作为第i条流，进行步骤(103)；
(105)检测全排列序列是否遍历完成，如果是，则结束；如果否，则对该序列下一个叶子节点的业务流进行步骤(103)。
其中，步骤(2)具体为：创建链路节点和流节点的依赖图，然后对业务流按照占用带宽进行排序；其中，链路节点表示为((u,v),b)，其中u,v为链路的相邻节点，b为该链路当前剩余带宽，流节点表示为(fi,bi)，其中fi为第i条流，bi为该流所需带宽；依赖图中每个流节点前后分别为它的新旧传输路径中依赖的链路节点。
其中，步骤(3)具体包括以下步骤：
(301)选择占用带宽最大的节点，然后查看其前置链路剩余带宽是否能够满足迁移需求；如果可以，完成流的迁移并更新对应的前置和后置链路节点，从迁移流节点集合中删除该节点；如果否，则从剩余节点中选择占用带宽最大的节点重复步骤(301)；
(302)检查流节点集合大小是否发生变化，如果大小没变，说明发生死锁，利用控制器作为带外传输点协助转发流量；如果集合元素减少，执行步骤(303)；
(303)检查迁移流节点集合中是否还有元素，如果有，重复步骤(301)至(302)直至集合为空；否则向交换机节点下发控制器协助转发的业务流的流表。
其中，步骤(302)中控制器作为带外传输点协助转发流量，具体处理过程为：依赖图更新的过程中，由于链路带宽剩余不足导致无法移动任何一条业务流，在产生死锁的若干条业务流中，决策出一条或者多条流将其暂时性上传至控制器，由控制器协助转发，直接将数据包转发至目的交换机节点，直至死锁的环路解开，然后控制器下发这些业务流的新的传输路径上的交换机流表，至此完成所有业务流的传输路径的更新。
本发明相比现有技术的优点为：
(1)本发明首先利用sdn控制器对全局资源的掌控特性，重新分配全局带宽资源，部署业务流的传输路径，通过整合带宽资源碎片，使得网络中可以容纳更多数目的流。
(2)本发明在传输路径发生变化后，相应的流表需要进行更新，流表的动态更新会引发流量黑洞、链路拥塞、环路等一致性更新问题，该系统通过petri网建模仔细协调各个交换机规则更新顺序。
(3)本发明借助带外的传输路径，短时间内将控制器视为一个转发节点，在保证低丢包率的前提下完成一致性更新。
(4)本发明利用令牌桶算法限制流出网络的流量，保证各条业务流之间带宽占用不会互相抢占，始终满足其需求带宽。
(5)利用本发明可以整合网络中的碎片化带宽，提升带宽利用率，使网络中可以容纳更多数目的流。同时，在流动态切换传输路径的时候，保证流表的一致性更新。
附图说明
图1是本发明系统总体架构示意图；
图2是基于qos的路由算法流程示意图；
图3是一致性更新算法流程示意图；
图4是流迁移示意图；
图5是流迁移死锁示例图；
图6是sdn主机通信方式示意图。
具体实施方式
下面将结合附图对本发明作进一步的阐释说明
图1是系统总体架构图，在应用层101中，系统在sdn环境下运行。在控制层102中基于qos的路由模块首先根据新流预约信息，计算网络中所有业务流的新的传输路径，确定流量调度方案，并将计算出的路径信息和原始路径信息传递给一致性更新模块。然后，一致性更新模块针对流的动态迁移，决策流表更新顺序，同时通过南向接口向转发层103的交换机下发相应的更新流表，交换机流表安装完后后，数据包将会按照新的路径进行传输。在出现死锁问题无法完成所有业务流的路径更新时，该模块将当前业务流依赖信息提交至冲突处理模块进行处理。冲突处理模块通过环路检测，将产生死锁的节点暂时提交至控制器协助转发，同时将一致性更新模块中的链路带宽信息更新。节点流量整形模块作为一个独立的模块负责端节点流量限速，限制各条业务流进入网络的速率，保证各个业务流之间互不侵占带宽，避免链路拥塞。
图2是基于qos的路由算法流程示意图。
步骤201，开始，新流s预约进入网络。
步骤202，计算s最短路径。
步骤203，判断是否可以直接加入网络，如果用户可以直接加入，则结束。如果用户预约的新流不能直接加入当前网络中，则进行步骤204。
步骤204，将包括预约流在内的所有业务流进行全排列，网络中所有链路带宽资源为初始值。其中全排列顺序为带宽从大到小，全排列序列中第一条业务流为父节点，其余业务流为叶子节点，首先按全排列序列指定的流顺序进行处理；
步骤205，对于第i条流，计算源节点到目的节点的最短路径；设其所需带宽为bi，源交换机为ui，目的交换机为vi，前i-1条流加入网络之后，对于网络拓扑上的任意一条链路e(u,v)，设be(u,v)为该链路被前i-1条流已经占用的带宽，则该链路满足公式ce(u,v)-be(u,v)≥bi约束：其中
步骤206，对于第i条流，如果存在源节点到目的节点的满足带宽的传输路径，则进行步骤208更新链路带宽使用情况，然后进行步骤209。如果否，进行步骤207，回溯至与其具有公共父节点的下一个全排列序列，将父节点的下一个节点作为第i条流，然后进行步骤205。例如：3，2，1分别为三条流占用的带宽，初始序列为3，2，1。假如该序列计算为3，2找到路径，1找不到，那么考虑3，1，2的顺序。因为一条流占用的是多条链路，所以可能让2换一条传输路径，就可以容纳所有的流。在这个例子中，3为父节点，2，1和1，2为两个子序列；
步骤209检测该序列是否遍历完成，如果是，则结束；如果否，则进行步骤210，i＝i 1，然后返回步骤205。
图3是一致性更新算法流程示意图。
步骤301，创建创建链路节点和流节点的依赖图，然后执行步骤302。
步骤302，对流量按照占用带宽进行排序。
步骤303，选择占用带宽最大的节点，紧接着执行步骤304；
步骤304，查看其前置链路剩余带宽是否能够满足迁移需求。
如果可以，执行步骤305完成流的迁移并进行步骤306、307更新相关前置后置链路节点，从迁移流节点集合中删除该节点。举例说明如何流迁移顺序决策，如图4所示。设定网络中每条链路的带宽初始值为10m，网络中共存在四条流，f1，f2，f3，f4，分别占用带宽6m，6m，10m，4m，流迁移前后对应的传输路径如图4所示，迁移的过程中，如果随机按照某个顺序更新流表，例如(f1，f2，f3，f4)，那么链路(s1，s5)和(s2，s5)会在更新的过程中出现链路拥塞，这可能会造成丢包或者增大时延，无法保证业务流的服务质量。通过petri网模型可以找到一个合理的更新顺序从而避免上述问题的发生。
如果否，则选择占用带宽次大的节点重复步骤303。
步骤308检查流节点集合大小是否发生变化，如果大小没变，说明发生死锁，执行步骤309、310利用控制器作为带外传输点协助转发流量，更新前置、后置节点剩余带宽资源。流迁移死锁产生示意如图5所示，三条流由于互相等待对方释放占用带宽，产生死锁，均无法进行流量迁移。
如果集合元素减少，执行步骤311，检查流节点集合中是否还有元素，如果有，重复步骤303至308直至集合为空；否则执行步骤312下发控制器协助转发的业务流的流表。
图6是sdn环境下主机通信方式示意图。
主机h1402产生数据包之后，传输给与其直接相连的openflow交换机403，openflowswitch1403收到数据包之后，没有相关流表处理该数据包，因此产生一个packet-in消息通过安全信道将数据包上传至控制器401，控制器401根据数据包的信息包括源ip地址、目的ip地址、源mac地址、目的mac地址等决策数据包的传输路径，然后下发携带流表信息的flow-mod消息至传输路径上的所有openflow交换机404，安装新的流表项，指导数据包在转发层的传输，同时将携带数据包信息的packet-out消息封装完成后发送给openflowswitch1403。在更新流表出现死锁的时候，本文提出的方案是在产生死锁的若干条业务流中，找出环路中一条或者多条流将其暂时性上传至控制器401，由控制器401协助转发，直接将数据包转发至目的交换机，直至死锁的环路解开，然后控制器401下发这些流的新的传输路径上的交换机流表。最终传输给主机h2403。
以上所述仅为本发明专利优选实施例而已，并不用于限制本发明专利，对于本领域的技术人员来说，本发明专利可以有各种更改，组合和变化。凡在本发明的精神和原则之内，所作任何修改、等同替换、改进等，均包含在本发明的保护范围之内。
1.一种sdn环境下保证服务质量的流量调度方法，其特征在于，包括以下步骤：
(1)当接收到用户预约的新业务流时，如果无法直接加入网络，则重新计算网络中所有业务流的传输路径信息，确定流量调度方案；
(2)确定流量调度方案后，根据计算出的传输路径信息和原始传输路径信息构建依赖图，决策流表更新顺序；
(3)进行依赖图更新，若更新过程中发现死锁环路的问题，则通过环路检测，将产生死锁的交换机节点提交至控制器协助转发，同时将链路带宽信息进行更新。
2.根据权利要求1所述的sdn环境下保证服务质量的流量调度方法，其特征在于，步骤(1)具体包括以下步骤：
(101)用户预约的新业务流s进入网络时，计算新业务流s的最短路径，并判断是否可以直接加入网络，如果可以，则结束，否则执行步骤(102)；
(102)将包括新业务流在内的所有业务流进行全排列，并将网络中所有链路带宽资源设为初始值；其中全排列顺序为带宽从大到小，全排列序列中第一条业务流为父节点，其余业务流为叶子节点，首先按全排列序列指定的流顺序进行处理；
(103)对于第i条流，计算源节点到目的节点的最短路径；设其所需带宽为bi，源交换机为ui，目的交换机为vi，前i-1条流加入网络之后，对于网络拓扑上的任意一条链路e(u,v)，设be(u,v)为该链路被前i-1条流已经占用的带宽，则该链路满足公式ce(u,v)-be(u,v)≥bi约束：其中
(104)对于第i条流，如果存在源节点到目的节点的满足带宽的传输路径，则更新链路带宽使用情况，执行步骤(105)；如果否，则将叶子节点进行重新排列得到新的全排列序列，将新的全排列序列中父节点的下一个叶子节点作为第i条流，进行步骤(103)；
(105)检测全排列序列是否遍历完成，如果是，则结束；如果否，则对该序列下一个叶子节点的业务流进行步骤(103)。
3.根据权利要求1所述的sdn环境下保证服务质量的流量调度方法，其特征在于，步骤(2)具体为：创建链路节点和流节点的依赖图，然后对业务流按照占用带宽进行排序；其中，链路节点表示为((u,v),b)，其中u,v为链路的相邻节点，b为该链路当前剩余带宽，流节点表示为(fi,bi)，其中fi为第i条流，bi为该流所需带宽；依赖图中每个流节点前后分别为它的新旧传输路径中依赖的链路节点。
4.根据权利要求3所述的sdn环境下保证服务质量的流量调度方法，其特征在于，步骤(3)具体包括以下步骤：
(301)选择占用带宽最大的节点，然后查看其前置链路剩余带宽是否能够满足迁移需求；如果可以，完成流的迁移并更新对应的前置和后置链路节点，从迁移流节点集合中删除该节点；如果否，则从剩余节点中选择占用带宽最大的节点重复步骤(301)；
(302)检查流节点集合大小是否发生变化，如果大小没变，说明发生死锁，利用控制器作为带外传输点协助转发流量；如果集合元素减少，执行步骤(303)；
(303)检查迁移流节点集合中是否还有元素，如果有，重复步骤(301)至(302)直至集合为空；否则向交换机节点下发控制器协助转发的业务流的流表。
5.根据权利要求4所述的sdn环境下保证服务质量的流量调度方法，其特征在于，步骤(302)中控制器作为带外传输点协助转发流量，具体处理过程为：依赖图更新的过程中，由于链路带宽剩余不足导致无法移动任何一条业务流，在产生死锁的若干条业务流中，决策出一条或者多条流将其暂时性上传至控制器，由控制器协助转发，直接将数据包转发至目的交换机节点，直至死锁的环路解开，然后控制器下发这些业务流的新的传输路径上的交换机流表，至此完成所有业务流的传输路径的更新。
技术总结