SDN 网络中的路由规则（三）-修正版

1.写在前面

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

2.优化目标

当我们说我们要优化一个网络，我们在说什么？
最优化是一个横向延展很宽的领域，在计算机和网络科学的研究中扮演着一个往来频繁的门客。在我目前所读到的90%的文献中，都存在着优化目标，以及基于这一目标（high-level object）的数学建模分析。

回到主题，我的研究内容是路由规则的放置，那目标该是什么呢？
有的研究者是假设流已知、端点规则（即流应该被正确地从入口转发到出口）和路由规则给定，试图使内存占用最小化——路由聚合[1]；有的研究者是假设流已知，端点规则给定，交换机内存和链路容量给定，试图构造路由规则（算法）以使得流收益最大（还有一些基本假设：对应每个出口的流权重不同，它试图优先满足权重更高的流）[2]；有的研究者假设流已知，端点规则给定，交换机内存和链路容量给定，要最大化能源节约量[3]。

然而，我要做的有三个基本目标，同时也是相互矛盾的目标：
假设流已知，构造路由规则，使得最大的链路利用率最小化，最大的交换机内存占用最小化，最大流时延（即入口到出口的转发跳数）最小化。
可能需要解释一下为什么要以这三个目标为优化目标，说白了它们也都是流量工程中的重要目标。
min(max(αl)) 的意义在于负载均衡,其中
αl=TlCl(αl≤1,l∈Links) 为链路利用率， Tl 为经由链路 l=(u,v) 上的流数目， Cl 为链路 l 的容量。链路利用率一般不超过0.5为宜。 Tl 的计算方法后面会再描述。

min(max(αs)) 的意义在于分散风险，当一个交换机宕机时不至于损失过大（也可以认为是负载均衡），其中
αs=TuCu(α≤1,u∈Nodes) 为交换机内存占用率， Tu 为安装在交换机 u 上的规则数， Cu 为交换机 u 的规则安装内存大小。

min(max(d)) 的意义在于：当流时延被限制为某一临界值时（时延超过这一值即认为该流寻路失败），能够损失最少的流。

3.数学建模

我们将符号化描述将要涉及到的规则放置问题：
NotationFSSeS+LIEL+N+(s)⊆S+N−(s)⊆S+def(s)∈S+E(f)⊆EE∗(f)⊆ECsBlpfDescriptionset of flowsset of openflow switches composing the networkset of external nodes directly connected to the network but not part of the network to be optimizedset of all nodes, S+=S∪Seset of directed links,defined by (s,d)∈S×S,where s is the origin of the link and d is its terminationset of directed ingress links that connect external nodes to switches, defined by (s,d)∈Se×Sset of directed ingress links that connect switches to external nodes, defined by (s,d)∈S×Seset of all links, L+=L∪I∪Eset of incoming neighboring nodes of switch s∈Sset of outgoing neighboring nodes of switch s∈Snext hop toward the controller from switch s∈Sset of valid egress links for flow f∈F according to the endpoint policy E∗(f)=E(f)∪∗,where * denotes the set of links attached to the controller memory limitation of switch s∈Scapacity of link l ∈L+packet rate of flow f∈F

我们试图求解这样一个 |F|−by−|L| 的布尔矩阵 A=(af,l) ， af,l 表示一条流 f∈F 是否经过一条链路 l∈L+ ,若经过则 af,l=1 ,否则 af,l=0 。
注意： l=(u,v),u≠v,(u,v)∈S+×S+

则我们的最优化目标可以写成：

1. min(max(∑f∈Fpfaf,lBl,∀l∈L))

2. min(max(∑u∈N+(v)∑f∈Faf,(u,v)Cv,∀v∈S))

3. min(max(∑l∈L+af,l,∀f∈F))

即最小化最大元。

下面给出约束条件：

网络限制

∀f∈F,∀l∈L+,af,l∈{0,1} (1)

∀f∈F,∀s∈S,∑v∈N+(s)af,(v,s)=∑v∈N−(s)af,(s,v) (2)

限制(1)保证了 af,l 是0-1二进制数，限制(2)说明进入节点的流量也会离开节点（即入度等于出度）。

带宽限制

∀l∈L+,∑f∈Fpfaf,l≤Bl (3)

限制(3)说明经过一条链路上所有流的实际带宽之和应不大于该链路带宽。

内存限制

∀s∈S,∑u∈N+(s)\ def(s)∑f∈Faf,(u,s)≤Cs (4)

限制(4)说明经过一个非默认路径上的交换机的所有不同类型流数目应不大于该交换机（规则安装）内存大小。

端点规则限制

∀f∈F,∀l∈E\ E∗(f),af,l=0 (5)

∀f∈F,∑l∈E∗(f)af,l=1 (6)

限制(5)说明一条流离开网络只能通过有效出口链路或者是下一跳是控制器的链路，限制(6)说明一条流只能通过一个出口离开网络。

辅助限制

∀f∈F,∑l∈∗af,l=0 (7)

限制(7)是对限制(6)的补充，要求对于我们的优化问题而言，要阻止流通过控制器离开网络。

以下内容详见下篇。

4.拟采用的相关算法

5.NP-hard初步

6.启发式算法