计算机网络-自顶向下方法-笔记【第5章-网络层-控制平面】

学习的课程及图片来源：中科大郑烇、杨坚全套《计算机网络（自顶向下方法 第7版，James F.Kurose，Keith W.Ross）》课程

5 网络层-控制平面

5.1 导论

5.2 路由选择算法

路由可以看作是子网到子网的路由【因此就是找到路由器到其他路由器的较好路径（到了这个路由器就到了这个子网）】，而不是主机到主机的路由，因为可以想象 IPv4 那么 40 亿多个主机，要确定其中两个主机的最佳路由路径，很困难。

事实上，对于不在一个子网的主机的第一跳一定是发送给这个子网的网关，最后一跳一定是由目标子网的网关发送给目标主机

原则

汇集树：sink tree 这个节点到其他所有路由器的最优路径形成的树

路由选择算法就是要为所有的路由器找到并使用汇集树

分类

• 全局/分布式
• 静态/动态：非自适应/自适应

link state-全局算法

链路状态算法：即Dijkstra 算法

贪心算法

1. 获得整个网络拓扑
2. 使用Dijkstra 算法获得到达其他路由器的最短路径

扩散即泛洪 flooding 让所有的路由器都能得到这个链路状态分组 LS。大家都这么做，所有可以让每个路由器都能得到其他所有节点的状况

迭代算法即 Floyed 算法 所有顶点的最短路径(非负权值)

一个节点 A 收到来自其他节点 B 的泛洪分组，那么要给这个节点发送 ACK 确认，同时将这个分组发送给 A 的其他的邻居 C D E……并期待它们的确认，如果没有收到确认，那么会 A 会一直重复发这个泛洪分组

因此泛洪是可靠的，能够保证所有的节点都得到这个分组的信息

distance vector-分布式算法

即 Bellman-Ford 算法

动态规划

距离矢量中要记录

1. 目标节点
2. 到达目标节点路径上的下一跳
3. 到达目标节点所需要的 cost

和邻居交换距离矢量，再加上自己到邻居的代价，即可得到到达目标的最低代价

定期测量；定期交换

• 自己到邻居的代价改变了，要重新计算
• 邻居给自己的到达目标节点的代价改变了，邻居重新发给自己了，要重新计算
• 自己的 DV 更新改变后要通知其他的邻居

特点：

• 好消息传得快

• 坏消息传的慢，需要很多次迭代才能发现不可达

  • 解决办法

    

    因为 C 要通过 B 才能到达 A，所以当 B 向 C 请求到达 A 时，C 应当告诉 B 为 INF。但告诉 D 时 C 会告诉 D 自己是可达的，这样就形成了水平分裂，C 的左右两边的信息不一样

  • 

    但水平分裂在环状的网络拓扑中效果不好，可以缓解传得慢【C 立即知道不可达】，但不能解决【A，B 需要很长时间才能发现】

LS 和 DV 的比较

上面的振荡是指可能上个时间选择这条路径，这个时间因为这条路径拥塞，所以换了一条，下个时间因为拥塞用换回来

5.3 自治系统内部的路由选择协议-内部网关协议

前面介绍的是抽象的算法，接下来是具体的协议，协议来实现算法

RIP-适合小网

Routing Information Protocol

基于 DV 算法

• 每条链路的 cost = 1，最大跳数为 15，如果跳数超过 15，即当作不可达
• 通告 advertisements：
  1. 邻居定期每隔 30 s，则交换通告
  2. 如果对方请求，那么可以直接发送通告
• 每个通告最多通告 25 个目标网络的 DV，因此适合小网的自治

毒性逆转就是水平分裂

网络层的功能借助应用进程来实现，为了实现这个功能，还借助了传输层的 UDP

OSPF-适合大网

开放最短路径优先 Open Shortest Path First

基于 LS 算法

直接在 IP 数据报上传送 OSPF 报文，不需要借助传输层协议

允许根据多个代价（跳数、延迟等）来计算最优

在大型网络中支持层次性 OSPF

分成多个 Area 分组只在一个 area 内进行泛洪，不会扩散到外面。area 之间来进行通信需要先交给骨干 area，由骨干 area 交给其他 area 其他 area 再在内部交给目标子网对应的路由器

5.4 ISP 之间的路由选择

前面讲的 RIP OSPF 等都是一个自治区内的路由选择，也就是一个平面内的路由。

但对于全球这么大的网络，显然用这些方法是非常困难的：规模问题、管理问题、安全问题

自治系统 AS Autonomous System

因此采用层次性路由，分为两层：

1. 将网络划分成一个个的自治区域【规模小，使用之前的路由协议可以轻松解决】，自治区域内使用内部网关协议 intra-AS routing protocol，且没有要求使用哪种协议，可以是 RIP 也可以是 OSPF 或者是其他的私有的协议
2. 自治区之间的路由：一个自治区在这个层面上只表现为一个点或者若干个很少的点，使用外部网关协议 inter-As routing protocol

BGP

Border Gateway Protocol 边际网关协议

不是由组织制定的，而是大家约定俗成的，因此称为事实上的标准

内部网关协议可以任意，但边际网关协议一定的一样的，不然不同的 AS 无法通信

对于每个AS，每台路由器要么是一台网关路由器（gateway router），要么是一台内部路由器（internal router）。网关路由器位于AS边缘，直接连接到其他AS的路由器。内部路由器仅连接自己AS中的主机和路由器。

• eBGP exterior BGP 网关路由器从其他相邻的网关路由器得到他们收集来的自己所在的 AS 的可达信息

  如下的 1c 把自己子网的可达信息告诉 2a 后，2a 内都得到这个信息，那么 2c 就可以把这个信息进行 re-advertisement，将其转发给 3a【但注意加增加一跳信息，即3a 要达到 AS1 需要通过 AS2】，所以 3a 就可以知道 AS1 中的可达信息了，同时 2c 也会把自己 AS2 的可达信息告诉 3a

• iBGP interior BGP 网关路由器将上面得到的子网可达信息传遍 AS 内部的所有路由器。告诉内部路由器，到到某个子网通过我这个网关路由器就可以到

  但注意下面的虚线不一定是物理链路，而是 TCP 连接，通过 TCP 传递子网可达信息，那么 TCP 怎么路由呢？自然是通过内部网关协议即可

基于改进的 DV 算法，不仅仅包含距离（即多少跳）还包含路径，因此可以检查出其中的环路，避免无穷计算问题，收敛速度更快

每对路由器通过使用179端口的半永久TCP连接交换路由选择信息。

使用 TCP 协议交换 BGP 报文

基于策略的路由，不像内部网关协议，毫无保留的通告，在不同 AS 之间的通告会基于一定的策略，有多条路径可选择时，也会基于策略进行选择一条，不一定就以跳数作为标准，还有其他的考虑因素【内部网关协议注重性能，外部网关协议关注策略】

两个重要的属性是AS-PATH和NEXT-HOP。NEXT-HOP是AS-PATH起始的路由器接口的IP地址。

BGP 路由选择

1.热土豆路由选择（hot potato routing）

选择到开始该路由的多个NEXT-HOP路由器中具有最小开销的那条路径。

热土豆的思想：尽可能快地将分组送出其AS（最低开销），而不担心其AS外部到目的地的余下部分的开销。热土豆路由选择是自私的算法。

2.路由选择算法

实践中BGP使用一种比热土豆选择更为复杂的算法，进入BGP路由选择算法的输入是到某前缀的所有路由的集合，如果只有一条这样的路由就选择该路由，否则依次按照一些消除规则直到剩下一条路由。

因此去往其他 AS 内的可达信息是由内部网关协议【决定通过哪些 interface 放出数据可以到达网关】和外部网关协议【决定怎么到外部子网】一起决定的

5.5 SDN 控制平面

SDN 控制器：

• 网络控制应用界面层：控制器通过**“北向”接口**与网络控制应用程序交互。
• 网络范围状态管理层：网络的主机，链路，交换机和其他SDN控制设备的最新状态信息，以及各种受控设备的流表。
• 通信层：SDN控制器和受控网络设备之间的通信。现在被称为控制器的“南向”接口。OpenFlow就是一种提供这种功能的特定协议。

采用 TCP 交换报文

3 种类型：

• 控制器–>分组交换机
• 控制器<–分组交换机
• 控制器<–>分组交换机

两种控制器 Open Daylight 和 ONOS。

5.6 ICMP

Internet Control Message Protocol 因特网控制报文协议

差错报告

ICMP 最典型的用途是差错报告

例如，当运行一个HTTP会话时，会遇到一些诸如“目的网络不可达”之类的错误报文。这种报文就来源于ICMP。在某个位置，IP路由器不能找到一条通往HTTP请求中所指定的主机的路径，该路由器就会向主机生成并发出一个ICMP报文以指示该错误。

ICMP通常被认为是IP的一部分，但从体系结构上讲它位于IP之上。当一台主机收到一个指明上层协议为ICMP的IP数据报时（上层协议编码为1）,它分解出该数据报的内容给ICMP,就像分解岀一个数据报的内容给TCP或UDP 一样。

ICMP报文有一个类型字段和一个编码字段，并且包含引起该ICMP报文首次生成的 IP 数据报的首部和 ICMP的前8个字节（以便发送方能确定引发该差错的数据报）。

如下在返回的 11 0 ICMP 报文中包含了引起该 ICMP 报文的源报文的 IP 首部和 ICMP 内容的前 8 B

ping

ping程序发送一个ICMP类型8编码0的报文到指定主机。目的主机发回一个类型0编码0的ICMP回显回答

Traceroute

利用返回的 ICMP 报文来判断，通过发送 ping 报文来实现

逐个增加 TTL 发送报文，同时为每个报文设定计时器，当 TTL 减为 0，路由器发送类型 11 编码 0 的 TTL 过期差错报告（包含这个路由器的名字和 IP 地址），因此可以得到往返时延。

当到达目标主机时，由于目标主机和 ping 的目标地址相同，因此目标主机会返回类型 0 编码 0 的 ICMP 报文对 ping 进行响应，因此 tracert 就知道已经到达了，无需再发送

（标准的 Traceroute 程序实际上用相同的TTL发送3 个一组的分组，因此 Traceroute 输出对每个TTL提供了 3个结果。）

总结

发送报文，同时为每个报文设定计时器，当 TTL 减为 0，路由器发送类型 11 编码 0 的 TTL 过期差错报告（包含这个路由器的名字和 IP 地址），因此可以得到往返时延。

当到达目标主机时，由于目标主机和 ping 的目标地址相同，因此目标主机会返回类型 0 编码 0 的 ICMP 报文对 ping 进行响应，因此 tracert 就知道已经到达了，无需再发送

（标准的 Traceroute 程序实际上用相同的TTL发送3 个一组的分组，因此 Traceroute 输出对每个TTL提供了 3个结果。）

总结

[外链图片转存中…(img-bAikkGdY-1656229054428)]