OFFICER——>转发规则放置问题
——>什么是规则放置问题？
一组规则如何放置到容量有限的交换机上，以满足上层应用的策略（ACL、流转发）。规则用来匹配流，其action是策略的执行者。这里研究的交换机可以是一个交换机（规则缓存问题考虑规则依赖，如cacheflow），也可以是一组以路径形式的交换机。（本文是后者）
对于那些匹配不到的流执行默认规则（优先级最低），可以丢弃，转发到控制器，转发到下一跳节点，不同的问题具体分析。
研究的方向有三种：
- 对规则进行压缩
- 对交换机容量进行改进
- 对规则进行分割和分配
规则的来源也使问题分为不同的场景：
- 规则和路由策略由运营商预先给定：ACL问题
- 规则决定流的路由策略（作为输出）：流转发规则问题
——>下面首先介绍两个概念：
- Endpoint Policy 端点策略：决定流的出口链路（ egress links），本文的流只有一个单出口，不考虑流的分割问题。
- Routing Policy 路由策略：使不同流的数据包通过不同的路径到达他们指定的出口链路。本文是宽松的路由策略（relaxing routing policy）
宽松的路由策略：流的转发不必遵循严格的转发路径，只要符合流需要转发到的出口。对于那些由于容量不足不能处理的流交给控制器。
以上两个策略是转发规则的放置问题（Forwarding Rules Distribution）的重要组成部分。
——>什么是转发规则的放置问题呢？
由于使用路径（路由）的形式转发端点策略的数据包不影响转发性能。因此，在不违背端点策略的前提下，想办法使流通过更好的路径上来转发到指定出口，以满足优化目标。
简单来说：就是在网络中流量转发的场景下，如何安放合适的规则。
文本OFFICER就是其中一类模型，下面以小见大的介绍：
——>OFFICER模型的归类：
- 该模型属于规则放置问题中的规则分割与分配（Split and Distribution）一类（也有规则压缩的部分思想，默认规则转发以节省规则）。其中，规则分割与分配模型分为：1）ACL规则放置（Access Control Rules Distribution）和2)转发规则放置（Forwarding Rules Distribution）
- 该模型是转发规则的放置问题，不是ACL规则的放置。
- 该模型是主动放置问题，不是被动放置问题。
- 注：以上总结于：《Rules Placement Problem in OpenFlow Networks: A Survey》
——>主动放置问题和被动放置问题的区别：
- 就是端点策略是否提前定义好，流是否提前知道。
- 主动放置问题：Proactive，在流到达前规则已经放好。流不可知。流可以减少延迟和控制信道开销。主要用于ACL问题。Palette、OneBigSwitch等。
- 被动放置问题：Reactive，按需放置。流不可知。来一个流安放对应的规则。适用动态的流转发问题。各种主流控制器：NOX、Floodlight、OpenDaylight等。
——>ACL规则放置和转发规则放置的区别：
从端点策略来区别：ACL规则放置是直接对规则集优化，忽略了网络中流对规则的影响。也就是说ACL端点策略中的规则（聚合规则，可以是通配符，图5（a）（b）所示）是给定好的，怎么把这块规则集分配到指定的路径上（图6所示）。而转发规则放置根据流量来生成规则（OFFICER单目的地址，不需要考虑分割问题，例子中的图所示），然后放到自己优化模型的路径上。
从路由策略来区别：，（宽松）路由策略是转发规则放置（OFFICER模型）的输出（端点策略则一直都是输入），通过制定路由策略来放置规则，以满足优化目标。而ACL问题的路由策略基本上是输入。
- 从主动或被动放置规则来区别：ACL问题一般都是主动放置问题，因为规则访问控制都是预先定义好的，不受流的影响。而转发问题可以是主动也可以使被动，但是主动时流，即端点策略需要提前定义好。
- ACL只约束容量；而转发问题（OFFICER模型）的约束条件主要限制链路带宽，容量次要，因为通过默认路径转发。
可以看出，在转发规则的放置问题中如何选择好的路径（路由策略）是关键。因此，不同的模型有不同的路由策略。
——>举个例子：
eg1：一个简单的网络拓扑中，有8个交换机。其中，入口链路有东、西两个，出口链路有南、北两个。
- a）模型的优化目标：最短路径。需要15个规则。
- b）模型的优化目标：最少化规则。需要9个规则。
- c）模型有约束条件：交换机容量限制。每个交换机只能存放两个规则。
其中，OFFICER模型类型于b）的问题。
——>OFFICER模型的主要思想：
OFFICER treats the network as a black box that must satisfy the endpoint policy imposed by the operator and tries to get the maximum from the available resources by adapting the routes followed by the different packets towards their desired egress links.
- modeling the network as a black box respecting the endpoint policy
- getting the maximum from the available resources by relaxing routing policy, the rest of the traffic that cannot be installed is routed on a default path
这里提出了默认路径（default path）的概念，是本文的创新点。
——>什么是默认路径？
就是从入口链路，经过某些交换机，到控制器的路径。如下图
——>默认路径的作用：
- ①并不是每个流都符合端点策略。②由于容量不足，安放不了流对应的规则，对于不符合上面情况的流转发到控制器，交给控制器处理。这就是为什么默认路径从入口链路开始。
- 默认路径有默认规则可以转发到默认的下一跳节点。如果流经过默认路径，可以减少转发规则的安放（压缩规则的意思）。这是本文OFFICER算法的核心思想，后面会详细的分析。
——>再举个例子：
eg2：如下图是线性结构的网络拓扑。所有交换机节点都连接到出口节点E，链路左端是入口节点，右端是控制器。默认路径从入口节点到控制器。
假设在这个拓扑中的端点策略，需要至少100个规则才能使所有的流转发出去而不经过控制器。现在考虑三种模型：
- Palette模型：根据最短路径（A——>E）的策略，所有的流都可能进过A、E，也就是说A、E的容量要满足至少100个规则才行。又因为拓扑中有4条路径到E，则至少需要安装400个规则。
- OneBigSwitch模型：拓扑中所有到E的4条路径：A——>E，A——>B——>E，A——>B——>C——>E，A——>B——>C——>D——>E。根据该模型均分的策略，每条路径（交换机）不超过25个规则。
- OFFICER模型：该模型也能满足所有的流转发。并且即使在网络资源匮乏的情况下（容量不足，交给控制器处理），属于under-provisioned networks情况下。而前两个模型是 best provisioning of the network情况，即网络资源已经预设好满足流。
本文提出：
- 一个整数线性规划的规则放置模型。
- 由于该模型是NP-hard问题，提出了一个启发式算法—— OFFICER，在约束条件的限制下，最大化网络中流的满意度。
下面依次介绍。
线性规划模型
——>各种符号的定义：
- 其中A是0-1矩阵。行代表不同的流F，列代表不同的链路L。
- α
f
,
l
表示第f个流是否在第l个链路上。是矩阵中的元素，取值{0,1}。
约束条件
优化模型的约束条件有：转发约束（避免环路，forwarding loops）， 链路带宽约束（bandwidth overload），节点容量约束（memory overflow），端点策略约束（endpoint policy）。
优化目标
分为两种情况：
- Minimizing memory usage：在交换机容量未知的情况下，最小化规则数
- Maximizing traffic satisfaction：在交换机容量已知的情况下，最大化流量的价值**
一、最小化规则数
目标函数：
约束条件：
- 增加约束（10），是对约束（8）重新定义。避免流转移到控制器，以减少规则数。
- 交换机容量未知，可以可以不考虑容量约束，约束（5）（6）设置为 ∞。或者由于条件限制，容量设置为Cs。
二、最大化流量的价值
目标函数及约束：
- 这里的w
f
,
e
表示流f在出口链路e上的收益值gain（权重）
- 如果只考虑最大化流量，则w等于流f的速率p
——>优化目标转化为：
The problem then becomes how to allocate rules so as to maximize the gain from the traffic exiting the network at egress link e(the rest of the traffic is forwarded to the controller over the default path).
OFFICER算法
由于线性模型是一个NP-hard问题，无法在多项式时间内解决。本文提出了一个启发式算法——OFFICER。
首先，提出了偏转技术（Deflection technique），与前文提到的默认路径联立。
Our idea is to forward packets of a flow on the shortest
path between the egress point of the flow and one of the nodes
on the default path.
思想：在默认路径节点和出口之间找最短路径。因为默认路径的转发不需要安放规则（有默认规则），只需在两者之间的偏转部分安放规则。而且偏转路径越短需要安放的规则越少。
——>有三种找最短偏转路径的策略：
- Closest first (CF)：入口链路和默认路径间的最短路径。
- Farthest first (FF)：控制器和默认路径间的最短路径。
- Closest to edge first (CE)：出口链路和默认路径间的最短路径。一般用这种策略。
——>例子：
——>伪代码：
该算法是贪心算法。最大化流的累计权值w。
算法的时间复杂度主要是对流的排序，O(|F| · log(|F|))。
改进：通常情况下，在数据中心有大量的流构成了一个巨大的矩阵A，这无疑增加了算法的时间复杂度。为此，我们可以忽略老鼠流，只考虑大象流的权值。
仿真实验
有四种因素会影响矩阵A： the topology, the traffic workload,
the controller placement, and the allocation algorithm。
拓扑：文中给出了仿真的四种拓扑类型
负载：对每个拓扑，随机产生24个负载。
控制器与默认路径的位置：
- the most centralized position (i.e., the node that has minimum total distance to other nodes, denoted by MIN)
- least centralized position (i.e., the node that has maximum total distance to other nodes, denoted by MAX)
算法类型：
- Random Placement (RP)：流量的权重随机，偏转点位置随机。
- Optimum (OP)：使用CPLEX计算上午中的整数线性模型的最优化
- OFFICER算法
前两个是参考标准。
——>流量在路径中的执行率
- x轴代表一个流最多可以放的规则数
- y轴代表流在路径的执行率
- points indicate the value of the metric of interest if all flows are delivered to their egress link when (i) strictly following the shortest path and denoted with a square and (ii), if ever computable, when minimizing memory usage as formulated in Sec. III-A and denoted with a circle.
——>路径的拉伸度
聚合规则会出现规则依赖问题，所以，增加限制条件：一个流只能有一个规则。
但是，由于带宽的限制，一个流往往并不只有一个路径。
当一个流需要转发到几个不同的出口，怎么办？①重新定义流②给流增加多个标签。
通过OFFICER模型的启发式算法，我们得到了一个优化的流矩阵A（|F|-by-|L+| binary matrix）。但是对于一个大型的网络拓扑，流矩阵A的规模将十分巨大，无法实际处理。同时TCAM节点的容量有限。——>如何减少A的规模呢？
请看下节： aOFFICER: Adaptive OpenFlow Rules Placement
引用：
- Nguyen, Xuan Nam, et al. “OFFICER: A general optimization framework for OpenFlow rule allocation and endpoint policy enforcement.” Computer Communications IEEE, 2015:478-486.
- Nguyen, Xuan Nam, et al. “Optimizing rules placement in OpenFlow networks: trading routing for better efficiency.” The Workshop on Hot Topics in Software Defined NETWORKING ACM, 2014:127-132.
- Nguyen, Xuan Nam, et al. “Rules Placement Problem in OpenFlow Networks: A Survey.” IEEE Communications Surveys & Tutorials 18.2(2016):1273-1286.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
