第5章：网络层-控制平面
路由协议
路由协议的目标：确定从发送主机到接收主机之间，通过路由器的网络较好的路径
路径：路由器的序列，分组将沿着该序列从源主机到达最后的目标主机
较好：最小代价，最快的，最不拥塞的
在路由计算中按照子网到子网的路径计算为目标，而不是主机到主机
最优化原则
汇集树(slink tree)：
此节点到其他节点的最优路径形成的树
路由选择算法就是为所有路由器找到并使用汇集树
路由的原则
路由选择算法的原则：
正确性： 算法必须正确且完整。它能保证数据包能一站站接力送达目标，并且路由表中包含了到达所有目标地址的路径，不存在无法处理的目标地址。
简单性：算法在计算上应简单高效。过于复杂的最优算法可能导致延迟过高而不实用，同时，算法本身不应为了收集路由信息而产生过量的额外网络流量。
健壮性：算法必须能适应变化。当网络流量或拓扑结构发生变化（如链路拥堵或中断）时，算法能快速适应，避免将数据导向问题链路。
稳定性：算法产生的路由不应频繁摇摆或振荡。路由路径应保持相对稳定，避免因路径不断变化引发网络动荡。
公平性：算法应对网络中所有站点（主机或子网）一视同仁，避免对某些站点产生不公平的偏好或歧视。
最优性：算法应力求达到某个或某些指标的最优，例如最短时延、最低费用等。但在实际中，获取绝对最优的代价可能很高，因此通常追求实际可用的“次优”解。
1 路由算法分类
路由信息分为全局和局部的
全局：所有的路由器拥有完整的拓扑和边的代价信息
link state 算法
分布式：路由器只知道与它有物理连接关系的邻居路由器，和到相应邻居路由器的代价值。迭代的与邻居交换路由器信息、计算路由信息
distance vector 算法
静态路由和动态路由
静态：路由随时间缓慢变化
动态：路由变化很快，周期性更新，根据链路代价的变化而变化
2 LS路由算法
链路状态路由选择(link state routing)基本工作过程
发现相邻节点，获知对方网络地址
在一个路由器上电之后，向所有线路发送HELLO分组
其他路由器收到分组后，回送应答，在应答分组中告知自己的名字
在LAN中，通过广播HELLO分组，获得其他路由器信息，可以认为引入一个人工节点
测量到相邻节点的代价（延迟，开销）
实测法，发送一个分组要求对方立刻响应
回送一个ECHO分组
通过测量时间可以估算出延迟情况
组装一个LS分组，描述它到相邻节点的代价情况
发送者名称
序号，年龄
列表：给出相邻节点和对应的延迟
将分组通过扩散的方法发到所有其他路由器
顺序号：用于控制无穷的扩散，每个路由器都记录（源路由器，顺序号），发现重复或旧的就不扩散
具体问题1:循环使用问题
具体问题2:路由器崩溃之后序号从0开始
具体问题3:序号出现错误
解决问题：年龄字段
生成一个分组时，年龄字段不为0
每一个时间段，AGE字段减1
Age字段为0的分组将被抛弃
通过
Dijkstra算法找出最短路径（这才是路由算法）每个节点独立计算出来到其他节点的最短路径
迭代算法：第k步能够知道本节点到k个其他节点的最短路径
3 DV算法算法
距离矢量路由选择
基本思路：
各路由器维护一张路由表
各路由器与相邻路由器交换路由表
根据获取的路由信息更新路由表
代价衡量：算法通过测量“代价”来选择最佳路径。这个代价可以是跳数、延迟或队列长度等指标，并且是通过实际测量相邻节点之间的链路状态来获得的。
路由更新逻辑：每个节点都遵循一个固定步骤来更新自己的路由表：
测量到所有邻居的代价。
接收所有邻居声称的、它们到目标节点B的代价。
计算“本节点A → 邻居X → 目标B”的总代价。
从所有可能路径中，选择总代价最小的那个邻居Z，作为到达B的下一跳，并记录新的总代价。
这个过程的核心是：每个节点不关心完整网络拓扑，只依赖邻居的“部分承诺”来做本地最优决策。
触发
触发条件：每个节点的计算是被动、被事件驱动的，仅在两种情况下被触发：
本地到邻居的链路代价发生变化。
从邻居收到了新的距离矢量更新报文。
节点行为：当事件触发后，节点会重新计算到达所有目标的代价估计值。如果计算结果有变化，它就会将这个新的距离矢量通告给所有邻居。
扩散过程：这种“计算-通告”的过程会层层传递下去。一个节点的变化会影响其邻居，邻居的变化又会继续影响邻居的邻居，直到全网信息达到一致状态。这个过程是分布式的，没有统一的控制中心。
特性
核心特性：距离矢量算法存在好消息传播快，坏消息传播慢的非对称性。
“好消息”示例：当一个节点接入网络，或出现了到某个目标更短的路径时，这个“好消息”能以每个交换周期前进一个路由器的速度快速传播，迅速被全网获知。
“坏消息”指什么：这里的“坏消息”特指某个目标变得不可达，或路径代价大幅增加的情况。
问题场景：假设A节点失效（到A的链路代价突变为无穷大）。此时，B和C需要通过多次信息交换，才能逐步“发现”A已不可达。
错误传播过程：
A刚失效时，B知道A不可达，但C还不知道。C仍以为可以通过B以较小的代价（如2跳）到达A。
B收到C的矢量后，误以为“C有通往A的路径（代价2）”，于是B更新自己的路径为“B->C->A”，代价变为2+1=3。
同理，C收到B的新矢量（代价3）后，会更新自己的路径为“C->B->A”，代价变为3+1=4。
恶性循环：这个过程会不断重复，B和C相互“误导”，各自计算出的到A的路径代价在每一次信息交换后都增加2（3, 4, 5, 7, 9…），直到代价最终增长到协议定义的“无穷大”（如16或更大），才能判定A不可达。这个过程极其缓慢，在网络规模大时会严重影响收敛速度。
4 LS与DV比较
消息复杂度
高。每个节点都需要将本地链路状态洪泛到全网。对于有 n 个节点、E 条链路的网络，会发送 **O(nE)** 个报文。
低。节点只与直接邻居交换距离矢量信息，每次交换的信息量也相对较小。
DV胜出 DV 产生的控制流量和开销更小。
收敛速度
快。通过 O(n²) 的 Dijkstra 算法计算，能够快速响应网络变化，收敛迅速。
慢。采用迭代的、异步的分布式算法，收敛速度较慢，尤其在拓扑变化时。
LS胜出 LS 能更快地适应网络变化，实现稳定。
健壮性 （应对故障/错误）
高。每个节点独立计算自己的完整路由表，不依赖邻居的计算。 即使有节点通告了不正确的链路代价，错误信息的影响范围有限，不易扩散。
低。节点计算路由严重依赖邻居提供的信息（“传闻路由”）。 一个节点的错误计算会传递给邻居，并可能扩散到全网，导致路由环路或“计数到无穷”问题。
LS胜出 LS 架构更分散、独立，局部错误不会导致全网性问题。
核心特性总结
**“局部的信息，全局传播”** 收集本地链路状态，然后广播给全网，让每个节点都拥有一张完整的网络拓扑图。
**“全局的信息，局部传播”** 每个节点只掌握到所有目标的距离和方向（下一跳），并只在邻居间交换这些摘要信息。
两者在信息传播和计算方式上截然相反。
主要问题
链路状态洪泛可能造成网络泛洪开销。算法在特定情况下（如对拥塞代价反应过快）可能出现路由震荡。
存在慢收敛和计数到无穷的经典问题。基于“传闻”的更新机制可能产生路由环路。
LS 的代价是洪泛开销，DV 的代价是收敛慢和环路风险。
5 自治系统中的路由选择
5.1 RIP
RIP：Routing Information Protocol
Distance vector算法
距离矢量：每条链路cost=1，最大为15hops，超过标记为不可达
DV每隔30s和邻居交换DV，通告
在对方的请求下可以发送通知报文
每个通告包括最多25个目标子网
链路失效和恢复
如果180秒没有收到通告信息--》 邻居或者链路失效
发现经过这个邻居的路由已经失效
新的通告报文会传递给邻居
邻居会因此发出新的通告
链路失效快速的在整网中传输
使用毒性逆转阻止ping-pong回路
RIP进程处理
RIP以应用进程的方式实现：route-d(daemon)
通告报文通过UDP报文传送，周期性重复
网络层的协议使用了传输层的服务，以应用层实体的方式实现
5.2 OSPF
OSPF：Open Shortest Path First
open：标准可公开获得
使用LS算法：
LS分组在网络中分发
全局网络拓扑、代价在每一个节点中保存
路由计算采用 Dijkstra 算法
OSPF通告信息中携带：每一个邻居路由器一个表项
通告信息会传遍全部网络（通过泛洪）
在IP数据报上直接传送OSPF报文
IS-IS路由协议：几乎跟OSPF一致
OSPF比RIP多的高级功能
安全性增强：报文认证
内容：所有OSPF路由器之间交换的协议报文（如Hello、LSA）都需要经过身份认证才能被接受和处理。
意义：这可以有效防止恶意设备伪造路由信息、发起路由欺骗攻击，从而提升了网络整体的安全性。RIP通常没有内置的认证机制。
负载均衡：支持多条等价路径
内容：当到达同一个目标网络存在多条代价（Cost）相同的路径时，OSPF可以将流量同时分配到所有这些路径上。
意义：这实现了负载均衡，充分利用了网络带宽，提高了数据传输的效率。而RIP只会选择并保存其中一条最佳路径。
服务质量区分：支持按服务类型（TOS）计算路径
内容：可以为同一条物理链路针对不同类型的服务定义不同的代价。例如，为“实时语音”设置高代价以避免使用高延迟的卫星链路，而为“普通网页浏览”设置低代价。
意义：这使得OSPF能够根据数据包的服务类型（如延迟敏感、带宽敏感）计算出不同的最优路径，为**服务质量（QoS）** 提供了基础支持。RIP不具备此能力。
集成化支持：单播与多播
内容：通过MOSPF扩展，OSPF可以利用相同的链路状态数据库来为组播流量计算分布树。
意义：实现了单播路由和组播路由协议的集成，简化了网络管理和拓扑维护。RIP是纯粹的单播路由协议。
可扩展性：层次化设计
内容：OSPF可以通过划分区域来构建层次化网络。其中必须有一个骨干区域，其他非骨干区域必须与骨干区域直接相连。
意义：这是OSPF最重要的高级特性之一。层次化设计能够：
大幅减少路由更新信息的传播范围，降低路由器CPU和内存开销。
将网络拓扑变化的影响限制在单个区域内，增强网络的稳定性和可扩展性。
这使得OSPF能够支持超大型网络，而RIP作为平面协议，网络规模严重受限。
6 层次路由
平面路由
平面路由是指网络中所有路由器地位平等，运行同一套路由算法（如DV或LS）来获取全网路由信息。这种架构在互联网规模巨大时暴露了三大致命问题：
可扩展性问题：
DV算法：每个路由器维护的距离矢量表会变得异常庞大，且拓扑变化时“坏消息传播慢”，在大型网络中几乎无法收敛。
LS算法：链路状态分组需要向全网几百万个节点泛洪，对带宽和存储造成巨大压力，最短路径算法（如Dijkstra）的计算开销也变得不可承受。
管理自治问题：
不同的网络运营商（如中国移动、中国电信）希望完全按照自己的策略管理内部网络，而不受外界干涉。
希望对外隐藏自己网络的拓扑细节，这既是出于安全考虑，也是商业需求。
互联需求：尽管希望内部自治，但所有网络又必须能够相互连接。
层次路由
为解决上述问题，互联网采用了层次路由，核心是将互联网划分为多个自治系统。
核心概念：自治系统
自治系统：一个在单一技术管理机构下，运行统一路由策略的一组路由器集合。例如，一个大学、一个公司或一个ISP的网络都可以是一个AS（autonomous systems）。
AS编号：每个AS由一个全球唯一的AS号码标识。
两层路由架构
AS内部路由：
在同一个AS内部运行的路由协议，称为内部网关协议。
不同的AS可以根据自身规模和管理需求，选择运行不同的IGP，例如小型网络可用RIP，大型网络则用OSPF。
作用：解决AS内部的路由问题，实现精细、快速的内部路由。这完美解决了可扩展性和内部管理自治的问题。
AS间路由：
在不同AS之间运行的路由协议，称为外部网关协议。
由每个AS边缘的网关路由器负责执行。
作用：解决AS之间的互联互通问题。EGP协议（主要是BGP）的核心功能不是寻找“最优路径”，而是基于策略（如商业合约、安全要求）来选择和控制路由的传播，这满足了对外隐藏细节和策略管理的需求。
7 ISP之间的路由选择
7.1 BGP
BGP（Border Gateway Protocol）：自治区域路由协议
事实上的标准
将互联网上各个AS粘在一起的胶水
BGP提供给每个AS以下方法
EBGP：从相邻的Ases那里获取子网可达信息
iBGP：将获得的子网可达信息传遍到AS内部的所有路由器
根据子网可达信息和策略来决定到达子网的好路径
允许子网向互联网通告其位置
基于路径矢量算法
不仅仅是路径矢量，还包括达到各个目标网络的详细路径（AS序号列表），能够避免简单DV算法的路由环路问题
BGP的核心是运行在不同AS的边界路由器（称为对等体，BGP peers）之间。它们通过半永久的TCP连接（通常是端口179）来建立稳定的BGP会话，并通过此连接交换路由信息。
路径矢量协议：BGP被称作“路径矢量”协议。它通告的不仅仅是“距离”（如跳数），而是一条完整的“路径”。这条路径实际上是一个AS编号的序列，指明了到达某个目标网络需要依次经过哪些自治系统。
BGP通告一条路由时，会附带丰富的路径属性，正是这些属性使得BGP强大而灵活。
路由的构成：一条BGP路由 = 目标网络前缀 + 路径属性。
关键属性：
AS_PATH：这是路径矢量核心体现，记录了该路由通告已经经过的AS列表。它有两个重要作用：防止环路（如果路由器在AS_PATH中看到了自己所属的AS号，则拒绝该路由），以及作为选路依据（通常路径越短越优）。
NEXT_HOP：指明到达下一跳AS的IP地址（通常是相邻AS边界路由器的接口IP）。本AS内的路由器需要根据IGP（如OSPF）找到去往这个IP地址的路径，这个过程称为“下一跳可达性”解析。
基于策略的路由：这是BGP与OSPF等IGP的本质区别。BGP路由的接收、传播和选择主要基于策略，而非单纯的技术最优。
输入策略：路由器收到邻居通告的路由后，可以基于策略决定接受或过滤。例如，拒绝经过某个竞争对手AS的路由，或只接受特定前缀的路由。
输出策略：路由器决定将哪些路由通告给其他邻居。例如，可能只向客户AS通告全部路由，而向同行AS只通告部分路由。
BGP通过四种报文在TCP连接上进行交互，确保了会话的可靠和可控：
OPEN
建立BGP对等体会话，用于参数协商和身份认证。
UPDATE
BGP的核心报文，用于通告新的有效路由，或撤销（Withdraw）不再可达的路由。
KEEPALIVE
定期发送以保活TCP连接，并确认OPEN报文。
NOTIFICATION
当检测到错误（如报文格式错误、策略冲突）时发送，随后会关闭BGP连接。
最后更新于