Optimizing the “One Big Switch” Abstraction笔记

2019-11-06 09:07:12

字体：大中小

来源：转载

供稿：网友

rule-placement algorithm概述

主要介绍了一种规则放置算法（rule-placement algorithm）以达到“One Big Switch”的抽象。由于switch容量有限，将所有规则放入一组switch 集群中，以抽象成一个 big switch。

input：①端点策略（end-point policy）和②路由策略（routing policy），以及③网络拓扑（network topology）和④交换机容量synthesize by：规则放置算法（rule-placement algorithm）output：规则（forwarding rule）

其中：

Network topology: location (loc) 端口exposed locations 与外界相连的端口ingress loc （入口）和 egress loc （出口）

Endpoint policy (E): a PRioritized list of rules E ：[r1, …, rm] ，其中m = ||E||，表示相应的规则集规则集由大到小分为：整个所有的规则E——>划分成部分不重叠的规则集Ei $_i$ ——>打包到switch的规则集Eq $_q$ （用在Path algorithm的cover阶段）为方便描述分别定义为：整块矩形E；大矩形Ei $_i$ ；小矩形Eq $_q$

Routing policy (R): R(loc1, loc2, pkt) = si $_i$ 1 $_1$ si $_i$ 2 $_2$ …si $_i$ k $_k$ ，其中si $_i$ 1 $_1$ si $_i$ 2 $_2$ …si $_i$ k $_k$ 就是一条路径（path）（？）packet和path的关系？

Our rule-placement algorithm helps raise the level of abstraction for SDN by shielding programmers from the details of distributing rules across switches.

让控制平台管理规则的放置，而不需要应用程序或程序员来实现。他们只需要定义高水平的策略。

注：不存在规则依赖问题，因为一组有依赖的规则都全部放入一组交换机集群中——one big switch

rule-placement algorithm分析

算法概述算法分为三个阶段：

Decomposition (component 1)：将问题分解成多条路径Resource allocation (component 2)：估计每条路径上的交换机总容量，LP问题Path algorithm (component 3)：在每条路径上安装对应的端点策略Ei $_i$

一、Decomposition

we decompose the general rule-placement problem into smaller sub-problems.

输入条件：implementing {E, R} as implementing the routing policy R and a union of endpoint policies over the paths.

通过routing policy可以找出所有τ个路径。a union of endpoint policies是所有规则集E的总和

过程：E划分——>规则空间 Di $_i$ （相当于实际部分规则集Ei $_i$ ）——>映射到 Pi $_i$

More formally, we can associate path Pi $_i$ with a flow space Di $_i$ (i.e., all packets that use Pi $_i$ belong to Di $_i$ )and the projection Ei $_i$ of the endpoint policy on Di $_i$

在整个规则集中划出一块相应的规则空间Di $_i$ 给一条对应的路径，相当于大矩形Ei $_i$ 。——>按什么方式划分？怎么对应？

怎么划分？

根据数据包包头划出规则空间Di $_i$ 。如二维规则，提取指定的src_ip和dst_ip部分组成Di $_i$ 注意任意两个不相同的规则空间总是不相交的确定Di $_i$ 后，可以分别找到所有对应的实际部分规则集Ei $_i$ ，如下图所示这里写图片描述

怎么对应路径？即怎么确定路径Pi $_i$ 是否合适？端口在路径中已经确定

涉及到阶段二，如下

二、Resource allocation

①The goal of “allocation” phase is to find a global rule-space allocation,such that it is feasible to find rule placements for all paths.

②the feasibility of a rule-space allocation depends primarily on the total amount of space allocated to a path, rather than the portion of that space allocated to each switch.

③we estimate the threshold value for the Li $_i$ -hop path Pi $_i$ with endpoint policy Ei $_i$ .

我们首先定义一个阈值η作为估计Di $_i$ 中的规则数量：η=αi $_i$ ||Ei $_i$ ||。其中αi $_i$ 是Pi $_i$ 长度的线性比值。可知，影响规则空间的两个因素：

The size of endpoint policy ||Ei $_i$ ||The path length Li $_i$ ：每个switch都需要至少一个小矩形，小矩形越多开销越大

rule-space allocation分为两步：

估计Di $_i$ 中的规则数量：η=αi $_i$ ||Ei $_i$ ||通过LP，判断这条路径Pi $_i$ 是否合适

LP问题：这里写图片描述

每个节点switchi $_i$ 在所有路径Pj $_j$ 上的容量之和不超过100%每条路径Pj $_j$ 的所有switchi $_i$ 之和要≥ηj $_j$ i代表节点，j代表路径Xi, $_i,$ j $_j$ 代表switch中可用容量占比。如交换机容量C4 $_4$ =1000，X4, $_4,$ 3 $_3$ =0.4，则表示在P3 $_3$ 上S4 $_4$ 中可以放最多400个规则。

当检测失败时，增大ηi $_i$ ，再重新执行LP

三、Path algorithm（path-wise endpoint policy）

概述：

对于每一条路径，该算法分别（并行）将一块规则（小矩形）放入路径上的某个switch每个规则在路径上只需要一个（i.e. 每个packet在路径上只需要执行一次的r.a）——>规则在路径上可以灵活地移动注意放置规则之前，路径上的每个节点（switch）都要安放一条默认规则（优先级最低），用于当packet没有相对应规则（i.e. packet不在Di $_i$ 中）时，转发到路径的下一跳节点

这里写图片描述

该算法分为三步：

Cover：在打矩形中找到小矩形Eq $_q$ 。如何找？Pack：将大矩形和小矩形重叠部分的规则打包到switchReplace：用一条新规则（优先级最高）q^Fwd= (q, Fwd)代替小矩形中的规则集

注意两点：

放入的实际规则总是不少于Ei $_i$ 的规则集规则放入switch不能有遗漏

接上，如何找小矩形？——> 如何找到最好的candidate rectangles？即在大矩形Ei $_i$ （这里不是整块矩形E）中找到第一次需要pack的小矩形？ ——>转换成两个子问题：怎么选择小矩形？；如何找到小矩形？

（1）问题1：Rectangle selection 这里写图片描述

internal rules是完全与q重叠overlapping rules是部分与q重叠规则数量相同，选择utility最优的

（2）问题2：Top-Down search

To limit the search space, our algorithm avoids searching too deeply, preferring larger rectangles over smaller ones.we only consider those rectangles q such that there exists no rectangle q¹ which satisfies both of the following two conditions:(i) q is inside q¹ and (ii) Eq¹ $_q¹$ can be packed in the switch. We call these q the maximal feasible predicates.q规则数量要满足≤switch的容量ci $_i$ 搜索的矩形块由大到小，直到收缩到规则的边

（3）算法伪代码：这里写图片描述

2、找到所有≤di $_i$ 的最大可行矩形Q【Top-Down search 】3、在Q中选出最好效率的q【Rectangle selection】5和6、移除internal rules（注意：在新的E¹中不需要改overlapping的规则）。如下这里写图片描述

7、在E¹添加新的规则q^Fwd= (q, Fwd)

算法优化

对一些不需要的数据包（丢弃操作的）还传入下一跳节点将会增加不必要的成本

充分利用入端口的switch容量这里写图片描述节点越靠前，权重越大

转变打包顺序

This motivates us to reverse the order we place rules along a chain:here, we shall first pack the most refined rules at the last switch,and progressively pack the rules in upstream switches, making the ingress switch responsible for the biggest rules.

INCREMENTAL UPDATES

Local Algorithm：不需要改变Path，只插入、删除、改变规则Global Algorithm：Path改变

Rule-Space Utilization

开销问题：额外规则的ovehead

多个路径的开销——一个规则在多个路径上（情况较少）单个路径上的开销

引用：

Kang N, Liu Z, Rexford J, et al. Optimizing the “one big switch” abstraction in software-defined networks[C]// ACM Conference on Emerging NETWORKING Experiments and Technologies. ACM, 2013:13-24.

上一篇：Fedora 25 关于grub2的操作

下一篇：Web Service基础