Unit 6. Routing
路由
在互联网中转发和路由数据包的方法和策略。
互联网采用了一种算法：分布式算法运行
Djskstra算法...以及在网路中的应用。
内部自治系统 OSPF
自治系统之间 BGP
Main Point
Approaches
Flooding
Source routing 源路由，无需转发表。符合强端到端原则，但是很少被使用，因为其安全性。
Forwarding table 目的地地址，哪个接口退出...路由算法的任务是填充转发表
Spanning tree 生成树...路由算法 OSPF/RIP
Algorithms
Bellman-Ford "distance vertor" algorithm: Used by RIP
Dijkstra's shortest path first "link state" algorithm: Used by OSPF
Internet routing
Hierarchical routing
BGP - path vector routing and local policies
Multicast routing
Spanning Tree Protocol（STP）
1. Routing - Basic
路由的基本概念和原则
1.1. The Problem
由 A 到 B 的传输。
应当选择最短路径？最快路径？还是最小花费的路径？
1.2. Flooding
泛洪。最简单的方法
泛洪机制：就是把数据包传输经过所有路由。
经过所有路径，最后当然也会到达 B点
但是效率非常低...还有可能陷入无限循环...
效率低这点我们无力改变...
所以我们至少需要保证他不会陷入无限循环
网络拓扑
1.3. Source Routing
A 记录了拓扑结构。记录每个路由之间的最短路径。
能够保证他能到达 B。
和泛洪一样，路由 无需提前记录，只是主机需要进行记录。
但是 A 主机会产生一些 Debuff，主要是携带大量的地址，缓存变得很大...
1.4. Forwarding Table
路由的转发表。
路由填充数据来实现这个功能......
填充方法：我们后面会讲解
1.5. Spanning Tree
当 host 多了起来之后...每台主机到达固定的 destination 之后的路径清晰化了...
生成树用于创建路由条目...
我们需要知道成功的标准是什么？
What is our metric ?
最短距离
最小跳数
最小延迟
最大吞吐量
least load path
most reliable path
lowest cost path
安全性最高
这些选择都可以
Annotated Graph
Annotated Graph（带注释的图）
最小成本...
简单的网络当然可以手动计算...
但是复杂的网络我们只能利用自动化的算法来计算了...
1.6. Multipath
多路径行为...
当主机的以往路径的某一条非常拥挤的时候...
会选择一些就近的转发..可能不会符合最小成本...
流量负载均衡
1.7. Multicast
多播
终端主机希望把数据包发送到其他的主机（部分），我们不能利用广播策略，因为不是所有的主机都需要收到。
显然我们可以逐个发送...
但是我们可能想知道是不是能复制策略...
多播（Multicast）就是一种更聪明的方法。它允许你只发送一份视频，然后网络会自动把这份视频复制给所有需要看的朋友。这样，不管有多少人要看，你只需要发送一次，网络也会更轻松。
2. Routing - Distance Vector Protocol: Bellman Ford Algorithm
距离矢量协议...计算距离，得到最生成树...
2.1. Bellman-Ford 算法
Bellman-Ford算法是一种用于计算单源最短路径的算法，它可以通过处理负权边来找到最短路径。这个算法的核心思想是通过多次松弛操作，逐步更新节点之间的最短路径。
算法原理
初始化：将源点到自身的距离设为0，到其他所有节点的距离设为无穷大。
松弛操作：对图中的所有边进行松弛操作，尝试更新路径长度。如果通过某条边可以找到更短的路径，就更新该路径的长度。
迭代次数：对所有边进行 V-1 次松弛操作（ V 是节点数）。因为最短路径最多包含 V-1 条边。
检测负权环：在 V-1 次松弛操作后，再进行一次松弛操作。如果还能更新路径长度，说明图中存在负权环。
有点类似动态规划的思想，首先计算包含一部分结点的路径的权重...然后逐步扩展
相当于进行一次全遍历，遍历完一次之后会得到一个最优解...
2.2. Distributed Bellman-Ford Algorithm
Bad news travels slowly
当某个结点失效的时候，除了相邻节点之外...其他结点仍然记录着失效信息
假设你告诉朋友：“我知道去出口的路，要经过我这里，再走3步。”但突然，你发现前面的路被堵死了，这条路走不通了！这就是“坏消息”——某个节点失效了，或者某条路径不通了。但是，你不能马上告诉所有朋友这条路走不通，因为你只能告诉相邻的人。相邻的人再告诉他们的朋友……这个过程一层层传下去，速度很慢。而且，中间还可能会出现一些误会。
Good news travels fastly
“好消息传得快”是怎么回事？好消息（比如发现了一条更短的路）传得快，是因为一旦你发现了一条更短的路，你马上就可以告诉相邻的人，他们也会马上更新自己的路径表，然后告诉他们的邻居……这个过程很快，因为每个路由器都会优先更新更短的路径。
2.3. Counting to Infinity Problem
怎么解决“坏消息传得慢”的问题？
为了加快坏消息的传播速度，距离矢量协议里有一种方法叫“毒性反转”（Poison Reverse）。
毒性反转的意思是：
当你发现某条路不通了，你不会简单地告诉邻居“这条路不通”
而是告诉他们：“这条路的成本是无穷大！”
这样，邻居们会更快地意识到这条路走不通，从而更新自己的路径表。
解决方法：
水平分割（Split Horizon）
毒性逆转（Poison Reverse）
触发更新（Triggered Update）
最大跳数限制
3. Routing Protocol - Dijkstra's shortest path first algorithm
Dijkstra算法，这是链路状态路由协议（Link State Routing Protocol）中常用的算法，用来计算最短路径。
3.1. 拓扑结构上的 Dijkstra
贪心算法...逐步选择最小的路径...
适用于链路状态协议：比如OSPF（Open Shortest Path First，开放最短路径优先）协议，就是用Dijkstra算法来计算路由的。
这个会进行逐次计算？？？
感觉和数据结构课上学的不大一样啊...
3.2. Dijkstra
Dijkstra算法是一种高效的单源最短路径算法，适用于非负权图。它通过贪心策略和松弛操作逐步构建最短路径树，能够可靠地找到从源节点到所有其他节点的最短路径。
Dijkstra算法基于松弛操作（Relaxation）和贪心策略，其核心思想是逐步扩展已知最短路径的集合，直到覆盖所有节点。
4. Routing - Routing in the Internet
综合介绍路由器和互联网
4.1. Hierarchy in the Internet
互联网规模庞大，我们需要进行适当的分解...
互联网的层次结构
一些个自治系统。每个系统之间有一个 Exterior Gateway Protocol
4.2. Autonomous System, AS
自治系统是由单一管理机构控制的一组路由器和网络。每个AS都有一个唯一的AS编号（ASN），并使用内部路由协议（如OSPF）管理内部路由，通过外部路由协议（如BGP）与其他AS交换路由信息。
之后的视频会学习 BGP-4 协议...
4.3. Interior Routing Protocols
一般来说我们综合应用Routing的各种协议和策略
RIP
Routing Information Protocol
算法类型：基于距离矢量算法（Distance Vector Algorithm），使用跳数（hop count）作为路径度量标准。
更新机制：RIP路由器每隔30秒向相邻路由器广播整个路由表，通过距离矢量叠加的方式更新路由信息。
最大跳数限制：最大跳数为15跳，超过15跳的网络被认为是不可达的。
OSPF
OSPF（Open Shortest Path First）
算法类型：基于链路状态算法（Link State Algorithm），使用Dijkstra算法计算最短路径。
更新机制：路由器通过洪泛（flooding）机制交换链路状态信息（LSA），建立全网拓扑数据库，动态计算最短路径。
无跳数限制：没有跳数限制，适合大规模网络。
4.4. Routing to a single/multiple exit points
路由到单一出口点与多出口点（Routing to Single/Multiple Exit Points）
在互联网路由中，出口点（Exit Point）是指数据包离开本地网络（如企业网络、ISP网络）进入其他网络（如互联网）的节点。根据网络的出口点数量和设计，路由策略可以分为单一出口点路由和多出口点路由。
单一出口点路由（Single Exit Point Routing）
单一出口点路由是指网络中只有一个出口点连接到外部网络。所有流量都通过这个单一出口点进出网络。
单一出口点路由适用于小型网络，配置简单，但缺乏冗余
多出口点路由（Multiple Exit Point Routing）
多出口点路由是指网络中有多个出口点连接到外部网络。流量可以根据策略选择不同的出口点。
多出口点路由适用于大型网络，支持负载均衡和冗余，但需要复杂的路由策略
在实际网络设计中，选择单一出口点还是多出口点路由策略，取决于网络的规模、拓扑结构以及对冗余和性能的要求。
4.5. Exterior Routing Protocol
外部路由协议（Exterior Routing Protocols）
用于在不同的自治系统（Autonomous Systems, AS）之间交换路由信息。与内部路由协议（IGP）不同，外部路由协议需要处理跨自治系统的复杂网络拓扑，并支持多种策略以满足不同网络运营商的需求。目前，互联网中最主要的外部路由协议是边界网关协议（Border Gateway Protocol, BGP）
边界网关协议（Border Gateway Protocol, BGP）
是一种路径矢量协议（Path Vector Protocol），用于在自治系统之间交换路由信息。它是互联网的核心协议之一，负责在不同ISP（Internet Service Providers）之间选择最佳路径，确保数据包能够高效、可靠地传输。
4.6. Internet structure
骨干ISP（Backbone ISPs）- 一级ISP（Tier-1 ISPs）
区域ISP（Regional ISPs） - 二级ISP（Tier-2 ISPs）
本地ISP（Local ISPs）- 三级ISP（Tier-3 ISPs）
接入网络（Access Networks）- 接入网络是终端用户接入互联网的第一跳网络
终端用户（End Users）- 终端用户是互联网的最终使用者
5. Routing - BGP
自治系统的一种协议..
5.1. Border Gateway Protocol（BGT-4） - Basic
不是一个 link-state or distance-vector routing protocol...
instead, BGP uses what is called a "Path vector" 路径向量
BGP - 特定自治系统的策略
每个网络（自治系统）都有自己的“小算盘”，比如它可能希望数据走最快的路，或者走最安全的路，或者避免经过某些地方。BGP允许每个网络根据自己的策略来决定数据包的走向。
5.2. Customers and Providers
客户就是那些需要“上网”的小网络。它们自己没有足够的资源或者能力去连接整个互联网，所以需要找一个“大靠山”来帮忙。
提供商就是那些“大靠山”，它们是大型的网络运营商，比如电信、联通、移动等。
5.3. Customers - Providers Hierarchy
客户和提供商之间的关系可以用“寄快递”来比喻：
客户：就像一个寄快递的人，他们有自己的包裹（数据），但没有能力把包裹送到很远的地方。
提供商：就像快递公司，客户把包裹交给他们，快递公司负责把包裹送到目的地。
BGP的作用：BGP就像是快递公司内部的“物流系统”，它告诉快递员（路由器）包裹应该怎么送，经过哪些中转站（网络）。
他们不会通过同一级别的中间节点流过...
5.4. The Peering Relationship
对等方peer 不能为对等方peers 提供中转服务
5.5. BGP Messages
Open
建立 BGP 部分
Keep Alive
握手 at regular intervals
Notifications
shuts down a peering session
Update
announcing new routes or withdrawing previous annouced routes
5.6. BGP Route Selection Summary
Highest Local Preference
Shortest ASPATH
Lowest router ID...
5.7. ASPATH Attribute
AS_PATH 是 BGP 里的“路线图”，记录了路由经过的所有自治系统编号。它有两个重要作用：防止环路和选择最优路径。通过 AS_PATH，网络可以更高效、更安全地传输数据。
自治系统路径...
一些个数字序列...
防止环路
选择最优路径
连接 Provider 和 Custormer
5.8. Summary
path vecttor algorithm
allows loops to be detected easily
andcomplex interface
6. Routing - Multicast Routing
6.1. Multicast
多播 - 组播...
你有一个视频会议，需要把视频内容同时发送给很多人。如果你用普通的方式（单播，Unicast），就需要给每个人单独发送一份视频，这样会浪费很多带宽和资源。而组播（Multicast）就是一种更聪明的方式，它可以让数据只发送一份，然后在网络中“分叉”，同时到达多个接收者。
6.2. Flooding
泛洪策略...这实际上是向所有接口发送数据...
最终数据包会到达终点...
通过此来形成 multicast tree 组播树
但是效率未免太低
6.3. Reverse Path Broadcast（RPB）
aka Reverse Path Forwarding（RPF）
反向路径广播 - 使用了反方向的生成树
RPB 是一种广播技术，主要用于组播通信。它的核心思想是：通过反向路径来选择数据包的传输路径，确保数据包能够高效地到达所有目标节点，同时避免环路。
避免环路：RPB 通过反向路径检查，确保数据包不会在环路中兜圈子，从而避免广播风暴。
高效传输：每个节点只转发数据包的一个副本，不会重复转发，节省了网络带宽。
有点类似泛洪...但是每一步的策略会更加具体...
逆向思维
你在一个迷宫里，要找到一条最短的路到达终点。RPB 的思路是反过来的：它从终点（接收者）开始，往回找一条最短的路到起点（发送者）。这样，数据包就可以沿着这条反向路径传输，确保每个节点都能收到数据包的一个副本。
剪枝
不需要的终端发送剪枝信息...multicast 只对部分 host terminal 发送信息，其他的 terminal 通过剪枝策略可以极大简化网络，提高效率
6.4. RPB + Pruning
数据包发送 loop-free 给每个end host
路由不关心 host 发送 prune 信息 towards source
生成树是最小 cost 的树，从结点开始...
高效利用带宽：通过剪枝，减少了不必要的数据传输。
避免冗余：每个节点只接收一次数据包，不会收到重复的副本。
节省资源：优化后的组播树减少了网络负载，提高了传输效率。
6.5. One tree versus several trees
“一棵树”
所有组播数据都通过同一条路径（树状结构）传输。这种方式通常用于简单的组播场景，比如直播服务。
“多棵树”
为不同的组播源或不同的组播组建立多条路径。这种方式更复杂，但也更灵活，适用于复杂的组播场景。
一棵树（Single Tree）
优点：简单、高效
缺点：不够灵活，可能会浪费资源
适用场景：简单的组播场景，比如单个直播源
多棵树（Several Trees）
优点：灵活、节省带宽、容错性好
缺点：复杂、资源开销大
适用场景：复杂的组播场景，比如多个直播源或多个组播组
6.6. Addresses and joining a group
IPv4
Class D addresses are set aside for multicast
IGMP*
Internet Group Management Protocol
6.7. Multicast Routing in the Internet
DVMRP
Distance Vector Multicast Routing Protocol
DVMRP 是一种基于“距离向量”的组播路由协议。它的名字听起来很复杂，但其实原理有点像我们熟悉的“问路”。
问路机制：每个路由器都问它的邻居：“嘿，你知道怎么到目的地吗？”然后邻居会告诉它最近的路径。
更新路由表：路由器会根据邻居的回答更新自己的“地图”（路由表），记录下到达每个目的地的最佳路径。
构建组播树：当有组播数据需要发送时，DVMRP 会根据路由表构建一棵“组播树”，数据沿着这棵树传输，确保每个接收者都能收到。
PIM
Protocol Independent Multicast
PIM 是一种“协议无关”的组播路由协议，意思是它不依赖于具体的单播路由协议，而是利用现有的路由信息来实现组播。PIM 有两种主要模式：PIM-DM（密集模式） 和 PIM-SM（稀疏模式）。
PIM-DM（密集模式）
原理：PIM-DM 假设网络中的每个子网都有组播组成员，所以它会先“洪泛”数据到所有地方，然后再剪掉不需要的分支。
特点：适合组播成员比较密集的小型网络，因为它会浪费一些带宽来“洪泛”数据。
PIM-SM（稀疏模式）
原理：PIM-SM 假设网络中的组播成员比较分散，所以它只向明确请求数据的成员发送数据。它会通过一个“中心点”（RP，Rendezvous Point）来管理组播树。
特点：适合大型网络，因为它更节省带宽，不会浪费资源在没有成员的地方。
7. Routing Spanning - Tree Protocol
路由主题
网路层 + IP 地址
如何 loops prevented?
7.1. Ethernet Switch
检验 header of arriving frame
学习（Learning）
交换机记录每个设备的MAC地址和端口。
转发（Forwarding）
交换机根据目的MAC地址把数据帧发送到正确的端口。
过滤（Filtering）
交换机避免不必要的数据传输，提高网络效率。
7.2. Learning Could Lead To loops
在某些情况下，交换机的学习过程可能会导致环路（Loop），这可能引发网络问题，比如广播风暴（Broadcast Storm）。
假设一个交换机网络中存在物理环路（比如两个交换机通过两条链路连接），交换机可能会错误地学习到错误的MAC地址路径，从而导致数据帧在环路中不断循环。
如何避免环路？
为了避免学习过程导致的环路问题，网络中通常会使用生成树协议（STP，Spanning Tree Protocol）。
7.3. Preventing Loops
Spanning Tree Protocol
生成树协议的作用：
打破物理环路：STP通过计算网络拓扑，选择一条最优路径，将其他路径置于“阻塞”状态，从而打破物理环路。
动态调整：如果某条链路故障，STP可以重新计算拓扑，恢复链路，确保网络的高可用性。
7.4. How it Works?
STP 的工作原理：
选举根桥（Root Bridge）：网络中所有交换机通过选举，选择一个“根桥”作为参考点
bridge protocol data unit
sets distance field to 0
计算路径成本：每个交换机计算到根桥的路径成本，选择最优路径
every sitch broadcasts until it hears a "better" message
A root with a smaller ID
A root with equal ID, but with shorter distance
Ties broken by smaller ID of sender
阻塞冗余链路：将非最优路径置于阻塞状态，防止环路形成
本地交换机只会在根端口和指定端口上转发
8. Names and Addresses: IPv6
互联网协议版本6
8.1. Goal of Internet Protocol Addresses
唯一标识：每个设备都有一个独一无二的地址，避免混淆。
高效通信：通过地址，数据包可以快速找到目标设备，就像快递包裹找到收件人。
灵活分配：地址可以分层次分配，方便管理和扩展。
IPv4 的使用率 ~35%
8.2. Internet Protocol, Version 6
在中国 IPv4 的可能及其稀缺
IPv6 是互联网协议的最新版本，用来替代老版本的 IPv4。IPv4 的地址长度是 32 位，总共只能提供约 43 亿个地址。随着互联网的发展，设备越来越多，IPv4 地址已经不够用了。因此，IPv6 应运而生。
8.3. Address Structure
全局路由前缀（Global Routing Prefix）
子网标识符（Subnet Identifier）
接口标识符（Interface Identifier）
8.4. Assignment & Type
单播地址（Unicast）
多播地址（Multicast）
任播地址（Anycast）
保留地址（Reserved）
8.5. Properties
更大的地址空间：IPv6 地址长度是 128 位，可以提供几乎无限的地址（3.4×10^38 个地址）。
简化的报文头：IPv6 的报文头更简洁，减少了处理开销，提高了传输效率。
更好的安全性：IPv6 内置了 IPsec（IP 安全协议），可以提供更强的加密和认证功能。
自动配置：设备可以自动获取 IP 地址，无需手动配置或依赖 DHCP 服务器。
Last updated