计算机网络——自顶向下的方法第五章的学习

这一章讲了网络层的控制平面。

上一章中，有句话说的挺好：一个人总是要不断超越自我，否则还有什么乐趣可言？

介绍

这一章主要学习控制平面，会学习多种协议，诸如 RIP，OSPF和BGP协议，以及后面的ICMP和SNMP协议。

概述

在通用转发的操作中，路由器可以转发，修改，复制，重写一个分组。完成这些工作可能又两种方法：

每路由器控制：相当于分布式控制，路由器不知道全局的拓扑情况，通过互相告知的方法选择最合适的路由。RIP，OSPF，BGP协议都是使用的这种方式控制。
逻辑集中式控制：相当于集中控制，远程控制器知道全局的拓扑，可以给每一个路由器下发最合适的路由表。SDN就是通过逻辑集中式控制实现的。

路由选择算法

我们把拓扑结构抽象成数据结构中的图，边权表示路径长度或者说开销。

我们的目的自然是要使得数据包在传输的时候走过最短的路径（shortest path）。

一般来说，根据该算法是集中式还是分散式来划分：

集中式路由选择算法：主要是用链路状态（Link State，LS）算法，这里我们假设知道全局的拓扑结构，且清楚地知道每一条路由的开销。
分散式路由选择算法：主要是使用距离向量（Distance-Vector，DV）算法，属于是分布式的，也许更为天然地适合那些路由器直接交互的控制平面。

根据算法是静态还是动态的进行分类，可以分为：

静态路由算法：人工配置路由表，除非人为干预，否则不会改变路由表。
动态路由算法：会根据网络的情况合理地调整自己的路由表。

最后可以分为负载敏感或者负载迟钝的，是否敏感主要在于某条链路的开销是否能真实反映链路的真实拥塞水平。显然 RIP，OSPF，BGP都是负载迟钝的算法。

链路状态路由选择算法

这个算法也就是OSPF协议所使用的Dijkstra最短路径算法了。

作为ACMer对这个当然很熟了已经，这个算法运行在每一个路由器中，每个路由器以自己为源点运行这个 $O(n^2)$ 的算法，当然如果我们用一个堆维护当前点的最小值，那么可以以 $O(nlog_2n)$ 的复杂度得到所有的最短路。

Dijkstra单源最短路的思想就是：维护所有点与自己的距离，初始只有自己邻居的距离知道，其它点的距离都是无穷大，此时选择一个距离最小的点，把它加到一个集合中，再去寻找以这个点为起点的距离（加上它到源点的距离）最短的节点，同样也选择到源点距离最小的点加入其中，如此循环，直到得到每一个点的最短距离。

距离向量路由选择算法

距离向量（Distance-Vector，DV）算法是一种迭代的、异步的和分布式的算法。

说它是分布式的，是因为每个节点都要从一个或多个直接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居。
说它是迭代的，是因为此过程一直要持续到邻居之间无更多信息要交换为止。
说它是异步的，是因为它不要求所有节点相互之间步伐一致地操作。

它首先会直接维护自己到邻居的开销，同时也要记住自己到其它节点的总开销。一开始，它只知道自己到邻居的开销。

然后把自己所知道的信息全部发给邻居，邻居知道后，把自己相应的距离表更新。

距离向量算法：链路开销的改变与故障

需要知道一点的是：当链路状态发生改变，它们也要响应的作出转变。举个例子：

看a图，本来的状态为：

	x	y	z
x	0	4	5
y	4	0	1
z	5	1	0

当 xy 的距离变为 1 的时候，x 和 y 迅速感受到。

	x	y	z
x	0	1	5
y	1	0	1
z	5	1	0

然后y把消息告诉了 z，z知道了 x 到 y 的距离变成 1 之后，马上算，我到 x 的距离就是 2，算法进入静止状态。

只两轮就到了平衡状态，链路状态变优的好消息迅速得到了传播，称为好消息传得快。

我们再来看链路状态增加的情况，也就是上面的 b 图。

此时遇到了路由选择环路，过程是这样的，初始状态还是一样，只不过此时 xy 的开销骤然变大，

	x	y	z
x	0	4	5
y	4	0	1
z	5	1	0

我们来看此时 y 的视角。我要更新我到x的距离，我到 x 的距离应该就是 min(edge(y,z)+dis(x,z),edge(y,x)+dis(x,x))，把值都带进去，因为此时 y 只能清晰地认知它到 x 的距离变成了 60，它并不能知道此时 z 到 x 的距离也变高了，它只会认为是之前的 5，因此带入上式可得到：

dis(x,y)=min(edge(y,z)+dis(x,z),edge(y,x)+dis(x,x))=min(1+5,60+0)=6。

上面的情况一定是先发生的，因为它们俩的变化只有 x 和 y 会做出反应之后通告了 z 之后，z 才会作出反应。

z 此时作出反应：因为 dis(x,y) 发生了变化，我也得考虑一下，我到 z 的距离，就是：

dis(z,x)=min(edge(z,y)+dis(y,x),edge(z,x)+dis(x,x))=min(1+6,50+0)=7。

然后它发出通告，告诉了y，那么 y 还是用那个公式去算：

dis(x,y)=min(edge(y,z)+dis(x,z),edge(y,x)+dis(x,x))=min(1+7,60+0)=8。

可以发现，出现循环了！

而且此时我们遇到路由选择环路（route loop），而且此时正常分组会在它们之间不断跳跃，因为按照它们的算法，它们到 z 的最短距离都是发给对方。分组便会在这两个路由器之间来回发送，直到 TTL=0 或者其中一个路由器意识到它们错了修改自己的转发表为止。

那么就像刚刚的循环会持续多久呢？按书上的说法，会持续 44 次，因为要让 y 正确认识到 z 到 x 的最短距离应该是 50。而初始情况的 dis(z,x)=5，经过 44 次循环之后应当就变成 50 了。

如果xy和zx的链路开销变成 9999，甚至是 9999 呢，那就要循环接近9999次才能解决问题，可以看到x到y的距离增加的坏消息传的慢，这个问题有时候也被称为无穷计数问题。

距离向量算法：增加毒性逆转

刚才描述的特定循环的场景可以通过使用一种称为毒性逆转（poisoned reverse）的技术而加以避免。其思想较为简单：如果z通过 y 路由选择到目的地 x，则z将通告 y，它（即z）到 x 的距离是无穷大，也就是 z 将向 y 通告 dis(z,x)=inf。这样让 y 知道之后重新做那个式子的选择：

dis(x,y)=min(edge(y,z)+dis(x,z),edge(y,x)+dis(x,x))=min(1+inf,60+0)=60。

然后转发给 z ，z 马上可以决定：

dis(z,x)=min(edge(z,y)+dis(y,x),edge(z,x)+dis(x,x))=min(1+60,50+0)=50。

然后 z 转发给 x，x也能马上收敛得到预期值：

dis(x,y)=min(edge(y,z)+dis(x,z),edge(y,x)+dis(x,x))=min(1+50,60+0)=51

这样我只是撒了一个善意的小谎言，我能提前结束这 44 次不必要的循环，当然因为这个机制的存在，y 在认为走 z 再转发给 x 的距离比较短的同时，也会告诉 y，dis(y,x)=inf，此时算法就可以达到稳定状态了。

但是它也没有解决一般无穷计数问题，应该认识到，涉及多个节点而不是两个直接相连的节点环路不能用毒性逆转的技术检测到。

LS与DV路由选择算法比较

直接说结论吧：

报文复杂性：LS比较高，因为一次链路发生改变要通告全体成员，然后全体又因为这个报文要发给其它所有人自己对应的新的距离，复杂性为 $O(NE)$，而DV算法仅仅在每次迭代的时候通告相邻路由器即可。
收敛速度：LS比较快，因为LS基本是有全局视角一样的去算距离，而DV算法会在链路增大的时候产生无穷计数的问题。
健壮性：LS算法比较好，因为对于DV算法来说，一个恶意的通告会导致所有流量到该路由器，从而扩散到整个网络。

因特网自治系统内部的路由选择

因特网是一个具有 32 位地址的集合，现在已经有超过10亿台主机，让路由器记住所有的 IP 地址显然不太可能。因此需要降低因特网这种大型网络的复杂性。

可以把主机和路由器组织进一个自治系统（Autonomous System，AS），一个自治系统由其全局唯一的AS号（ASN）所标识。就像IP 地址那样，AS号由ICANN区域注册机构所分配。在一个自治系统内运行的路由选择算法叫作自治系统内部路由选择协议（intra-autonomous system routing protocol）。内部路由选择协议主要有路由信息协议（Routing Information Protocol，RIP）和开放最短路优先协议（Open Shortest Path First，OSPF）。

RIP协议

RIP 是一种分布式的基于距离向量的路由选择协议，是互联网的标准协议，其最大优点就是简单。

RIP 定义从一个路由器到另一个路由器的距离为 1，这个距离也可以叫跳数（hop count）。从一路由器到非直接连接的网络的距离定义为所经过的路由器数加1。“加1”是因为到达目的网络后就进行直接交付，而到直接连接的网络的距离已经定义为1。

每经过一个路由器，跳数就加1。RIP 认为好的路由就是它通过的路由器的数目少，即“距离短”。RIP 允许一条路径最多只能包含15 个路由器。因此“距离”等于 16 时即相当于不可达。可见 RIP 只适用于小型互联网。

RIP 不能自动选择最优路由，只会选择跳数最少的路由。

RIP 的特点：

仅和相邻路由器交换信息，不相邻的路由器不交换信息。
路由器交换的信息是当前本路由器所知道的全部信息，即自己现在的路由表。
按固定的时间间隔交换路由信息，例如，每隔30 秒。然后路由器根据收到的路由信息更新路由表。当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。

RIP 还具有距离向量算法的所有特点，诸如好消息传得快，坏消息传得慢等特点。RIP 协议使用运输层的用户数据报 UDP 进行传送（使用UDP 的端口520）

RIP报文格式

如下图所示：

由首部和路由部分组成。

RIP 的首部占 4 个字节，其中的命令字段指出报文的意义。例如，1 表示请求路由信息，2 表示对请求路由信息的响应或未被请求而发出的路由更新报文。必为0部分是为了对齐4个字节。

RIP2 报文中的路由部分由若干个路由信息组成。每个路由信息需要用20 个字节。

地址族标识符（又称为地址类别）字段用来标志所使用的地址协议。如采用IP 地址就令这个字段的值为 2。
路由标记填入自治系统号ASN（Autonomous System Number），这是考虑使RIP 有可能收到本自治系统以外的路由选择信息。
再后面指出某个网络地址、该网络的子网掩码、下一跳路由器地址以及到此网络的距离。

一个RIP 报文最多可包括 25 个路由，因而RIP 报文的最大长度是 4 + 20 × 25 = 504 字节。如超过，必须再用一个 RIP 报文来传送。

RIP2 还具有简单的鉴别功能。若使用鉴别功能，则将原来写入第一个路由信息（20 字节）的位置用作鉴别。这时应将地址族标识符置为全1（即0xFFFF），而路由标记写入鉴别类型，剩下的16 字节为鉴别数据。在鉴别数据之后才写入路由信息，但这时最多只能再放入 24 个路由信息。

OSPF协议

OSPF是一种链路状态协议，它使用洪泛链路状态信息和Dijkstra最低开销路径算法。OSPF报文直接使用 IP 承载，协议字段的值为 89。

OSPF 具有以下优点：

安全：可以鉴别路由器是否可信，保证数据的真实性。
多条相同开销的路径：当开销相同时，不会单一地选择一条路径。
单播与多播路由选择的综合支持：多播OSPF （MOSPF）提供对OSPF的简单扩展，以便提供多播路由选择。MOSPF使用现有的OSPF链路数据库，并为现有的OSPF链路状态广播机制增加了一种新型的链路状态通告。
支持层次化结构。

ISP之间的路由选择：BGP

AS之间还需要有通信协议，AS之间通信必须运行相同的AS间路由选择协议，称为边界网关协议（Broder Gateway Protocol, BGP）

BGP的作用

BGP其实就是用于连接 AS，确保自治系统之间的通信。BGP为每台路由器提供了一种完成以下任务的手段：

从邻居AS获得前缀的可达性信息。
确定到该前缀的“最好的”路由。

下面我们开始研究这两点。

通告BGP路由信息

一台路由器，要么是一台网关路由器（gateway router），要么是一台内部路由器（internal router）。

如图有三个 AS，连接其它AS的路由器就是网关路由器，而只连接自己AS路由器的路由器就是内部路由器。

每对路由器通过使用179端口的半永久 TCP连接交换路由选择信息。每条直接连接以及所有通过该连接发送的BGP报文，称为 BGP连接（BGP cormection），跨越两个AS的BGP连接称为外部 BGP （eBGP）连接，而在相同AS中的两台路由器之间的 BGP会话称为内部 BGP（iBGP）连接。就像下图展示的一样：

一台主机（x）想表明自己在 AS3 中可以直接发 AS3 x，当经过边界路由器的时候，它会带上自己的自治系统号，比如这个信息被转到了 2c 这里，2c 他就会表明通过跟我自治系统的连接可以找到 AS3 中的 x。它会给其它的路由器发送这样的信息：AS2 AS3 x，为了防止回传，我们规定，如果一台路由器在路径列表中看到包含了它自己的AS，它将拒绝该通告。当经过 AS1 的时候，AS1 收到 AS2 AS3 x，它就知道了，我应该先经过 AS2，再去找到 AS3 中的 x。

确定最好路由

当路由器通过BGP连接通告前缀时，它在前缀中包括一些BGP属性（BGP attribute）。用BGP术语来说，前缀及其属性称为路由（route）。两个较为重要的属性是AS-PATH和NEXT-HOP。AS-PATH属性包含了通告已经通过的AS的列表，

NEXT-HOP是AS-PATH起始的路由器接口的IP地址

比如路由器 2a 来说，最左侧的接口的IP地址就是 NEXT-HOP，对于AS-PATH=AS2 AS3 x 来说。

而路由器 3d 来说，最左侧的接口的IP地址就是 NEXT-HOP，对于 AS-PATH=AS3 x 来说。

热土豆路由选择

它不会查阅最好的路由，它只会尽可能快速地把数据包送出自己的 AS，比如对于 1b 到 3d 的转发，虽然通过 1d 的右边端口可以很快地到达，但是它仍会选择 1c 路由器的端口转发到 AS2 中。

因此我们把分组看成是烫手的土豆，每个 AS 都在尽最大可能送出自己的分组。因此它是自私的算法，因为它只关心自己的开销而不管其它的开销。

在做这个的时候也是想到了一点，在数据包传给 AS2的时候，那个路由器会不会认为AS1可以直接到达，并且AS1的下一跳最近而把数据包还给AS1的网关路由器，然后它们之间就循环了，因为对方路由器都是最近的下一跳并且可达，总之，纯粹的热土豆路由选择算法应用场景还是比较小的。

路由器选择算法

实际应用中，所有路由器会被管理员指定一个本地偏好。本地偏好：本地偏好是一种策略属性，完全由AS网络管理员设置。具有最高本地偏好值的路由被选择。然后再根据以下算法选择路由：

从余下的路由中（所有都具有相同的最高本地偏好值），将选择具有最短AS-PATH的路由。如果该规则是路由选择的唯一规则，则BGP将使用距离向量算法决定路径，其中距离测度使用AS跳的跳数而不是路由器跳的跳数（也就是经过多少个AS转发的）。
余下的路由就是拥有相同本地偏好且具有相同 AS-PATH 长度的路由，这个时候使用热土豆转发一个具有最近 NEXT HOP 的路由。
如果仍留下多条路由，该路由器使用BGP标识符来选择路由。

可以看到，这个算法不再自私，它会选择尽量少的 AS-PATH 长度。

IP任播

任播是指把数据包发送给一个 IP 集合中的任意一个主机。比较常见的应用就是镜像网站，因为地理位置缘故，为了保证较快的访问速度，在多个地理位置建立相同的网站，在访问的时候选择任意一个地理位置接近的网站。

CDN就是一个使用IP任播的应用，但是实际上 CDN 不使用 IP 任播，而是让原网站将DNS解析到CDN服务器，然后CDN提供商做内容分发。

实际中，DNS解析是使用IP任播的方式去解析的，IP任播会将数据包发送到地理位置最近的一台根DNS服务器。

路由选择策略

来参考一下这样的网络：

考虑这样的问题：

B网络给Y的流量是否会经过X，如果经过X，X必然不愿意，因此客户网络永远不会通告自己有到达其它网络的办法。

在考虑W到Y是否会经过B，因为W和Y都不是B的客户，浪费我的流量服务不属于我的客户我必然不愿意。商业运行的ISP们都遵从的一个经验法则是：任何穿越某ISP主干网的流量必须是其源或目的（或两者）位于该ISP的某个客户网络中；不然的话这些流量将会免费搭车通过该ISP的网络。

因特网的呈现

讲述了一个公司，怎么注册自己的门户网站和域名邮箱等等服务。

无非就是我先和ISP签订协议，分配IP和域名，并安排人到我的公司物理链接和配置。要向域名管理商拿到一个域名并且把自己的一台主机变为域名服务器并把IP地址告诉域名管理商。

我自己添加 www 子域作为 web 服务器，添加 mail 子域作为邮件服务器。

SDN控制平面

SDN的四个关键特征：

基于流的转发：像前面提到的，可以根据运输层，网络层，链路层首部的各个字段进行转发，丢弃，修改首部等操作。
数据平面与控制平面分离：数据平面由分组交换机组成，是相对简单但快速的设别，该设备在他们的流表中执行匹配+操作的功能，而控制平面由服务器以及决定管理交换机的流表软件组成。
网络控制功能：SDN控制平面由软件实现，网络控制应用程序通过调用SDN提供的北向API获取，监视，编程，控制下面的网络设备。
可编程的网络：决定使用什么样的算法去转发以及操作分组。

SDN控制器和网络控制应用程序

这一章感觉没有特别重要的东西。

OpenFlow协议

运行在6653端口之上。

ICMP：因特网控制报文协议

我们在连接失败的时候，通常会发送一个ICMP给到原TCP链接，以便于告诉主机发生了一些什么事情导致了怎么怎么样的情况，比如我们 nc 常见的，Destination net unreachable，这些信息就是通过 ICMP 告诉套接字的，当套接字收到了ICMP报文，便会根据这个去查找对应的 info 和采取对应的操作。

ICMP通常被认为是IP的一部分，但从体系结构上讲它位于IP之上，因为ICMP报文是承载在IP分组中的（它属于网络层协议）。这就是说，ICMP报文是作为IP有效载荷承载的。当一台主机收到一个指明上层协议为 ICMP 的IP数据报时（上层协议编码为1）。

ICMP报文有一个类型字段和一个编码字段，对应的信息如下表所示。

ICMP类型	编码	描述
0	0	回显回答（对 ping 的回答）
3	0	目的网络不可达
3	1	目的主机不可达
3	2	目的协议不可达
3	3	目的端口不可达
3	6	目的网络未知
3	7	目的主机未知
4	0	源抑制（拥塞控制）
8	0	回显请求
9	0	路由器通告
10	0	路由器发现
11	0	TTL过期
12	0	IP 首部损坏

另一个有趣的ICMP报文是源抑制报文。这种报文在实践中很少使用。其最初目的是执行拥塞控制，即使得拥塞的路由器向一台主机发送一个ICMP源抑制报文，以强制该主机减小其发送速率。

随便抓一个 IP 分组过来。

里面有八位的 type 字段和八位的 code 字段，后面还有一系列数据。

traceroute 程序的原理就是使用 ICMP 报文去获取链路上的路由信息的。为了判断源和目的地之间所有路由器的名字和地址，源主机中的Traceroute向目的地主机发送一系列普通的IP数据报。这些数据报的每个携带了一个具有不可达UDP端口号的UDP报文段。第一个数据报的TTL为1，第二个的TTL为2，第三个的TTL为3，依次类推。当第 n 个数据报到达第 n 台路由器时，第 n 台路由器观察到这个数据报的TTL正好过期。

根据IP协议规则，路由器丢弃该数据报并发送一个ICMP告警报文给源主机（类型11编码0）。该告警报文包含了路由器的名字和它的IP地址。当该ICMP报文返回源主机时，源主机从定时器得到往返时延，从ICMP报文中得到第n台路由器的名字与IP地址。这便是traceroute的工作原理了。

一般这个不可达的端口为 33434。

小结

我们学习了构建控制平面有两大类方法：传统的每路由器控制（其中在每台路由器中运行算法，并且路由器中的路由选择组件与其他路由器中的路由选择组件通信）和软件定义网络（SDN）控制（其中一个逻辑上集中的控制器计算并向每台路由器分发转发表为它们所用）。我们在5.2节中学习了两种基本的路由选择算法，即链路状态和距离矢量，用于计算图中的最小开销路径；这些算法在每路由器控制和SDN控制中都有应用。这些算法是两种广泛部署的因特网路由选择协议OSPF和BGP的基础，我们在5. 3节和5. 4节中讨论了这两种协议。我们在5. 5节中讨论了网络层控制平面的SDN方法，研究了SDN网络控制应用程序、SDN控制器，以及控制器和SDN控制设备之间通信所使用的0penFlow 协议。在5.6节中，我们包括了管理IP网络的某些技术细节：ICMP （互联网控制报文协议）。

网络层到这里就结束了，下面就只剩下链路层了，这本书也快结束了。