SDN中基于负载均衡的最优路径分配算法研究.PDF

第３３卷第８期 计 算 机 应 用 研 究 Ｖｏｌ３３Ｎｏ８ ２０１６年８月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ａｕｇ．２０１６ ＳＤＮ中基于负载均衡的最优路径分配算法研究 王春枝，罗　晨，陈宏伟 （湖北工业大学计算机学院，武汉４３００６８） 摘　要：针对传统网络控制与转发的紧耦合，其路径分配算法的全局性差、实时性不足，根据软件定义网络的集 中控制，提出一种基于马尔可夫链负载均衡（Ｍａｒｋｏｖｃｈａｉｎｌｏａｄｂａｌａｎｃｉｎｇ，ＭＣＬＢ）算法。该算法使用马尔可夫链 的转移概率计算链路重要性，并同时对业务流请求量和网络负载均衡率两个目标进行优化，获得多请求下的最 优路径分配。通过大量实验对比表明，该算法优于传统ＳＰＦ（ｓｈｏｒｔｅｓｔｐａｔｈｆｉｒｓｔ）算法，最大可以增加网络负载均衡 率３０％，提升网络业务流请求接受率２０％，达到了负载均衡效果，提高了网络的性能。 关键词：软件定义网络；路径分配；业务流请求；负载均衡；马尔可夫链 中图分类号：ＴＰ３９３０７　　 文献标志码：Ａ　　 文章编号：１００１３６９５（２０１６）０８２４６２０５ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１６．０８．０４９ ＯｐｔｉｍａｌｐａｔｈａｌｌｏｃａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｌｏａｄｂａｌａｎｃｉｎｇｆｏｒＳＤＮ  ＷａｎｇＣｈｕｎｚｈｉ，ＬｕｏＣｈｅｎ，ＣｈｅｎＨｏｎｇｗｅｉ （ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＨｕｂｅｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００６８，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｔｈａｔｐａｔｈａｌｌｏｃａｔｉｏｎａｌｇｏｒｉｔｈｍｈａｓｐｏｏｒｇｌｏｂａｌｉｔｙａｎｄｌａｃｋｏｆｒｅａｌｔｉｍｅｉｎｔｈｅｔｉｇｈｔｌｙｃｏｕｐｌｅｓｏｆ ｔｒａｄｉｔｉｏｎａｌｎｅｔｗｏｒｋｃｏｎｔｒｏｌａｎｄｆｏｒｗａｒｄｉｎｇ，ｔｈｅｐａｐｅｒｕｓｅｄｃｅｎｔｒａｌｉｚｅｄｃｏｎｔｒｏｌｏｆｓｏｆｔｗａｒｅｄｅｆｉｎｅｄｎｅｔｗｏｒｋｉｎｇ（ＳＤＮ）ｔｏｐｒｏｐｏｓｅ ｔｈｅＭＣＬＢａｌｇｏｒｉｔｈｍ．ＴｈｅｍｅｔｈｏｄｃａｌｃｕｌａｔｅｄｌｉｎｋｉｍｐｏｒｔａｎｃｅｂｙｔｒａｎｓｉｔｉｏｎｐｒｏｂａｂｉｌｉｔｙｏｆＭａｒｋｏｖｃｈａｉｎ，ａｎｄｏｐｔｉｍｉｚｅｄｔｈｅ ｂｕｓｉｎｅｓｓｆｌｏｗｒｅｑｕｅｓｔｑｕａｎｔｉｔｙａｎｄｔｈｅｌｏａｄｂａｌａｎｃｅｒａｔｅｏｆｎｅｔｗｏｒｋｓｉｍｕｌｔａｎｅｏｕｓｌｙｔｏｇｅｔｏｐｔｉｍａｌｐａｔｈｉｎｍｕｌｔｉｒｅｑｕｅｓｔｓ．Ｌａｒｇｅ ｅｘｐｅｒｉｍｅｎｔｒｅｓｕｌｔｓｃｏｍｐａｒｉｎｇａｎａｌｙｓｉｓｐｒｏｖｅｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｉｓｓｕｐｅｒｉｏｒｔｏｔｈｅｔｒａｄｉｔｉｏｎａｌＳＰＦ（ｓｈｏｒｔｅｓｔｐａｔｈｆｉｒｓｔ）ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈｃａｎｉｎｃｒｅａｓｅｔｈｅ３０％ｎｅｔｗｏｒｋｌｏａｄｂａｌａｎｃｅｒａｔｅａｎｄ２０％ｂｕｓｉｎｅｓｓｆｌｏｗｒｅｑｕｅｓｔａｃｃｅｐｔａｎｃｅｒａｔｅｉｎｓｏｍｅｃａｓｅｓ．Ｔｈｅｐｒｏ ｐｏｓｅｄａｌｇｏｒｉｔｈｍａｃｈｉｅｖｅｓｔｈｅｅｆｆｅｃｔｏｆｌｏａｄｂａｌａｎｃｉｎｇａｎｄｉｍｐｒｏｖｅｓｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｎｅｔｗｏｒｋ． Ｋｅｙｗｏｒｄｓ：ｓｏｆｔｗａｒｅｄｅｆｉｎｅｄｎｅｔｗｏｒｋｉｎｇ；ｐａｔｈａｌｌｏｃａｔｉｏｎ；ｂｕｓｉｎｅｓｓｆｌｏｗｒｅｑｕｅｓｔ；ｌｏａｄｂａｌａｎｃｉｎｇ；Ｍａｒｋｏｖｃｈａｉｎ