01 布景

阿里云作为亚太榜首云厂商，需求服务各种各样的细分领域客户，例如 3C、游戏、网页加快等客户。近年来，跟着视频咨询类客户的蓬勃开展（头条），低推迟、高可用的全球网络需求也越来越旺盛。因而，在“全站加快”架构规划之初，就需求考虑怎么为海量客户构建差异化的低推迟网络。

阿里云现在现已建造有 2800+个全球节点，但这些节点的带宽才能、互联互通才能、对 TCP/QUIC 等传输协议兼容才能都不尽相同。因而，怎么在这种复杂的、多维束缚的网络环境中挑选适宜的网络通道（即智能选路），就变得十分重要了。

02 海量客户的智能选路

从图论的视点看，CDN 节点、客户源站类似于图中的节点（node），节点间网络、回源网络类似于图中的 edge，由这两者组成的有向图 G(node, edge)，便是智能选路需求求解的全集。

所以智能选路体系本质上是：在有向图 G 中寻找最“短”途径的进程。虽然这个“短”会叠加上很多定语，例如：在带宽允许的状况下，在跳数束缚的状况下（由于跳数越多，本钱越高）。但为了简化问题，能够先不考虑这些定语，即无限资源场景下的智能选路。这在产品上线前期，客户少、带宽等资源占用少的时候，是比较适用的。

1.最短途径

介绍智能选路体系绕不开的一点，便是最短途径算法的选型。考虑到实践公网中，是不会存在负权重的场景，因而只需求在 Dijkstra（单源最短途径，以下简称 D 算法）、Floyd（多源最短途径，以下简称 F 算法）中挑选即可。

乍一看，要处理海量客户的智能选路问题，好像就应该挑选 F 算法，但仔细想想其实应该组合运用。智能选路是要处理客户端到源站的最短途径问题，它是不需求核算不同源站间的最短距离的，即它不是一个 P2P 的选路问题。跟着客户源站数量的不断增长，算法所需的邻接矩阵会越来越稀疏，这时候 D 算法的性能优势就展现出来了。

当然 F 算法也不是一无是处的。把智能选路分解为 2 个子问题：CDN 节点间最短问题 + 回源网络最短问题，考虑 CDN 节点间网络是强连通的稠密网络，因而求解进程用 F 算法会比 D 算法更快。在求解全链路最短问题是时再运用 D 算法。这种算法组合能获取 1 个数量级的核算耗时缩短（当然，提升多少其实也取决于客户源站数量级）。

2.多样途径

从高可用（即体系安稳性）的视点看，恣意 2 点间只给出 1 条最短途径是不行的。由于一旦这条途径上的光线被挖断、节点因毛病下线等影响，都会导致客户服务的短时间不可用。

上述影响是比较常见，也比较简单设想到的问题，但其实还有数据推迟（时间）问题，由于智能选路体系构建的网络拓扑不可能是彻底实时的，总是有一定推迟存在的。假如 T-1 时间的网络较好，但 T 时间网络反常时，智能选路体系用 T-1 时间的网络拓扑核算的选路成果肯定是有问题的，而网络反常又是难以预测的，因而增加冗余的途径就显得极为重要了。

所以原则上，最少要一起供给 2 条相对较短的途径。这在学术上一般称之为 k-shortest 途径问题。直接套用学术界的算法会有一些比较糟糕的问题：1）只要 k 是大于 1 的值，求解耗时一般呈指数级上涨，会导致核算太慢（即毛病切换时也慢）；2）学术届一般都是考虑严厉含义的第 2 短、第 3 短途径等，不考虑途径重叠的问题。在实践公网传输的场景中，一旦挖断的光纤是主备途径的公共段，仍是会导致客户服务的短时不可用。因而需求工程化的高效的、多样的备途径能被筛选出来。

3.分层聚合

跟着客户源站接入的越来越多，智能选路体系的算力越来越绰绰有余。虽然能够经过体系横向扩容，经过集群化的方法处理规划问题，但扩容总是面临预算、周期等要素的影响，不太可能一蹴即至。因而仍是要持续优化算法

直觉的高速网络通道的挑选进程，其实和菜鸟的快递运输进程、高德的途径导航进程是高度类似的。所以，当人来挑选北京到杭州的最快、最短途径时，一般都是找 1 个最近的高速路口，先上高速，然后再找 1 个距离杭州近的高速路口下。几乎不会考虑省道、县道等若干段途径的组合，经历上也是高速更快的。

这种可解释性十分好的直觉选路战略给了 2 个启示：1）应尽量挑选高速公路，在公网上相对应的便是专线及能被双边加快的途径。单边加快的途径应该尽可能短，哪怕这部分途径有一些南辕北辙也没关系，长链路上“高速公路”上的加快作用是彻底能超越这部分丢失的；2）没有必要为北京东城区、海淀区的不同客户，分配不同的到杭州途径。换句话说：新接入的北京电信的客户源站，其实上能够直接复用其他北京电信客户的智能选路成果，没有必要重复算（一般算出来的也是一样的）。

03 多维束缚的智能选路

上述内容首要介绍了“无限资源场景”下的智能选路。跟着客户数量的增多、客户自有带宽量的上涨，“无限资源”的简化场景就不太适用了。因而需求考虑多种不同维度的束缚，确保智能选路体系在有限范围内，挑选适宜的途径。即“有限资源场景”的智能选路。

1.节点束缚

在前文布景中也介绍了，节点带宽才能是在采购环节就决议了，用量超越上限必定会带来不可用、过错、推迟等各种反常问题。因而需求在智能选路时考虑节点容量（包含但不限于带宽、CPU 等）。

这种带束缚的途径规划问题，要么运用贪心战略：优先核算一部分客户的最短途径，扣减相关资源占用后，持续下一部分客户的途径核算；要么运用运筹优化：设定最小化方针（例如：最小化大局推迟），并参加多种束缚条件后，导入求解器求解。贪心战略适用于有清晰优先级划分的场景，规划上便是低优先级避让高优先级，可解释性好；运筹优化适用于无优先级场景。

所以需求根据不同业务场景，挑选不同规划算法，甚至可能是组合运用。在核算规划十分大，无法实时（分钟级）核算时，还需求邻域搜索等部分更新算法。

2.网络束缚

公网中绝大部分流量都是 TCP 的，因而公网的中间设备往往对 TCP 有很多 QOS 的优待。相比较 UDP 的相关优化就很少，会被限速，甚至在高水位运转的网络中，还存在下降 UDP 转发优先级给 TCP 让路的行为。

因而节点间传输运用 QUIC 协议就需求“小心翼翼”，既要关注前史 UDP 峰值，调查在大流量时的推迟指标是否有显着“非预期”的下滑，选路时也要多多运用这种大流量“无损”的 UDP 管道，然后确保对客户服务的安稳。

3.动摇束缚

经过实时的网络探测来量化节点间网络距离是常见的，与此一起，网络探测值也是带有噪声的。无论是来自节点内不同机器的负载细微差异，仍是公网中必定存在的细微动摇，都有可能直接导致智能选路成果的变化。从朴实算法、图论的视点看是没问题的，由于每一轮算法的输出成果都是独立于上一轮的，即彻底基于静态快照式的选路。

网络流量彻底参考快照式选路成果来传输，是 100%无损的么？并不是的。关于绝大部分有衔接的 TCP 来说，新的途径就意味着新的 TCP 衔接建立，必定有握手的开支。假如上层跑的是 HTTPS 流量，还有 SSL 握手等更大的开支。一方面这些握手有带宽本钱的上涨，另一方面非 0-rrt 管道就意味着“慢”。所以，为了 3-5ms 的理论距离缩短，支付 30-50ms 的额定握手开支是因小失大的。

所以，衔接池、TFO 等 0-rtt 网络传输技术，反向要求智能选路成果是安稳的（即依赖上一轮选路成果的）。简单理解便是只有在网络显着劣化、节点毛病下线时，才快速切换。即非必要，不切换。

当然，在必需求切换的场景中，也是需求思考并规划合理的阻尼的。例如在单节点毛病下线场景，关于流量切出的要求是：下一轮核算有必要 100%完成切出；而关于流量切入（次短 or 备途径）的要求则不是那么严厉，即流量能够分摊到次短、次次短等多条途径上。这首要是考虑次短途径全量接受，会导致瞬时新建衔接洪峰，极简单打满 TCP 半衔接行列，形成 syn 包重传等加快性能的劣化。

上述动摇束缚，还仅仅只是考虑了动态恳求（一切恳求都到达源站）的加快进程。考虑静态恳求（节点缓存有概率能射中，不需求一切恳求到达源站）的加快进程，对途径动摇的容忍度更低。由于新途径上一开始的射中率是 0%，而老途径上是 XX%。所以途径切换最好发生在缓存快要过期的时间，这对海量缓存的实时计算，智能选路的精准切换提出了更高要求。

4.手动束缚

无论是开发的前期阶段，需求手动调试体系的才能（或东西），仍是在开发后的交给阶段，需求供给毛病逃逸的人为介入手法。由于需求在彻底自动化智能选路体系中，在一些要害节点或环节，参加人为操控是十分必要的,就像世界上自动化程度极高的波音客机的自动驾驶，依然保留了手动驾驶模式，以防止在极点恶劣状况、体系规划中非预期状况下，由人判别，由人决策。

综上，智能选路体系是从一个有向图的最短途径算法集，逐步开展并完善成一个能为海量客户实时构建多维束缚的低推迟、高可用网络的算法渠道。