导语在了解了 TCP/IP 的底层传输和网络边缘应用后我们将直击互联网的“导航中枢”——路由 (Routing)。数据包究竟是如何跨越全球的路由器之间是如何沟通“路况”的本单元我们将系统学习距离矢量、链路状态算法探索 BGP 协议背后的商业逻辑以及下一代互联网协议 IPv6。Main TopicsApproaches (路由策略)Flooding (泛洪)、Source routing (源路由)、Forwarding table (转发表)、Spanning tree (生成树)。Algorithms (路由算法)Bellman-Ford 算法 (Distance Vector 距离矢量如 RIP 协议)。Dijkstra 算法 (Link State 链路状态如 OSPF 协议)。Internet Routing (互联网路由)层次化路由、AS 自治系统、BGP 协议背后的商业策略。Multicast Routing (组播路由)。Spanning Tree Protocol (STP生成树协议)。Names and Addresses: IPv6。1. Routing - Basic (路由的基本概念和原则)1.1 The Problem (核心问题)当数据包要从 A 传输到 B 时面对复杂的网络拓扑应该走哪条路是最短路径最快路径还是最省钱的路径这就是路由要解决的问题。1.2 Flooding (泛洪)机制最简单粗暴的方法。路由器把收到的数据包向除了接收端口之外的所有接口复制并发送出去。优缺点数据包最终绝对能到达 B 点但效率极低会引发极大的网络拥堵广播风暴甚至陷入无限循环。因此现代路由很少直接使用无限制的泛洪。1.3 Source Routing (源路由)机制由发送端主机 A记录并决定整个网络的拓扑结构和最短路径。数据包的头部包含了沿途要经过的所有路由器的完整清单。优缺点路由器无需维护庞大的转发表符合“强端到端原则”。但缺点是数据包的头部会变得极其庞大开销大且存在巨大的安全隐患因此在实际中极少被使用。1.4 Forwarding Table (转发表现代主流)机制路由器内部维护一张表包含目的地地址和对应的输出接口。数据包只携带目标地址路由器查表决定下一步怎么走。路由算法的核心任务就是动态地计算并填充这张转发表。1.5 Spanning Tree Metrics (生成树与衡量标准)Spanning Tree (生成树)当网络中存在环路时利用生成树算法可以构建一个无环的逻辑拓扑确保数据不会无限打转。What is our metric? (成功的标准是什么)路由算法在计算“最优”时可以基于不同的标准Annotated Graph带权图最短距离、最小跳数 (Hop count)、最小延迟、最大吞吐量、最低成本 (Cost) 或 最可靠路径。1.6 Multipath (多路径行为)流量负载均衡当计算出到达目的地有多条成本相同的路径或者某条最优路径非常拥挤时路由器会选择将流量分散到多条路径上以提高整体网络效率。1.7 Multicast (多播/组播)场景终端主机希望把一份视频同时发送给 100 个人。如果逐个单播要发 100 份极大浪费服务器带宽如果广播全网都会收到不仅浪费而且不安全。多播机制一种极其聪明的策略。发送方只发送一份数据数据包在网络的交叉路口路由器根据需要自动复制“分叉”精准送达需要它的主机群。2. Routing - Distance Vector Protocol: Bellman Ford Algorithm距离矢量协议 (Distance Vector) 的核心是每个路由器只知道自己到邻居的距离大家通过互相交换“小道消息”来拼凑出全局最优解。2.1 Bellman-Ford 算法算法原理一种计算单源最短路径的经典算法。它通过迭代和松弛操作 (Relaxation)逐步更新节点之间的最短路径。特点类似动态规划的思想。每个路由器维护一个向量表记录自己到所有已知目的地的成本和下一跳并定期把这个表发给相邻的路由器。2.2 Distributed Bellman-Ford (分布式机制与信息传播)Good news travels fast (好消息传得快)如果发现了一条更短的路路由器会立刻更新自己的表并告诉邻居邻居再告诉邻居整个网络迅速收敛。Bad news travels slowly (坏消息传得慢)假设节点 A 宕机了B 发现路不通但 C 之前的记录里写着“我可以通过 B 到达 A”。于是 C 告诉 B“没关系你可以通过我到达 A。” B 信以为真更新了错误的路由。大家互相欺骗跳数不断累加这就是臭名昭著的Counting to Infinity (计数到无穷大) 问题。2.3 Counting to Infinity Problem (如何解决环路与坏消息传播)为了加快坏消息的传播距离矢量协议引入了以下机制Poison Reverse (毒性逆转)当你发现某条路不通时你不只是把它从表里删掉而是主动告诉邻居“这条路的成本是无穷大 (Infinity)” 这样邻居就会立刻死心不会再尝试把数据发回给你。Split Horizon (水平分割)路由器从某个接口学到的路由信息绝不会再从这个接口发回去防止路由回环。Triggered Update (触发更新)一旦链路状态改变立刻发送更新而不是傻等 30 秒周期。3. Routing Protocol - Dijkstra’s shortest path first algorithm链路状态协议 (Link State Protocol) 采用了与距离矢量完全不同的“上帝视角”。3.1 拓扑结构上的 Dijkstra机制每个路由器都会把自己知道的链路状态我和谁连着成本是多少通过泛洪广播给全网所有路由器。最终每个路由器手里都有一张完全相同的、完整的全网地图。计算有了全网地图后每个路由器在自己脑海中独立运行Dijkstra 算法以自己为根节点计算出一棵到达所有其他节点的最短路径树。3.2 Dijkstra 算法核心贪心算法 (Greedy)逐步选择当前已知距离最短的节点通过松弛操作扩展已知最短路径的集合直到覆盖所有节点。应用著名的OSPF 协议就是基于此算法。它收敛极快且彻底消除了“计数到无穷大”的环路问题。4. Routing - Routing in the Internet (互联网的宏观路由架构)互联网太庞大了如果让一个路由器记录全球几十亿个 IP 的最短路径内存和算力早就崩溃了。因此互联网采用了层次化路由 (Hierarchical routing)。4.1 Hierarchy in the Internet互联网被划分为许多个自治系统 (Autonomous System, AS)。比如清华大学校园网是一个 AS中国电信也是一个 AS。4.2 Autonomous System, AS (自治系统)定义由单一管理机构控制的一组路由器和网络。每个 AS 都有一个全球唯一的 AS 编号 (ASN)。内部分工AS 内部使用IGP (内部网关协议)AS 之间使用EGP (外部网关协议)。4.3 Interior Routing Protocols (内部路由协议 IGP)在 AS 内部网络管理员可以随心所欲选择路由算法RIP (Routing Information Protocol)算法基于距离矢量 (Bellman-Ford)。指标以跳数 (Hop count) 为标准最大跳数限制为 15 跳16 即视为不可达。适合小型网络。OSPF (Open Shortest Path First)算法基于链路状态 (Dijkstra)。指标没有跳数限制依靠泛洪交换 LSA (链路状态公告)。适合复杂的大型企业网络。4.4 Routing to a single/multiple exit points (出口策略)单一出口 (Single Exit Point)小型企业网通常只有一个出口连接外部 ISP。配置极简但毫无冗余断网即失联。多出口 (Multiple Exit Point)大型网络有多个出口连接外部。支持负载均衡和高可用冗余但需要复杂的路由策略来决定流量从哪个口出去。4.5 Exterior Routing Protocol (外部路由协议 EGP)用于在不同的 AS 之间交换路由信息。跨系统不能简单地看“距离最短”还要考虑商业利益和国家政策。BGP (Border Gateway Protocol, 边界网关协议)是目前互联网核心唯一使用的外部路由协议。它是一种路径矢量协议 (Path Vector Protocol)。4.6 Internet structure (互联网的阶层)Tier-1 ISPs (一级/骨干 ISP)全球顶级的跨国运营商它们之间互联互通覆盖全球。Tier-2 ISPs (区域 ISP)国家或区域级运营商。Tier-3 ISPs (本地 ISP)提供宽带接入的本地服务商直接连接终端用户 (End Users)。5. Routing - BGP (边界网关协议互联网的外交官)5.1 Border Gateway Protocol (BGP-4) - BasicBGP 既不是链路状态也不是距离矢量而是“Path Vector” (路径矢量)协议。核心特性BGP 的路由选择不是基于“最短距离”而是基于策略 (Policy)。每个网络都有自己的“小算盘”比如必须走最便宜的路、绝不帮竞争对手免费转发流量、或者出于安全避免数据流经某些特定国家的 AS。5.2 Customers and Providers (客户与提供商)互联网的路由本质上是一门生意。客户 (Customers)需要“上网”的下游网络他们花钱向提供商购买带宽。提供商 (Providers)诸如电信、联通等大型运营商他们收钱办事负责把客户的数据送达全网。5.3 Customers - Providers Hierarchy (商业路由原则)寄快递比喻客户自己没有能力送达全球就把数据包裹交给提供商快递公司。路由底线路由器绝不会做亏本买卖。一个 AS 绝对不会让自己的网络成为两个毫无关系的网络的“免费中转站”。5.4 The Peering Relationship (对等方关系)Peer (对等方)两个体量相当的 AS比如谷歌和苹果或者联通和电信为了节省向更上层提供商交的过路费选择直接拉一根线互联互相免费交换彼此的数据。黄金法则对等方绝不为对等方提供中转服务(Peers do not provide transit for peers)。联通绝不会免费帮电信把数据中转给移动。5.5 BGP Messages (BGP 报文类型)Open建立 BGP 邻居连接。Keep Alive定期发送证明自己还活着。Update核心报文用于发布新路由 (announcing) 或撤销失效路由 (withdrawing)。Notification发生致命错误断开对等连接。5.6 BGP Route Selection Summary (BGP 选路原则)当到达同一目的地有多条路时BGP 会依次比对以下属性Highest Local Preference (本地优先级)内部策略设定数值最高的胜出。Shortest AS_PATH (最短 AS 路径)经过的 AS 数量最少。Lowest Router ID如果前面都一样选 Router ID 最小的。5.7 AS_PATH Attribute (BGP 核心属性)AS_PATH记录了这条路由自诞生起经过的所有 AS 的编号列表例如AS 100 - AS 200 - AS 300。防环机制当 BGP 路由器收到一条路由更新时如果发现在 AS_PATH 里看到了自己的 AS 编号说明出现了环路直接丢弃该路由5.8 SummaryBGP 通过路径矢量算法完美解决了 AS 间的选路和防环问题同时其复杂的策略接口支撑了当今庞大的互联网商业生态。6. Routing - Multicast Routing (组播路由)6.1 Multicast (组播的价值)如果要在网上开几千人的视频直播单播 (Unicast) 会撑爆服务器带宽。组播让数据只发送一份在网络中间的路由器处“分叉 (Fork)”大幅节省资源。6.2 Flooding (泛洪组播树)最原始的方法向所有接口泛洪。虽然能形成一棵覆盖全网的树但极大地浪费了无辜不看直播的主机的带宽。6.3 Reverse Path Broadcast (RPB, 反向路径广播)逆向思维的神奇应用RPB 的思路是反过来的。与其从源头找接收者不如从接收者出发往回找一条通往源头的最短路径。迷宫比喻在迷宫里从终点往起点走往往最容易。数据包顺着这条反向计算出的路径的正方向传输。这不仅确保了最高效送达还完美避免了环路兜圈子。6.4 RPB Pruning (反向路径广播 剪枝)Pruning (剪枝)如果某个路由器下属的终端都没人看这场直播它就会向源头发送“剪枝 (Prune)”信息告诉上游“别往我这发了我这没人要看”。优势通过剪枝组播树被修剪得极其精炼只包含那些真正需要数据的网络分支达到了带宽利用率的极致。6.5 One tree versus several trees (一棵树 vs 多棵树)One tree (共享树)所有组播数据不管谁是主播都走同一棵树状骨干。配置简单但路径不一定最优。Several trees (基于源的树)为每个不同的直播源单独建一棵树。路径最优但路由器维护开销极大。6.6 Addresses and joining a group (组播地址与 IGMP)IPv4 D 类地址(224.0.0.0/4)专门预留给组播使用。IGMP (Internet Group Management Protocol)终端主机用这个协议告诉身边的路由器“我要加入某个组播群聊” 或 “我要退群”。6.7 Multicast Routing in the Internet (常见组播协议)DVMRP (距离矢量组播路由协议)有点像路由界的“问路机制”基于距离矢量算法构建组播树。PIM (独立于协议的组播)不绑定特定的路由算法无论是 OSPF 还是 RIP 都能配合。PIM-DM (密集模式)假设全网都要看先发给所有人不要的人自己喊“剪枝”。适合用户密集的局域网。PIM-SM (稀疏模式)假设全网都没人要看只有主动请求的人才给发。适合用户分散在广域网的大型网络。7. Routing Spanning - Tree Protocol (生成树协议 STP)7.1 Ethernet Switch (二层交换机的隐患)交换机有三大功能Learning (学习)记录来源 MAC 地址和对应的物理端口。Forwarding (转发)查表并把数据帧从正确端口发出去。Filtering (过滤)丢弃不需要跨交换机的数据。7.2 Learning Could Lead To loops (学习可能导致环路)为了防止单点故障网络工程师通常会在两个交换机之间拉两根网线做冗余。但这会导致物理环路此时交换机的“学习”和对未知包的“泛洪广播”机制会引发广播风暴 (Broadcast Storm)。数据帧在环路中以光速疯狂兜圈子瞬间瘫痪整个网络。7.3 Preventing Loops (使用 STP 打破环路)Spanning Tree Protocol (生成树协议)的使命就是在物理上有环路的网络中通过算法自动阻塞掉某些备用链路构建出一个逻辑上绝对无环的“树状拓扑”。当主链路断开时STP 能动态唤醒被阻塞的链路实现网络自愈。7.4 How it Works? (STP 工作原理)选举根桥 (Root Bridge)全网交换机对比 ID选出一个具有最小 ID 的交换机作为整棵树的“树根”。计算路径成本所有非根交换机计算自己到达“根桥”的最短距离并挑选出离根最近的端口 (Root Port)。阻塞冗余链路交换机互相发送 BPDU (桥接协议数据单元)。经过一轮比拼比拼到达根的距离、发送者 ID 等把多余的、会导致环路的端口强行置于“阻塞 (Blocking)”状态。8. Names and Addresses: IPv6 (下一代互联网协议)8.1 Goal of Internet Protocol Addresses核心目标唯一标识、高效通信寻址、以及灵活的层次化分配。危机IPv4 (约 43 亿个) 已经接近枯竭目前活跃使用率极高。特别是对于中国等后发互联网国家IPv4 地址资源更是极其稀缺严重依赖 NAT 续命。8.2 Internet Protocol, Version 6 (IPv6)为了彻底解决地址枯竭问题IPv6 应运而生。它直接将地址长度从 32 位扩展到了128 位。8.3 Address Structure (地址结构)IPv6 地址通常被切分为三个部分全局路由前缀 (Global Routing Prefix)分配给站点的公网前缀。子网标识符 (Subnet Identifier)站点内部划分不同子网用。接口标识符 (Interface Identifier)设备网卡的唯一标识通常可由 MAC 地址自动转换生成。8.4 Assignment Type (地址类型)IPv6 彻底取消了广播地址 (Broadcast)取而代之的是以下三种单播 (Unicast)一对一通信。多播/组播 (Multicast)一对多通信。任播 (Anycast)多个设备使用同一个 IP。数据包会自动路由给在物理距离或路由距离上“离得最近”的那一个设备常用于全球 CDN 和 DNS 根服务器部署。8.5 Properties (IPv6 的核心优势)极其庞大的地址空间21282^{128}2128号称“能给地球上的每一粒沙子都分配一个 IP 地址”。简化的报文头去除了 IPv4 头部中复杂的碎片字段和 Header Checksum路由器处理效率大幅提升。更好的安全性IPv6 强制/内置支持了IPsec原生支持端到端的加密和身份认证。无状态自动配置 (SLAAC)设备插上网线就能通过路由器广播的前缀自己计算生成唯一的 IP 地址彻底摆脱了对 DHCP 服务器的依赖。