Central Control Over Distributed Routing

0.ABSTRACT
1.Introduction
2.Flexible Fibbing
3.Augmenting Topology
4.Implementation
5.Reaction to Failures
6.Frequently Asked Questions
7.Related Work
8.Conclusion

0.ABSTRACT
中心路由选择虽然提升了灵活性,但是牺牲了分布式协议的健壮性。这篇文章提出了Fibbing(谎言),一种架构,在分布式路由上实现中心控制。Fibbing以一个潜在的链路状态路由协议欺骗结点和链路,使得路由器可以基于增长的拓扑计算他们的转发表。Fibbing是有表达性的,并且支持灵活的分路平衡、转发工程、且支持路由。基于高级转发需求,谎言控制器计算出一个紧凑的增长的拓扑并且通过标准路由协议信息注入欺骗元素。谎言可以与任何不可修改的支持OSPF协议的路由器兼容。我们的实验也显示了它可以通过转发需求、引进最小限制、快速反应网络状况和控制器的错误来扩大网络规模。

1.Introduction
作为网络管理员,怀疑网络上发生了denial-of-service attack(Dos)l,要检查网路,需要做:
1.孤立目标为这些ip地址的流
2.将它们直接交给洗涤器,如果需要就清洗他们。
3.通过路径平衡的方法利用未被使用的链路来降低拥塞。

这些工作在传统网络中非常难做。
因为,中间件和目的地离得很远,许多设备的配置需要修改,修正一个错误会改变规则使得其他地方又发生错误。

软件定义网络可以很容易地解决这些问题,因为它可以中心化并直接控制转发行为。然而,移除分布式路由协议又会造成一些问题。

可扩展性和可靠性会下降,由于所有工作都要由控制器来做,而分布式路由协议可以将这些工作分摊开。为了可扩展性和可靠性,SDN控制器必须地理上分布式重复放置,但这样又会产生管理控制其状态的挑战。而且现有网络难以大量向SDN过渡,故SDN目前只是小范围部署。

Fibbing欺骗路由器,让路由器以为链路中有一些不存在的结点或者链路,基于像OSPF或IS-IS这样的链路状态协议,让路由器计算转发路径。

他们做了如下工作:
1.抽象方面:展示了如何通过操作分布式链路状态路由协议去表达和实现高级转发需求。
2.算法方面:提出了新的、高效的算法去计算紧密增长的拓扑
3.实现方面:描述了一个完整的实现,在未被修改的Cisco和Juniper路由器上。
4.评估:展示了欺骗控制器在路由器上快速生成小的拓扑和路径。

2.灵活的Fibbing
DAG:Directed Acyclic Graph 有向无环图
Fibbing工作流有以下4个阶段,这4个阶段基于两个输入 :
1.一个希望做的事情(转发)的图,每个目标都有一个DAG
2.一个IGP拓扑。(interior Gateway Protocol,内部网关协议)
4个阶段如图:

Central Control Over Distributed Routing阅读笔记-LMLPHP

1.转发DAG的提供可以以直接的方式,也可以以不直接的方式,即以高级的方式,用一种简单的基于路径的语言。若采用后一种方式,在编辑阶段开始时会先将转发需求编辑为具体的转发DAGs。
2.随后,在拓扑扩展阶段计算出扩展的拓扑去实现这些DAGs。
3.计算扩展的拓扑很快,产生的结果可能会很大。于是在拓扑优化阶段(在不影响转发路径的情况下)削减拓扑。
4.注入及监视阶段将虚假信息转化为谎言由控制器注入网络。

这部分,我们呈现了高级的语言以及编辑的过程,并展示了Fibbing可以表达宽泛的转发行为。

2.1 Fibbing高级语言

Central Control Over Distributed Routing阅读笔记-LMLPHP

requirement:表达了传说应该如何向目的地进行的需求,或者表达了当IGP拓扑发生变化时传输应该如何进行的后备需求。

       每个路径需求都由路径需求的与、或递归定义。

       操作者可以用n个需求联合起来表达一个均衡分路的需求;同样也可以用这n个需求中的单独的一个来确保一个特定的传输目标。

       路径需求由许多节点需求的队列组成。

       一个节点需求可以是针对某个特定点的路由,也可以是对任意点队列都适用。

       与路径需求一样,点需求也可以用逻辑与、逻辑或结合起来定义。

       当没有点需求时,将会使用最初的IGP路径。这时,操作者不用表述所有未修改的路径,只需偏离IGP最短路径。(这句原文:This way,operators do not have to express        all the unmodified paths,only deviations from the IGP shortest path.) 

       例子:

       Central Control Over Distributed Routing阅读笔记-LMLPHP(不知道这个图最后一个分号之前是不是多了一个括号??)

       E到D1,有两个分路平衡的路径;

       A到D2,要经过B或者C;

       当(F,H)断了的时候,F到D3要经过G。

通过发现方便的网络路径(如果有的话),Fibbing政策被编辑为针对每个目标的DAGs。

编辑工作分为两个阶段:

1.编辑器将任何的非特定节点的路径需求进行扩展

2.编辑器通过这些需求的目标将其归类并计算其析取范式(Disjunctive Normal Form(DNF),用“或”“V”把几个公式连接构成的公式)。为了最终生成转发DAG,编辑器分别迭代这些路径需求,检查生成的图是否无环。

2.2Fibbing Expressiveness

除了根据一个现成的路径去传输数据,我们现在展示Fibbing还可以:1.在多条路径上平衡分路。2.提供备用路径。

Fibbing可以以任意路径转发任意的流。

Fibbing在多条路径上平衡传输,以最大化生产量,减少响应时间或提升可靠性。

Central Control Over Distributed Routing阅读笔记-LMLPHP

图a,IGP协议计算的最短路径为(E,F,G,H),所以蓝色黄色都走这段,(F,G)的承载量是1,但0.75+0.5=1.25>1,故拥塞了。

(有一种减弱拥塞的方法,是将黄色的流分两路,(B,C)和(F,G),传统的链路状态路由可以将从E过来的数据平衡分路(如将(F,G)的权值改为15)。但是这样会使从S2和S3过来的数据都分散到两条路,创造新的拥塞。更一般的来讲,传统链路状态路由不可能令去往D2和D3的数据流走两条不同的路。)

Fibbing将拓扑改成图b的样子,加入虚结点,由于1+6<3+1+3+x(x为h到黄色目标节点的权值),故黄色的流走上面,这样就解除了拥塞。

这个例子中,Fibbing可以在任何一条链路满负荷时最大化网络效率。

Fibbing可以给任何流提供备用路径,以防止拥塞或由于链路或节点失效而上升的延迟。

Central Control Over Distributed Routing阅读笔记-LMLPHP

图a中(E,F)坏了,故S1到D1,S2到D2的数据都经(A,B)于是拥塞(0.5+0.5>0.75),我们要把D1和D2的流分为两个保持不解体的路径,但仅在(A,D,E,F)有故障时才这样做。这用链路状态路由无法实现,而且这需要用到MPLS(Multi-Protocol Label Switching多协议标签交换)之上的意义重大的控制层。

相对地,Fibbing可以很容易地实现,如图b,备用节点用我们的语言描述为(A,B,*,D1)AND(A,G,*,D1) as backupof((A,D)or(D,E)or(E,F))。加入虚结点后,虚结点的那条路总权值为4,比3大,比9小。

虽然在这个例子中成功了,但是Fibbing并不能满足所有对备用路径的需求。

3.扩展的拓扑

这部分,详述了扩展的问题(3.1),展示了Fibbing控制器如何快速由一些转发DAGs计算小的、扩展的拓扑,我们依靠基于三个连续步骤的分治法。

1)拓扑初始化(3.2):如果必要,我们在链路状态协议中修改初始权值,以保证转发DAGs的任何集合可被Fibbing强制操作。如果需要这个操作的话,这个操作才会被做,且这个操作只能在Fibbing初次被部署时做一次。

2)每一个目标的扩展:由初始拓扑开始,我们为每一个输入的转发DAG的目标独立地计算一个合适的扩展。

我们为这一步设计了两个算法,分别在计算时间和扩展规模上做出了不同的权衡。

1.简单型,可以在毫秒级时间上计算出增加的拓扑并为每个路由器注入一个特定的欺骗节点以改变其下一跳。

2.(相对较慢的)合并型,通过重复利用相同的欺骗节点对多个路由器编程以减小扩展的规模。

两种算法适合不同的目标:

——简单型有助于快速对故障做出反应。

——相对地,合并型可以在后台运行,以进一步对扩展的拓扑再优化。

第5部分将评估每个算法达成的权衡。

3)Optimization across destinations (对目标进行优化?根据目标优化?)(3.4)

将每一个目标的扩展合并起来以进一步减少虚结点和边的数目。也就是说,在安全的情况下,我们将多个实现不同目的的虚结点替换为一个可实现这些所有目的虚结点,或在这个扩展的拓扑中的路由器之间创建一条新路径(捷径)。

3.1拓扑扩展问题

我们通过精确定义它们所依赖的东西以及所解决的问题,开始对拓扑扩展算法进行描述。

虚结点的范围

Fibbing Controller可以生成1.本地范围谎言(对一个路由器);2.全局范围谎言(对所有路由器)

1在允许做出不会对其它路由器造成影响的本地行为时有用

2可影响整个网络,因此,若仔细计算,它们可以减小扩展拓扑的规模。之前的例子用的都是全局谎言。

第4部分将详细介绍如何将这两种谎言实现到当前的OSPF。

转发的下一跳,匹配功能的虚边。

Fibbing可以修改任一IGP路由器r计算出的路由路径。具体的,它可以增加IGP拓扑,故r的最短路径不再是原始拓扑中的那个,而是包含了一些虚的次级路径的。这篇文章中,我们假定最短路径中包含虚路径以及改变路由器的下一跳。

第4部分将讨论如何在现有的OSPF协议以及将来的IGPs上实现这个能力。

拓扑扩展问题

扩展后令每一条(u,v,…,d)的路径中u的下一跳为v或一个虚结点。

3.2 拓扑初始化

如果链路的权值太小,则成比例地增加。

此外,我们将通向任一目标的开销设置得很高。至少与图中最长路径的长度相等,或数倍于最长链路的权值。

拓扑的初始化可以使Fibbing有很强的表达性。

事实上,拓扑初始化使IGP拓扑成为Fibbing顺从的,即派出了转发DAG中Fibbing所不能实施的一些情况。

Fibbing顺从的拓扑中,对每个目标d,包括各个d在内的每个路由器通向它的开销都超过2.

在Fibbing顺从的拓扑中,对任何路由器r到目的地d,控制器总是可以计算出一条虚路径p,满足:

1.p比原本r到d的最短路径短。

2.p比其他路由器v!=r到d的最短路径长。

可以由以下两条定理证明Fibbing可以转发相同目标的流,在任何无环路经集合上。

定理1:任何的针对每个目标转发,有向无环图总能被强制扩展为一个Fibbing编辑的拓扑,即使只使用全局谎言。

证明:r到d的最短路径大于2,加入虚结点fr,使总长度为2,故走(r,fr,d)。

注意:定理1在扩展的拓扑中应用于目标。这些目标不需要去匹配IGP协议中声明的目标前缀。因此Fibbing可以控制流去解聚合初始的IGP目标(由IP地址间隔决定)或者甚至是不重叠的前缀。

拓扑初始化是非干涉的

拓扑初始化基于对一些配置参数的调整,初始化过程可被运用于任何链路状态路由配置并保持原始的转发路径不变。它可在运行的网络中实行,运用著名的无损重配置技术。此外,它在网络的生命周期中不用被运行超过一次。

3.3每个目标的扩展

用图来描述简单型与合并型的不同。

3.3.1简单型

用本地谎言创造虚结点和虚路径(对每个路由器),改变下一跳。由于是本地谎言,故其他路由器不受影响。

Central Control Over Distributed Routing阅读笔记-LMLPHP

(a)由于50太大,故都不走,现在需求大家都来走这个50的。

(b)简单型,给每个路由器配置一个虚节点、局部谎言

(c)合并型,需求更长时间的计算,缩小了增添的规模

3.3.2合并型

分为两个阶段

1.加入一定数量过渡的虚节点,计算各自多的或是少的开销

2.基于计算出来的约束价值,尽可能合并虚节点。

欺骗限制计算:

step1.upper bound:可改变最短路径的值中最大的。Dist(r,d,G)-1

Lower bound:不改变其他结点最短路径的值中最小的。

为了计算lower bound,将节点分为两个集合,依据是输入的转发DAG是否规定去改变他们的下一跳。

对于下一跳不变的:图b中,为了使得f0的加入不改变F到红色点的最短路径,应该有:F走到f0那边的红色点的距离+25>110。更一般的来讲lb(f (r,d))>dist(n,d,G)-dist(n,r,G)

对于下一跳改变的(与其他虚节点连接的):不知其最终的最短路径长度,但这却是由扩展本身决定的。也就是说:任何虚节点的下限都是由其他虚节点的下限决定的。

例如:在b中,f4改变X的最短路径,只有在lb(f4)<dist(X,C,G)+lb(f3)。

Lb增值,第一个从保存的真实路径开始增值,并固定,下一个由上一个固定下来的开始增值,并固定。

Step2:虚节点合并。迭代每个简单结点由源到d,当安全时就合并那一对虚节点。

为评估何时合并是安全的,合并算法连续进行了三步检查:

1.合并算法评估IGP最短路径是否包含被考虑的这条路径。在我们的例子中,A和B之间的最短路径是需求的(A,B,X,D)的一部分。如果A需求路径之前的结点没有与虚节点连接,这个检查会被在那些之前的节点上重复进行。

2.(论文3.3.2最后的部分)

3.3.3处理备用需求

备用需求可以被详细说明,通过提供额外的被标记的转发DAGs。简单型和合并型的小的变种可以处理备用的需求。

1.简单型中,主要修改是针对备用节点将其开销由2改变为3.

2.合并型中,强迫备用路径的下限高于最短路径。

备用路径有时无法被实现。

3.4交叉目的的优化

虚结点有可能过多,减少这些多余的通过以下两种方式

1.将连在同一个实节点上的虚结点合并

2.将虚假的目的地公告替换为连在实节点上的虚结点。

4.IMPLEMENTATION
我们构建了一个完整的协议用Python( 算法部分)和C(与OSPF交互),在Quagga上实现。
Quagga:软件,可将linux机器打造成一台功能完备的路由器。
在这一部分,
4.1 展示协议
4.2 描述Fibbing如何与现在的OSPF路由器一同工作
4.3 提议在链路状态协议的两个小的修改,它们会让Fibbing更有效率
4.4 最后,我们描述了如何确保路由器的可靠性)

4.1 Fibbing 控制器
协议包括3个组成部分:
1.假拓扑生成器
(i) 将转发需求转变为转发DAGs的编辑算法
(ii)将转发DAGs转换为虚结点和链路的扩展算法。
2.链路状态翻译器
与路由器交互:建立路由邻接关系将谎言和拓扑的改变注入路由器。
flooding:从任何节点通过一个路由器发送的信息会被发送给与该路由器相连的所有其他节点(除了发送信息包出来的那个节点)。flooding是快速散布路由更新信息到整个大型网络的每个节点的一种方法。它有时也被用于多点传输信息包(在真实或虚拟网络中从一个来源节点传输到许多特定节点)。互联网的OSPF协议(它在网络中更新路由信息)使用的就是flooding。

运用flooding从每个邻接边散播出去信息,每个路由器有一个特定的识别器,只能看到控制器希望自己看到的谎言。

3.事件管理器
维持一个实时更新的网络拓扑视图,通过
1.分析翻译器收集的路由信息
2.为拓扑生成器构造一个网络图

事件管理器网络中发生了事件影响转发需求(如节点故障或增加)。如果有,它第一时间检查数据库去寻求一个之前计算好的谎言,如果找不到,就通知拓扑生成器去请求一个新的增加拓扑。

4.2 Fibbing与未作修改的OSPF一同工作
我们的Fibbing模型可以与未作使用修改的OSPF协议的路由器一同工作(在Cisco和Juniper上测试的)。为了创造谎言,我们的模型控制控制OSPF信息中的Forwarding Address(FA) field(转发地址域)。假如控制器想让路由器认为目标d以目标地址y直接依附于路由器。控制器便给路由器注入信息:d有一个转发地址y,并且让路由器认为到达d的开销与到达y的开销相同。路由器y忽视了这条信息,所有其他路由器计算他们到达y的开销与信息中的开销的和作为路由开销。

OSPF中的本地谎言。 为支持本地谎言,我们储备了很多IP地址,用于FAs中。所有这些地址在OSPF中网络范围传播。然而,每个路由器都没有路由所有这些地址。所以,只有直接相连的路由器可以到达这些地址,并且接收这些路由地址作为FA。FA关联的IP地址的配置和分配都只能在网络生命周期中做一次。

OSPF中的全局谎言以及其限制。
OSPF支持全局谎言,通过FA,然而未修改的OSPF网络中有一些微妙的限制,由于FAs在路由器上被处理的方法而产生的,显著的:
1.OSPF虚节点事实上欺骗路由器去识别FA,因此它们的位置和到达的方法都被限制
2.OSPF路由器丢弃了FA是它自己的IP地址的信息,并且根据没有虚假节点的拓扑计算最短路径。
这两点结合起来,限制了全局谎言在OSPF中的力量让它想要实现所有转发可能DAG会变得比较没有效率。

克服OSPF的限制。
为了最大化Fibbing的表达性,我们的模型控制器使用了一种顺从OSPF的合并型算法的实现,这种算法结合了本地谎言和全局谎言。在可以的时候运用全局谎言,在全局谎言不能满足需求的时候运用本地谎言。

4.3提议的协议增强
其他链路状态协议,如IS-IS,不支持转发地址,甚至OSPF对谎言的实现也是被限制的。然而较小的协议扩展可以使更灵活的Fibbing运用在未来的路由器上。完全成熟的Fibbing需要路由协议支持两个功能:
1.在接收到的信息的基础上创造邻接(与虚拟节点)
2.一个第三方的下一跳机制,允许被选中的路由器识别转发中要被用到的下一跳。

这两个功能,可以让协议更加有识别性(不影响现有功能的情况下),而且可以通过路由软件的升级来进行升级。

通过与路由器供应商讨论,这个方案可行。

4.4控制器Replication(复制,回答,反应)
与其他网络组建一样,Fibbing控制器任何时候都有可能坏掉。可靠性可以这样被确保:运行多个Fibbing控制器副本,它们平等的,并将他们连接起来,他们在不同的地理位置。

各个副本之间只需要交换输入的转发需求。所有副本总可以算出精确的同样的增加的拓扑。Fibbing副本唯一保持的动态状态是网络图。这个状态被通过IGP同步。

我们算法的确定性允许所有的副本同时注入相同的谎言。然而,这会增加信息洪流的量。

为了限制控制层支出,只有一个副本是活跃的,这个副本注入谎言,其他副本只计算不注入。当这个副本出现问题的时候,其他副本通过接收到的IGP信息,通过判断router ID是否是最小,来决定谁是下一个活跃的副本。

5.评估

通过三个轴评估Fibbing

1.展示路由器可以完美地适应Fibbing加入的额外路径(5.1)

2.就速度和拓扑规模展示了Fibbing增加拓扑的效率(5.2)

3.在网络层级上观察Fibbing的行为就如同一个简单明了的IGP协议一样。因此,由于单个路由器上的微不足道的影响和我们的控制器的高效率,现在的IGP网络可以视作对Fibbing最好的大规模的评估。因此,我们通过阐述Fibbing如何被运用在真实的事例中来完成这次评估。

5.1路由器测量

增加了链路状态路由拓扑的规模,Fibbing可以提升路由器上CPU和内存的支出或降低协议的收敛速度。我们的实验证明了对路径和收敛速度的影响都微乎其微。

(i.e. E.g. Etc.这三个简写的意思在本子上有记录)

两种路由平台上我们得到了同样结论:

Fibbing在路由器上产生很小的CPU和内存支出。

RIB:保持每个路由器都知道如何到达每个目标

OSPF:保持整个OSPF拓扑。

结论:RIB过程和OSPF过程支出都很低。

(RIB应该是路由转发信息库,但这里好像不是,不知道是不是RIP写错了)

Fibbing可以快速完成转发登记。

Total installation time:路由器完全更新FIB的时间

结论:比现在市场上任何OpenFlow交换机快很多。

Fibbing对路由协议收敛时间没有任何影响。

最后,我们比较了有或者没有虚结点时网络的收敛时间。

故意弄坏,看FIB更新时间。

结论:无可见影响,有时甚至有虚结点会更快。

5.2拓扑扩展评估

评估简单型和合并型,根据:

1.它们根据一个给定的需求计算出扩展拓扑的时间;

2.生成的扩展拓扑的规模

Central Control Over Distributed Routing阅读笔记-LMLPHP

Fibbing在毫秒级时间内扩展网络拓扑。

简单型可在0.5ms-8ms的时间内扩展拓扑,合并型用更多的时间,但是也比1秒小很多。两种算法的计算时间与改变下一跳的节点数目关系都不大。

合并型算法及路径优化有效地降低了扩展的拓扑的规模。

合并型算法在平均情况下降低了25%的规模,最好情况下降低了50%。

路径优化在高于90%的情况下实现了对扩展拓扑规模的降低,比不进行路径优化的合并型算法降低了10%,比简单型降低了20%

5.3实例研究

Central Control Over Distributed Routing阅读笔记-LMLPHP

两个源,两个目的,有个源0s就存在,另一个5s加入,开始竞争,为改善,Fibbing控制器加入虚结点,实现分流,于是两个流的吞吐量都提高了。

6.对故障的反应

我们区分了网络(实际的路由器或路由器间的链路)和控制器(坏掉的副本或副本与路由器间的链路)的故障。

我们也分别处理了划分的网络和未划分的网络中的故障。

Fibbing可以对未划分的网路中的故障快速反应。

在网络故障中,被转发的流有三种情况。

1.一些流不受故障影响,由于在故障之前的转发路径没有被打断。

2.没有输入需求的流,只需要IGP为它们重新建立一个路径,不需要Fibbing控制器做什么。这种情况下对故障的反应非常快,由于当前的IGP普遍支持快速收敛和本地快速重路由。

3.剩下的流在Fibbing控制器修改的路径上被转发。它们需要控制器的反应,需要移除之前注入的谎言产生的黑洞和环路,而且避免需求与新的IGP路径不冲突。

理论上讲,总的故障反应时间等于以下三部分时间的总和:

1.通知时间(路由器被通知故障的时间)

2.处理时间(控制器计算新的拓扑扩展)

3.IGP收敛时间(所有路由器安装新的谎言)

我们的评估显示处理时间非常短,尤其是简单算法。此外,通知时间与IGP收敛时间有关,因为flooding比重收敛要快。因此,最坏情况下,总的反应时间是二倍的IGP收敛时间,仍然低于2秒。而且在平均情况下,通知时间比IGP收敛时间短,因为控制器会在所有其他路由器收敛完成之前被通知;因此控制器在路IGP收敛的时候注入新的谎言,总的故障反应时间略微高于没有Fibbing的IGP收敛。

而且如果一个或多个控制器副本坏掉了,但是其他副本还在工作,这对与转发流没有影响,除非坏掉的那个正好是活跃的,并且正在注入的谎言在下一个活跃的副本被选出来之前过期了。即使在后一种情况,新的活跃的副本也会在大约与IGP察觉并flooding这个错误事件相同的时间被选出来。这会使得谎言不太可能在新的活跃副本被选出来之前过期,并且限制了可能的故障的周期。

Fibbing可以实现允许错误或者不允许错误的语义以处理划分的网络。

虽然不太可能,但是比如所有控制器副本或所有网络划分全部失效还是有可能发生的。对所有的中心化方案来说这些情况的主要风险是使网络失控。

举个例子,这种情况发生时,如果一些路由器在一次网络划分之后无法被控制器副本链接到。出于对纯净的SDN方案的遵守,Fibbing可以将控制权委托给潜在的IGP协议。这种方式,Fibbing可以在每一个目标的基础之上实施允许错误的或者不允许错误的语法。

1.对于不严格的(优化)需求,如传输管理的需求。相应的目的可以被注入IGP,这样子,在划分制造出至少一个源到目的的路径之前,连接可以被保持(不影响工作。)

2.对于严格的需求,如安全方面的需求(如跨越防火墙),Fibbing可以实施不允许错误的语法,通过不在IPG中宣布相应的目标。同样的,相应的流在控制器无法连接时停止被转发(这里原文用的是stop to be forwarded in the absence of the controller,但感觉意思应该是停止被转发)。快速实现这个配置,我们可以为被注入的谎言设置一个短的有效时间,是它们在没有重新连接上的情况下快速失效,这会使控制层有额外的开销。

我们确认了Fibbing的恢复力

Central Control Over Distributed Routing阅读笔记-LMLPHP

Central Control Over Distributed Routing阅读笔记-LMLPHP

如图,将两个副本分别连接到A和B,连接到A的副本是活跃副本,假定有一个严格的政策强制红色的流走链路(C,X)。我们在红色的流觞配置一个不允许错误的语法,在另一个流上配置允许错误的。

最开始,运行正常。

时间T=5时,活跃的副本坏掉;T=12时(A,B)链路坏掉;T=20时,(B,X)链路坏掉。最后,T=36时修复(B,X);T=48时修复(A,B)。

实验结果通过iperf收集。活跃副本的故障没有影响流的转发,因为最开始被动的副本(连接到B的)很快察觉到了另一个副本的故障并且继续刷新故障的控制器副本注入的谎言。当(A,B)坏掉,活跃的副本需要移除虚结点f1:因为物理路径(C,A,B,X)不再可用了,这个虚结点会在A和C之间对紫色的流建立一个环路。在察觉故障的情况下,控制器接下来大约1秒内发送LSA(链路状态广播Link State Advertisement)去移除f1,重新建立坏掉的连接。注意这个时间可以通过使用快速的故障检测机制(如BFD)来缩短。当(B,X)也坏掉了,我们便创造了一个划分,使得链接在B上面的副本无法与A,C和X交互。在大约1秒后,被注入的谎言消失了,因为它们不再被任何的控制器刷新。由于被配置不允许错误的语法,红色的流就被黑洞了(为了避免IGP对它路由,使它违反规定的政策),而紫色的流保持着使用IGP的最短路径。最后,失效的连接的重新加入使得工作的副本重新控制了网络:在(B,X)恢复的时候,它为红色的流重建了一条(安全的)路径;并且在(A,B)恢复的时候,它重新优化了两条流在可选路径上的分路。

7.经常被问到的问题

1.Fibbing是一个长期的解决方案吗?

答:短期内,Fibbing提供了可编程性,容易被部署,开销很小。需求更高灵活性的网络可以在边缘部署细粒度(finer-grained)的SDN功能,如Fibbing这样的在核心的解决方案被主要的工业和研究者们所提倡。Fibbing将最好的中心路由与最好的分布式路由结合起来,它比当前的转发模型更符合网络核心的需求(灵活性、鲁棒性、低开支)。

2.Fibbing集合了中心方法和分布方法的复杂性吗?

答:不。Fibbing以非常简单的方式使用了潜在的IGP。IGP的输出易预测,而且提供给控制器强有力的API(Application programing interface)去对路由器编程。这样就使得Fibbing控制器的设计比现有的SDN控制器简单。因为如路径计算和拓扑维持这样的繁重的任务交给了路由器。甚至控制器复制和副本一致的基本任务也主要委托给了现在的分布式路由协议。

3.Fibbing影响安全性吗?

答:不。Fibbing控制器加入的谎言易被认证,如使用基于MD5的认证。

4.既然Fibbing只能设计无回路的路径,它可以支持中间设备的链接吗?

答:部分地。当操作数据流穿过中间设备的链接时,可能会遇到转发回路。这些需求可以再Fibbing中被满足,由来自路由器的本地支持去破坏掉回路。举个例子,路由器出了可以匹配使用基于策略路由的目标IP地址外,还可以匹配输入接口,这个特性广泛的适用于现存的路由器,并且通过BGP中心化预分配。另外一种方式是,中间设备传输控制可以通过SDN的功能在网络边缘实现,网络的核心还是使用Fibbing。

8.相关工作

Fibbing通过在设计空间上发现一个新的点,加深了对路由的集中式控制和分布式控制的讨论。

分布式路由协议的集中配置:

集中的管理系统,可以通过优化链路状态协议中的链路权值来控制传输。Fibbing更通用,因为它可以通过注入虚结点和链路到链路状态协议中以实现任何转发路径。

中心控制使用现存的路由协议作为控制渠道:

RCP是一个逻辑中心化平台,他使用RCP为路由器安装转发项目。RCP必须在每个设备上一个接一个安装转发条目。相对地,Fibbing可以立即调整很多路由器的转发行为,仅用一个很小的输入(如加入一个虚结点),并让它们计算它们自己的转发条目。

集中控制 路由/转发 表:

在SDN中,中心控制器直接将包处理规则装入交换机,也有可能是当接收到特定包时的反应。虽然SDN比Fibbing更灵活(如允许状态性的控制逻辑),但它需要一个接一个地更新交换等级规则,并且放弃了分布式路由所带来的可扩展性和可靠性。最近IETF(Internet Engineering Task Force,Internet工程任务组)开发了I2RS(Interface to the Routing System),I2RS提供了一个新的管理接口去在路由器中集中更新路由信息库(RIB)。但是I2RS仍必须将RIB条目单独推送到每个路由器。

表达需求的Fibbing语言在精神上与Merlin类似,但满足需求的机制(如虚结点/虚连接)完全不同。我们主要的贡献在于Fibbing技术和算法,而非语言。

为满足网络对OpenFlow提供的额外的灵活性的需求,Fibbing在传输中为任何SDN控制器提供了对遗产的路由器转发表(FIB)的权限。这种技术就像圆形监狱一般,可编程性只在网络中允许SDN的部分可用。

CONCLUSIONS
SDN的到来说明了网络需要更高的可编程性与中心化管理。
这篇论文中,展示了Fibbing如何中心化、自动化地控制转发,在没有舍弃分布式路由协议的益处的情况下。
Fibbing是表达性的,可扩展的,并且可以与已存在的路由器一同工作的。
未来工作:
着眼于扩展IGP协议通过Fibbing去实现更好的控制。
抽象地讲,Fibbing展示了如何把集中式和分布式方法结合起来。
我们相信新的研究可以进一步探索这个方向,举个例子,集中式或分布式组件研究中选一个进一步研究。

(1.没有这套方案前,SDN用在分布式路由上会遇到什么问题?
答:分布式路由计算分布式路由的路径,同时sdn控制器给分布式路由制定路径,然后分布式路由会再次更新最短路径,根据分布式路由协议将sdn下达的命令修改、覆盖掉。而且全部计算都交给SDN控制器,会增大sdn控制器的负担。

2.出现这个问题的原因?这种改进后是骗SDN还是骗分布式?如果骗另一方可不可以?
答:未修改的分布式路由协议会自己根据自己的规则计算最短路径,如果SDN控制器给出的命令与分布式路由协议自己的规则不符,则分布式路由协议会将控制器下发的规则修改为自己计算出的规则。

这种改进是骗分布式路由协议,SDN控制器制定骗局,让分布式路式协议分摊它的任务,并且不会干涉它所做的决定。

如果骗控制器,不可以。因为Fibbing的目的是在保持中心路由灵活性的同时,达到分布式路由协议的健壮性、可靠性、可扩展性,如果欺骗了控制器,则会丧失网络的灵活性。

3.他是如何实现骗的?
答:设置虚假节点与路线,让分布式路由根据虚假节点计算最短路径,以达到为SDN控制器服务的目的。

4.传统网络有多种路由协议,这篇文章的方法运用咋哪种路由协议上?若运用在另一种路由协议,会有什么问题?
答:这篇文章运用在OSPF路由协议上,如果运用在RIP路由协议上,
1.rip协议一条路由有15跳限制,无法达成提高网络可扩展性的目标。
2.rip协议以跳数作为网络度量值,没有网络延迟和链路开销的概念,而Fibbing想要精准的欺骗路由协议,精准地控制路由协议的行为,需要对各段路径之间的开销进行操作,在rip中无法实现。
3.rip周期性交换路由信息,ospf在链路发生变化的时候交换路由信息,正好符合Fibbing的需求。
4.rip中路由器用自己的路由表与相邻路由器交换信息,有慢收敛的特性,好消息传得快,坏消息传得慢;ospf交换路由信息,收敛速度快,控制器下发的指令生效速度差别很大。

在虚节点撤销的时候,RIP的慢收敛特性,会产生比较大的麻烦。

5.rip协议交换的是路由表,即每个路由器如何到达某个目标,OSPF交换的是整个链路的状态。在OSPF中比较容易实现本地的谎言,在rip中不容易实现。由于rip的信息比较简单,即A到达X需要多少跳,这个信息在A传递给B的时候,以及传递给C的时候,比较不容易制造本地谎言。

05-11 18:00