SDN网络中的路由规则（四）

1.写在前面

因为毕业设计的缘故，准备向计算机方向读研的我偶然结识了SDN与Openflow这两个神奇的家伙。
SDN的中文名称为软件定义网络，然而它的英文拼写除了正规的文献和专业人员，几乎很少被正确地表示出来。
百度百科对它的解释就是一个看似正确的表率：Software Defined Network。
其实我一开始也是这么以为的（甚至一开始我的解读是 Software Definition Network），不过玩文字游戏实在是没什么意思：请大家以后不要再拼错了，SDN的全称是：Software-defined Networking！这是来自Wikipedia和SDN官方网站的定义。

2.优化目标

3.数学建模

注：以上两点请见上一篇文章

4.核心算法

（1）图算法——网络拓扑可用图表示，其中重点涉及到的有最短路径算法和遍历算法（深度优先和广度优先）；

5.NP-hard？

容易发现，许多文献中的最优化问题都是NP-hard问题，而求证NP-hard的原理是退化法，即对模型一步步弱化变量因素，使之退化为一个已知的NP-hard问题。接下来就是证明我所处理的优化问题，可以退化为一个已知的NP-hard问题：EAR。

重新列出第一优化目标如下： $min(max(frac{sumlimits_{f in F}p_fa_{f,l}}{B_l},l in L^+))$ (1)

第一步退化：令$p_f = 1,B_l=C$为常数，则优化目标变成： $min(max(sumlimits_{f in F}a_{f,l},l in L^+))$ (2)

第二步退化：用min替换max，则优化目标变成： $min(min(sumlimits_{f in F}a_{f,l},l in L^+))$ (3)

第三步退化：将目标（3）退化成EAR问题： $min(sumlimits_{l in L^+}x_l)$，$x_l = 0$ if there is no flow running on link l (4)

而根据以下这篇论文，可知EAR问题是一个NP-hard问题。

6.启发式算法

启发式算法的严格定义可以参照维基百科，链接如下：

而针对我们要解决的问题，三个优化目标的自然语言描述为：

但是在构造启发式算法之前，我们要坐而论道，什么道呢？

为了方便解决我们提出的优化问题，针对以上两个例子带来的启示，我必须做出如下两个重要假设：

这样，我们就能够既服从工程现实的需要，又服从整个优化问题了。

具体的启发式算法请见下一篇内容。

最后

以上就是可爱铃铛为你收集整理的SDN网络中的路由规则（四）的全部内容，希望文章能够帮你解决SDN网络中的路由规则（四）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。