包处理的艺术(2)---如何设计协议

语言修辞通常把一个东西叫成不同的名字，而数学则恰恰相反。

2018年OCP，阿里的依群总有个Keynote：The Challenge and Opportunity to Build a Transparent Network[大概4:00~6:00的时候] 提到过BGP、BFD这些协议已经数十年以前设计的了，但是已经无法适应现有的网络需求。同时还有K姐在19年说过：“SDN这事本身错了”。

协议的设计背后有太多的考虑，网络中要给出一个解决方案非常容易，无非就是编码解码总有一种方法能够处理某些特定的案例，但是最终活下来的都是有很强泛化能力的协议。这就是为什么我在开头会说一句话：“语言修辞通常把一个东西叫成不同的名字，而数学恰恰相反”。前段时间跟一些同事开会更是深刻的感受到了两种思维方式的碰撞。

1. 协议的设计：自顶而下的方法

《计算机网络：自顶向下的方法》基本大家都有读过，那么计算机网络的协议设计自然也是这样Top-Down的方法，但是向下遍历的过程中却有些奇妙的事情在发生，因为个人的职业生涯都是自底而上的。

1.1 深度优先的设计思维=Down to Top

人的职业生涯发展，没有人一开始什么都懂就直接做架构师做顶层设计的。通常在设计协议时回溯自己走过的光辉历程并将自己的职业生涯和已有项目经验复用便成了最佳实践。这样的思维方式解决小规模的问题非常棒，毕竟可以很快速的通过类比理解需求和最小的工程代价实现。但是随着职级越做越高，其实这样的设计会变得越来越危险，因为您需要解决的问题规模越来越大，而自身的视野并没有同比例的扩大。

通常这个时候解决问题还是按照一线研发的思路，定义好一个很小的问题，然后逐渐细化到差不多代码层级能工作了，也就认为协议设计做完了，但最后却成了一个工程灾难，因为客户用的拓扑结构千奇百怪, 为了满足客户的需求通常需要伤筋动骨的大改。而且这样的设计通常模块间紧耦合或者冗余组件过多。实际上这种以深度优先寻找解决方案的设计思维变成了自底而上的设计方法。

某司在设计第一代SDWAN时便犯了这样的错误，最终花600M USD买来某家的教训借此复盘一下。第一代SDWAN: IWAN诞生的讨论大概是在2012年左右，Hugo Vliegen(现在Aryaka的PM-VP)和Michael Dickman(现在Aruba的SVP/GM)召集大家搞了一个某司的路由市场部的All hands，主要议题就是现在互联网带宽足够价格也下降了，企业可以使用IPSec VPN技术构建基于互联网的Overlay线路了。而且某司在很多企业包括自己的CVO(Cisco Virtual Office)解决方案中都使用了互联网线路构建。所以在找到场景细化设计架构时，犯下了一个非常严重的错误。也就是这种自底儿上的思维方式的错误。某司VPN方案有一堆(Crypto Map / GRE over IPsec / IPsec Over GRE / SVTI / DVTI / EzVPN / GetVPN / DMVPN)，最终直接选择了DMVPN，因为很多客户都在用它商用，有Hierarchy的支持，看上去也不错，也可以很快速的到市场，然后需要广域网和内网隔离，复用已有的FrontDoor VRF和InDoor VRF即可，看上去也没毛病，隔离开来以后Underlay的fVRF需要有一个路由协议，而Overlay的iVRF也需要路由协议，好像也能直接用BGP、EIGRP、OSPF，然后客户又提出来我要根据性能选路，好像某司以前还有个OER后来叫PfR，套上去就行了。而最终这样的实现方式产生了灾难性的后果。对于一条路由，广域网上由四套路由协议决定，PfR、Overlay的EIGRP、DMVPN的NHRP、underlay的IGP，然后同时由于PfR的问题，还要约束客户部署拓扑，BR/MC的放置都是问题， 自动路径选路一致性的问题也无法协同解决。

而SDN领域的OpenFlow和大量的SDN实现都在后期遇到了问题，最根本的原因也就是在此，正如12条军规中所说的那样：Every old idea will be proposed again with a different name and a different presentation, regardless of whether it works.

当然在这个过程中，还有一点非常重要，就是不要因为某些东西一时热起来了就去跟风，而不考虑内在的原理。某司不成熟的iWAN我从来没给任何客户推荐过，而OpenFlow我极力让客户不要上线，甚至在公司内部一直反对这些东西，虽然没有因为这些热门技术获得一些升职加薪的机会，但是一个人在行业里的决断力和评价自然会因为坚持而获得收获。时至今日，几乎所有的人都在推SRv6和P4时，我依然会反对，就是这个原因。

1.2 广度优先的设计思维

这样的处理方式一开始就要很坦诚：One size never fits all，你要在不同的地方列出能够实现的选择，并细致的分析哪些适用，哪些场景不适用，最终做出合适的选择和取舍。

广度优先的设计思维实施起来却非常的难，因为要见多才能识广，很难有人有能够有广阔的视野和丰富的项目经历去覆盖大量的客户场景，并且同时参与到研发中，细致的了解大量协议的实现过程，通读RFC并且构建拓扑触发各种消息然后抓包分析。（我不要脸的说，我都做过）

或许是因为常年受数学系的训练所致，我在处理这样的问题的时候，通常会进一步的去抽象问题，找到各个场景的共同点，类似于合并问题分支，另一方面是从原理上出发去找到一些理论上不可行的解决方案，通过剪支来降低问题的规模。最后适当的约束问题的规模，然后尽力的去找到相对约束条件下的可行解，并且清楚的明白自己取了什么，舍弃了什么。

说起来非常抽象，接下来几个章节给大家详细说说如何操作的。

2. 分布式系统的CAP理论

本质上计算机网络就是一个分布式系统，自然不得不提及CAP理论：

CAP定理又称CAP原则，指的是在一个分布式系统中：Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），最多只能同时三个特性中的两个，三者不可兼得，最多满足其中的两个特性。也就是下图所描述的。分布式系统要么满足CA,要么CP，要么AP。无法同时满足CAP。

百度百科

2.1 CAP定义

Consistency (一致性)

“all nodes see the same data at the same time”,即更新操作成功并返回客户端后，所有节点在同一时间的数据完全一致，这就是分布式的一致性。一致性的问题在并发系统中不可避免，对于客户端来说，一致性指的是并发访问时更新过的数据如何获取的问题。从服务端来看，则是更新如何复制分布到整个系统，以保证数据最终一致。

Availability (可用性)

可用性指“Reads and writes always succeed”，即服务一直可用，而且是正常响应时间。好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。

Partition Tolerance (分区容错性)

即分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性或可用性的服务。分区容错性要求能够使应用虽然是一个分布式系统，而看上去却好像是在一个可以运转正常的整体。比如现在的分布式系统中有某一个或者几个机器宕掉了，其他剩下的机器还能够正常运转满足系统需求，对于用户而言并没有什么体验上的影响。

2.2 一些事实

事实1：基于目的地址转发的系统是CP

CP without A：如果不要求A（可用），相当于每个请求都需要在服务器之间保持强一致，而P（分区）会导致同步时间无限延长(也就是等待数据同步完才能正常访问服务)，一旦发生网络故障或者消息丢失等情况，就要牺牲用户的体验，等待所有数据全部一致了之后再让用户访问系统。

当我们选择了基于目的地址转发时，为了避免环路则必须要保证路由表计算的一致性，例如OSPF这些链路状态协议本质上就是在同步LSDB在出现故障时牺牲局部的可用性，也就是说无论如何BFD怎么搞或者SPF怎么算，都会存在短暂的可用性的问题，要么是短暂的MicroLoop要么是短暂的路由黑洞。

事实2：路由协议和一些SDN实现是CA

CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但放弃P的同时也就意味着放弃了系统的扩展性，也就是分布式节点受限，没办法部署子节点，这是违背分布式系统设计的初衷的。

很多路由协议设计于上世纪，由于规模相对较小所以通常采用保持一致性和可用性的做法，例如在域内选举DR、BDR的方式，或者采用RR反射的方式，本质上这样的做法就是在转发系统要求一致性的时候，控制面选择某种集中式的处理方法，Openflow也就是这种思维的延续，通常很多人会假设有一个云端无限的资源池，但忘记了本质是当您选择了CA则无法满足分区容错性，控制器脑裂的故障自然而然的就出来了，为了补救P和A路由环路和黑洞的问题也同时伴生了。这些问题在SDN规模不大时还好，而在SDWAN时就产生灾难性结果了，因为广域网的不可靠性让你A都满足不了。

事实3：SR采用适当的源路由放弃一致性获得可用性，即AP

AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。

Clarence做SegmentRouting的本质就是在适用源路由的方式获得TI-LFA，即对于任何拓扑，将问题分治成P、Q两个域，各自域内采用基于目的转发，而通过源路由连通P、Q域，实现控制平面不一致时的转发平面的可用性，本质上您看这个问题就是AP了，本地数据不一致时也无所谓，只要能找到一个满足SLA的路径就可以了。

2.3 协议设计的原则

成年人的世界不讲选择，都要？

CAP不行，那么我选择控制平面CP和转发平面AP来构建~

原则1：控制平面采用CP

正如前面所说，在SDWAN等复杂场景中，控制平面可达性本身就无法保障，经常会存在Headless的情况，那么Availability自然就可以舍弃了，找个CP实现的系统作为控制平面则是非常自然的取舍，一致性的约束范围也有取舍，不保证链路状态一致性，而仅保证资源归属一致性。后面路径计算小节会详细叙述原因。

原则2：数据平面采用AP->BASE

数据平面才是真正承载用户业务的地方，选择AP的原因是为了实现BASE(Basically Available, Soft State, Eventual Consistency). 如前文所述，使用SR是必然选择，但是在这一点上不要想太多做太复杂，使用SR只是利用Segment的思想完成LFA就好，如果再去构建一些流量工程的复杂SRTE或者ServiceChain您又会陷入到选择CA或者CP的境地，Basic Available是前提，对于Soft-State的处理简单的P/Q Space划分做LFA就好，最后Control Plane Eventually会Consistency。

不要把事情做的太理想化, 所以这也是某种程度上我并不看好SRv6做复杂的编程Policy的原因，更多的是您需要将策略和路径和虚拟化租户三者解耦，把策略和转发混合在一起本质上就是一个灾难，策略是自顶而下的，转发是自底而上的。

Policy comes primarily out of business decisions, and business decisions should be close to the business, not the topology. Hence, policy, or least some element of policy, is often best done when centralized. 

Topology and reachability, however, are grounded in what should be the only source of truth about the state of the network, the network itself. Therefore, it makes sense that decisions related to the topology and reachability, from detection to reaction, should be kept close to the network itself; hence, topology and reachability decisions should trend toward being decentralized

DataPlane如果也要选择C，那么是CA还是CP？历史上很多分布式系统的路由器集群，例如CRS-1，TX-Matrix最终走向坟墓就是因为选择了C，这样也从另一个方面反证了数据面只能采用AP，并尽力的实现BASE是唯一选择。

3. 路径计算

为了解决分布式系统的问题和SPF等算法导致链路带宽无法充分利用的场景，在这种背景下，集中式计算，控制面大集中被提了出来，似乎将控制面集中就有了上帝视角。基于OpenFlow的SDN就这样被忽悠出来了。然后很多人开始算天算地算空气了。最后遇到了大量的Scale的问题。

另一方面集中式节点无法实时的获得链路状态，故障出现后，由于可达性问题使得故障无法上报到集中式路径计算引擎，因此会出现黑洞。所以某个号称弹性SDWAN白皮书的运营商整个方案虽然用了SR但是犯了集中路径计算的错误，也是前面我提到过的Policy和Topology本质上一个是需要集中一个是需要分布的。

现代网络业务对于网络的需求已经不是简单的通或者不通了。一把梭的年代早就过去了...

所谓的服务化网络更多的是基于服务质量的计算，并不是非黑即白的计算方式，有些时候并不需要最低延迟或者最大带宽，满足SLA即可。在这种情况下，链路质量通告将成为刚需，基于链路质量的路径计算会成为必然选择。因此我们有以下两个结论：

结论1：必须采用分布式路径计算, 并且路径计算尽量由最边缘的节点完成，其它中继节点采用简单的转发模式，这也是Intelligence Edge，Dummy Core的原则。

推论: 由于边缘节点需要计算路径，因此链路状态信息必定会通告给边缘节点。

3.1 链路状态通告

链路状态的通告也是有争议的，是采用Push还是Pull的模式？是全链路通告还是不通告？例如一个标准的三段网络带有PoP点的SDWAN，核心网的拓扑和链路状态是否要通告给边缘节点?

Option.1 核心网拓扑隐藏，PE进行第二层决策

这也是常见的作法，传统的MPLS VPN的PE就是这样的，如果不通告给CPE，则PE需要采用基于目的地址的转发，中间可能会因为一些问题出现路由黑洞或者链路非最优化的情况，数据平面的BASE无法保障，PE同时需要维持大量的状态信息，例如不同的CPE对于不同业务优先级的需求等规则，同时核心网拥塞情况CPE无法感知，CPE也无法选择链路绕行，整个系统资源利用率较低，如果数字孪生的方式为每个CPE计算路径，例如采用SPF算法时间复杂度为O(N^3,因为SPF是N^2还有乘以CPE的个数次的运算)。当然很多通信从业者计算机算法的底子薄也显露出来了，例如Dijkstra可以通过堆优化的方法把时间复杂度降到O(nlogn),但集中式运算复杂度也要O(logN*N^2）,如果客户应用种类多可能复杂度还要进一步乘以应用个数M，按照我以前搞OI的经验，这样的算法复杂度规模节点数不会超过10K，很多做通信的人没有这方面的知识， 还会不停的跟您说“云的资源是无限的”，但是计算和同步这些信息需要大量的时间，特别是广域网环境，即便是假设所有的通信时间为0，但咱也没那么多钱来构建这些啊，最后整个解决方案变成了买椟还珠那种，控制器成本比CPE还贵。所以这也是某运营商弹性SDWAN白皮书一开始就没想清楚的地方。

Option.2 核心网通告链路状态给CPE

如果核心网通告链路状态给CPE，那么拓扑通常非常大，而且伴随链路变化拓扑更新一直在通告，链路状态泛洪在大规模拓扑中也是一个大问题，特别是很多运营商希望PE设备云化能够根据CPE业务数量弹性扩容时。所以采用Push模式全通告链路状态也是不可行的，这样又剪掉了利用BGP/BGP-LS构建路由信令控制面的可能性。

那么是否可以在这两个选择之间妥协呢？基于图的全计算SPF算法无法满足大规模的需求，同时全网链路状态同步和泛洪压力非常大，而基于分层/分段对于路径和拓扑复杂度做了剪枝，但又无法满足端到端的业务识别和拥塞情况感知，需要同CPE做大量的业务绑定耦合。PE本身就要做到轻量化无状态才能满足BASE的需求。

3.2 基于BASE原则的可选链路状态通告

给出这张图大家都明白了，图搜索算法例如Dijkstra是无法满足大规模网络的路径选择的，路径规划本身就有很多成熟的算法和商业实践，例如传统的A*，或者后期的一些CH/HH/CRP等算法：

CH：http://algo2.iti.kit.edu/schultes/hwy/contract.pdf
HH：http://algo2.iti.kit.edu/documents/routeplanning/esa06HwyHierarchies.pdf
CRP：http://research.microsoft.com/pubs/145688/crp-sea.pdf

本质上这个问题和当年的EIGRP所采用的DUAL算法有些相似的地方，我只需要满足Fesible Condition尽力朝着目的地走就行了，满足应用的SLA就行了。

全拓扑的信息也就不需要了，只需要CPE动态的根据自己的SLA情况，不满足SLA计算了再多从控制面subscribe几个PE的linkstate信息就好，这也就是我在做自动驾驶网络的时候的算法，如下图所示，R1/R6可以根据自己的实际业务需求要求控制器或者其它路由器发送LinkState

而端到端的应用性能检测和可达性检测，则采用如下的一些AI算法直接在CPE上就可以做：

4. 同构

分治并且通过封装来解耦是一个非常常见的处理问题的思路，这也是我以前读SICP的最大收获之一。网络如果能实现同构则对整个规模的扩大会非常有益，例如CLOS的交换架构或者BGP的联盟，本质上就是将一堆个体组合起来，其操作（算子）还能等同于原来个体的处理能力。

所以CLOS架构的交换网本质上是要构建一个大的虚拟交换机，所以SDWAN的设计上也需要构建一个大的路由器，满足L2VPN / IPSec / MPLS / IGP / BGP / Multicast / VXLAN等多种业务场景，这也是很多安全厂商或者云厂商做SDWAN最软肋的地方，某些客户经历了十多年二十年的广域网部署，通常网络配置和业务流向非常复杂，这些厂商的SDWAN在这种Brown Field的部署几乎是不可能的，被迫让客户选择完全重建，而且和已有的网络完全无法融合，或者仅能在一些PoP点互操作。

当我在设计Ruta时，本质上就是利用Ruta同构Router，所以一开始的想法就是Ruta整个系统要能够作为一个大型的路由器使用，本质上就是把各个CPE当作路由器的线卡实现，即便是移动手机的VPN客户端也把它抽象成路由器线卡的一部分。

但是这样的做法也有一些特别巧妙的地方，有人说SDN不也是把OVS当作线卡放到主机上，然后有一个ODL控制器来管理么？请参考第二章和第三章再来反思这个问题和两者真正的区别。

5. 软硬件一体化

本质上分布式系统为了满足高性能的处理，通常解决方案是软硬件一体化的方案，但是在不同的位置异构的硬件芯片也有不同的属性，因此协议设计者需要同时对硬件有很深入的理解，很多人盲目的拔高交换芯片的编程能力，或者盲目的认为FPGA无所不能，这些都是非常错误的观念。

核心芯片基于吞吐量的考虑通常只能实现一些简单的Pipeline的操作，因此协议设计上就不能让核心节点处理一些分支Jmp的操作，即便要有也要足够时间和可约束的Cycle完成，这些内容只是在这里提一下，后面讲RTC vs Pipeline时会详细阐述。

6. 协议设计实战

Ruta是一个完全云原生的去中心化自组织路由器架构，可以通过容器扩容支持数十Tbps容量和数百万端口密度的超大规模路由器系统。

控制面：draft-zartbot-srou-signalling.txt 

转发面：draft-zartbot-sr-udp.txt

zartbot.Net，公众号：zartbotRuta？智能插座？重新发明路由器！

按照如上的分析，控制面选择需要保证一致性，那么只能选择CP，我在设计Ruta时控制平面选择ETCD也就是这个原因，针对数据面则为了满足AP(BASE)，选择实现了SR，但是Segment Routing在互联网云环境中无法支持MPLS，接入侧又无法保障IPv6，因此选择了采用SRover UDP的作法，把Layer3隐藏，这样就可以保证Ruta在MPLS或者IPv4/IPv6上都可以连接。

另一方面为了保证数据面BASE，实际上我们可以随机选择3个Pop点的方式构建一个规模相对较小的拓扑供CPE计算. CPE可以实现完全的RTC计算能力和数据面复杂的性能监测和安全策略，因为其处理能力通常仅在100Gbps以下的规模，而中继的Pop点为了在CPE不满足Basic Available需要新增时（例如原有Pop点失效，CPE为移动网设备需要动态迁移Pop）等场景时，保证Pop点Stateless做Pipeline 转发也是必须的，因此SRv6也有一些问题，如果不改变源地址可能会导致一些中继节点RPF检查过不了。

所以基于这样的思维方式设计的协议，自然泛化能力会相对好很多，无论是SDWAN的场景，还是数据中心高性能网络场景，或者视频会议等场景，具体可以参考如下连接：

今日技术扶贫到此结束，留个图懂的人自己体会~