将原始规则表分割成均等的C个子表，（其中图中最短路径的长度是C的上界）然后使用彩虹路径方法将子表放入交换机中，保证每条路径上都要有所有的子表。
decompose：如何分割使子表均等，且子表规则数最少→子表数最多，还要考略分割的质量（子表的大小是问题的关键）distribute：不同的拓扑图路径，如何考虑C，如何放入How to decompose a large table that contains all rules into a predetermined number of smaller tables.
将原始表分割成规定数量的子表。其中子表的大小应该近似均等。
定义每一个子表都代表一种颜色（color）分割要满足两点： Order-oblivious访问子表可以无序性（？）；Semantically-invariant子表不会改变原始表的语义有些规则不能分配，即表中的一些规则必须在指定的switch中（如r.p是讲packet发到指定的switch端口），是不安全的默认这里表中的规则都是安全的，可以被分配的两种类型的规则： 默认规则（default rule）：所有位都是*（通配符），优先级最低，用于如果没有匹配到其他规则，默认转发到下一跳switch，执行默认动作。分解时忽视默认规则。非默认规则（non-default rules）：普通的规则如何具体分割表？
——>两个分割方法：
Pivot Bit Decomposition（PBD）：基于轴点的分割Cut-Based Decomposition（CBD）：基于切割的分解迭代地，每次通过合适的轴点将表分割成两个子表。直到①达到指定的c个子表，或者②子表的规则数没有减少（即并没有比分割前的表少）结束迭代。
注意这里一次迭代会分割成两个子表。两个规则中最多的那个子表是最大子表。——>什么是轴点（pivot）？
指的是那些规则的位（bit）上是*的位点（e.g.如规则1*0，第二个位是轴点，规则可以被分解成100和110。）注意一个规则上可以有多个轴点，即可以被分解成多个规则（e.g.一个规则有P个轴点，则可以被分解成2 P 中新规则。表同理。）可知不同的一些轴点，可能会得到不同的子表。所有子表的结果由待分表和轴点共同决定——>如何选择合适的轴点（bit）以满足我们的目标？
目标：Our goal is to greedily minimize the maximum table size among all the small tables.
目标：最小化每个switch中最大子表的规则数量，来最大化子表（colors）的总量。
每次都选择最大的表开始分解分解轴点的选择：首先依次遍历该表中的所有bit[i，0-6]位（i代表第几列，轴点），其实就是依次横向预分解得到估计的最大子表（即两个表中规则数最多的那个做代表），最后从所有最大子表中选择规则数最少的那个作为最少最大子表→得到相应的轴点i→得到相应的可分解规则R。以实现目标——子表规则数最少（理解：最大子表的规则数都是最少的了，还有神马子表不是呢）每次迭代根据PBD分割的两个子表的规则数会大致相等轴点（pivot）公式： 若得到的最少最大子表规则没有减少，则拒绝该表的分割，跳到下一个表——>例子1：
各bit[i,0-6]上的最大子表规则数分别为：6、5、6、6 、6、 6Rule ϕ 2 has * in bit 1,and therefore it is duplicated to rule ϕ′ 2 = 001***0 and ϕ′′ 2 = 011***0.first sub-table：ϕ 1 , ϕ′ 2 , ϕ 6 and ϕ 7 second sub-table： ϕ′′ 2 , ϕ 3 , ϕ 4 , ϕ 5 and ϕ 7——> 证明
引理一：如果一个packet（h）在原始表中可以匹配一个非默认规则时→那么在PBD中，h也可以匹配的非默认规则只在一个子表中，其他所有子表匹配非默认规则（证明略，没看懂）引理二：如果一个packet（h）在原始表中匹配的是默认规则时→那么在PBD中，h可以匹配所有子表的默认规则
定理一：PBD可以保持原始表的语义，不管子表的被访问顺序
——>缺陷
若表规则数c不是2的整数倍数，会导致子表的规则数不均等了（？） 解决：取最大整数p，使p满足p 2 < c。一个子表取p 2 ，另一个子表取c - p 2 个可能会出现最大子表规则数不理想，是理论上的c倍（定理二） 证明：假设有一个原始表（N个规则）如下： 01111 10111 11011 11101 11110 按照1到c-1bits分割成c个子表 结果：c-1个一个规则的子表，剩下一个最大子表规则数为N-c+1（理想情况下：子表规则数N/c） 倍数约为：（N-c+1）/（N/c）≈ c，N足够大规则依赖公式|C u, v | = {i | b v i = * and b u i ≠ * } 其中 b u i denote the i-th bit of node u.
（理解：规则依赖即规则的重叠部分，这里C指的是低级规则对高级规则包含的通配符个数。依赖成本指的是若分割后需要添加的新节点（规则）的个数，注意与规则缓存中依赖成本是被依赖的规则数相区别。其实依赖本质上是一致的，只是量化的方式不一样：规则缓存是一起放入依赖规则；规则放置是将依赖规则放入多个交换机，需要分割）
各边上的权重（weight）代表分割这条边的成本：w(u, v)= |C u, v |−1
——>分割的原理
通过消除两规则之间的依赖关系来分割边
for each bit i in C u, v , we can write a rule that is identical to v, except the i-th bit that is replaced by 1 − b u i .
我们将重写|C u, v |个新的规则（节点）：第i位为1 − b u i 。这些规则是用来分割规则v的，因此与规则u不依赖了。总之添加了w个规则，并且这些新规则的成本也降低了。
定理三： Using the above-mentioned edge breaking and node expansion operations, CBD can exactly emulate PBD.
CBD方法事PBD方法的扩展。
在PBD中，没有packet可以都匹配两个子表中的不同规则。CBD也同理。
——>如何分割呢？
目标：
步骤：迭代地进行，每次迭代的步骤
我首先 使用METIS 划分（partition）出大小均为c的子图（子表），要使边的权重最小化根据划分的质量（是否超过参数权重w 0 ）来选择：若超过。则expand one of the rules, and then go to the next iteration（？）；若没有超过，则结束分割所有的依赖边（cut-edges，分割原理如上）（？这部分没有看懂，需要了解METIS算法）how to spread the subtables in the network？ ——>怎样将分割的子表放到网络中？
second subproblem is to ensure that each packet traverses all the types of small tables (i.e. all colors), so that the resulting setting would be semantically equivalent to a single lookup in the large table. ——>要使每个packet可以遍历到所有的子表（colors）
each path must contain all c colors. ——>就相当于每个路径（path）都必须要有所有的c个子表（colors）
定义一：the (G, P, c) RAINBOW PATH PROBLEM 将上述问题归纳成彩虹路径问题，即是否存在一个方案γ：使每条路径都能放入所有的子表。
G：一个给定的网络拓扑图 G =（V, E）P：流的路径集（path）P = {p 1 , … , p f }。其中 S(p i ) 代表路径中的switch，L(p i )代表路径中的链路c：分割后子表（colors）的数量目标：我们的目标是最大化子表的数量（上一章已经介绍：通过最小化子表的大小来最大化子表数量）
——>怎么判断方案γ是否存在？
结合定义一和目标，子表（colors）的数量最多不能超过最短那条路径（path）的容量。
如何具体判断？我们将问题划分为下一节的几点具体分析
下面具体分析各种情况下的方案γ（以下的分析是基于自己的理解得到的，如有错误之处请指正）
（x，y）是set P上的最短路径s是最短路径的容量大小单源树：所有路径都是从同一个节点x出发
可得定理五：
a valid color assignment γ with s+1 colors最短路径P是通过对网络拓扑图BFS（广度优先遍历）得到的，时间复杂度O (m + n)证明略，参考上图a一般情况下的树。path的起始点x不再确定，→即（x，y）不一定在树的一条分支上，→（x，y）可能有一部分有其他的path 共用。
可得定理六：
a valid color assignment with ⌈ s/2 + 1⌉ colors 时间复杂度O (m + n)证明（简单理解，见上图b）： 首先 d(y′, x) = d(x, y) + d(y, y′) ，因为树是无环的⌈ s/2 + 1⌉是怎么得到的？p1, p2 将p分为两个path，假设p1的长度大于p2，可得 |S(p1)| ≥ ⌈ s/2 + 1⌉。即p只能在其中一部分放最多 ⌈ s/2 + 1⌉个规则一般情况下，网络拓扑是复杂的图。
思路： At each iteration, which corresponds to a new color, GREEDY continuously picks uncolored nodes one by one, until each path contains at least one of the picked nodes in this iteration.
在每次迭代中，我们总选择那些①占有最多路径的（理解为最重要的交汇点，贪心思想）②所在路径还有未被颜色c染色的节点v（switch），用颜色c进行染色（即将子表放入switch中），直到每条路径都染上了颜色c，然后进行下一次迭代。若发现某条路径上节点都已被染色完，即颜色c染不上了，则终止迭代，方案失败。
注，第一次迭代总会成功的我们将算法分为两类：
1-GREEDY 每次只能选一个节点，满足上面①②要求 定理七：时间复杂度O (n 2 *f）= f · ((n − 1) + (n − 2) + … + 1) n是图中的节点数（switch），f是路径数 。q-GREEDY 每次可以选q个节点，其中至少要有一个节点满足①要求（②是默认满足的） 定理八：时间复杂度O ( n q + 1 · f）——>伪代码
3-16 第一个while循环是迭代操作，每次迭代使所有路径都要染上颜色c，否则迭代失败6-16 第二个while循环是在迭代中，找到满足条件①②的节点，进行染色。然后接着找下一个节点。时间t=((n − 1) + (n − 2) + … + 1)——>例子2 当q=1时，γ（V1,V2,V4）=1
(1)V=V1,V2,V4,V3;P＇=P=P1,P2,P3;V＇=∅; ①Vº=V1 Pº=P1,P2 V=V/Vº=V2,V4,V3;V＇=V1;P＇=P3 ②Vº=V2 Pº=P1,P3 V=V/Vº=V4,V3;V＇=V1,V2;P＇=∅ (2)V=V4,V3;P＇=P=P1,P2,P3;V＇=∅; ①Vº=V4 Pº=P2,P3 V=V/Vº=V3;V＇=V1,V2,V4;P＇=P1 ②在V中找不到路径集P＇上的节点——>Vº=∅→迭代失败当q=2时，γ（V1,V2,V3,V4）=2
(1)V=V1,V2,V4,V3;P＇=P=P1,P2,P3;V＇=∅; ①Vº=V2，V3 //V3不是最大的 Pº=P1,P2,P3 V=V/Vº=V1,V4;V＇=V2,V3;P＇=∅ (2)V=V1,V4;P＇=P=P1,P2,P3;V＇=∅; ①Vº=V1,V4 Pº=P1,P2,P3 V=V/Vº=∅;V＇=V1,V2,V3,V4;P＇=∅动态规划的思想
在一个switch中可以分配多个 colors
有三点好处：
有利于大容量的switch增加分配子表的灵活度 ratio=switch中的子表/总的子表数适用于短的路径非常短，长路径非常长的情况。 如果用 (G, P, c) 彩虹路径的方法，为了适应最短路径→只能有较少数量的子表→导致子表非常大→不能充分利用长路径的容量定义二：(G, P, c, d)RAINBOW PATH PROBLEM
其中d表示每个switch里能放最多d个colors例子3
若是单节点的彩虹路径，每个节点只能放一个相同颜色的color若是多节点的彩虹路径，则c=2。γ(V1) = {1, 2} ; γ(V2) ={2, 3} ; γ(V3) = {3, 1}。