计算机网络

概述

协议

网络协议 (Network Protocol)，简称为协议，是为进行网络中的数据交换而建立的规则、标准或约定。

协议的三个要素

语法：数据与控制信息的结构或格式。

就是这一段内容要符合一定的规则和格式。例如，括号要成对，结束要使用分号等。

语义：需要发出何种控制信息，完成何种动作以及做出何种响应。

就是这一段内容要代表某种意义。例如数字减去数字是有意义的，数字减去文本一般来说就没有意义。

同步：事件实现顺序的详细说明。

就是先干啥，后干啥。例如，可以先加上某个数值，然后再减去某个数值。

体系结构

四层、五层、七层结构

各层的协议簇

七层结构的协议簇见下图：

性能指标

速率：数据传输速率。速率往往是指额定速率或标称速率，非实际运行速率。
单位： $bit/s$

注：响应两个单位的倍数是 $10^3$ ，而不是 $2^10$

带宽：

（1）单位时间内网络中某信道通过的最高数据率。单位 $bit/s$
（2）信道的频带宽度。单位： $Hz$

吞吐量：单位时间内通过某个网络的实际数据量。
单位 $bit/s$
最大吞吐率（一个 RTT 时间内发送所有窗口数据）
线路效率（吞吐率/网络速率）

物理层

信道

（重要）信道的传输速率

奈氏准则

信道的理想传输速率。

码元传输速率：

B=2W

其中：

$B$ ：码元传输速率（波特率）
$W$ ：带宽（赫兹）

奈氏准则：

C=B\log_2 N

其中：

$C$ 的单位为 $bit/s$
$B$ 是上面的码元传输速率
$N$ 是码元离散对(电平)的个数

信噪比

信号的平均功率和噪声的平均功率之比，常记为 $S/N$ ，并使用分贝作为度量单位：

\text{信噪比}=10 \log_{10} \frac{S}{N}

其中：

信噪比的单位为 $dB$
$S$ :信号的平均功率
$N$ :噪声的平均功率

香农公式

有噪声情况下的极限信息传输速率

C=W \log_2 (1+\frac{S}{N})

$C$ 的单位为 $bit/s$
$W$ 为带宽
$S/N$ 为信噪比

奈氏准则计算

假定某信道受奈氏准则限制的最高码元速率为 $20000$ 码元/秒。如果采用振幅调制，把码元的振幅划分为 16 个不同等级来传送，那么可以获得多高的数据率( $bit/s$ )?

解

$B=20000,N=16$

C=B \times \log_2 16 = 20000bit/s \times 4 = 80000 bit/s

数据链路层

三个基本问题

封装成帧：就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。
透明传输：由于帧的首尾使用了特殊的控制字符，因此需要对数据部分出现的控制字符进行转义。这样就会给人一种“透明”的感觉，也就是无论发送什么数据，这个层像玻璃一样，看起来好像不存在。
差错控制：采用差错检测技术，及时丢弃带有差错数据的帧。但是不能修复错误，也不能保证传输的可靠性。

（重要）两个协议

PPP:使用点对点信道进行通信
以太网:使用广播信道进行通信，支持一对多。

（重要）CRC 差错检测

生成多项式

看每一项的幂 $i$ ，那么对应除数 %P% 的第 $i$ 位为 1。

生成多项式

$P(X)=X^4+X+1$ 对应的除数 $P=10011$

生成检验序列

计算帧检验序列 $R$ ：设除数 $P$ 的位数为 $i$ ，那么：

先将数据 $Q$ 在后面加 $i-1$ 个 0，得到 $Q'$
再将 $Q'$ 除以 $P$ ，得到余数 $R$

得到的余数 $R$ 即为检验序列。

验证检验序列

要验证数据是否出现问题，只需要：

将数据 $Q$ 后面接上检验序列 $R$ ，得到 $Q'$
$Q'$ 除以除数 $P$
若得到的余数不为 0，则传输出现错误

CRC的计算例题

设数据 $Q=101001$ ，除数 $P=1101$ 。

那么， $Q'=101001000$ ，除以 $P$ 后得到检验序列 $R=001$

如果数据传输时，某一个 $1$ 变为了 $0$ 。那么 $Q$ 和 $P$ 连接后得到的数据，除以 P 后余数就不为 0 了。

（重要）以太网的拓展

不同设备拓展以太网的效果:

设备	层级	隔离碰撞(冲突)域	隔离广播域	特点
集线器/转发器	物理层	×	×	扩大了网络范围，但碰撞域增大了，吞吐量未提高。
网桥/交换机	数据链路层	√	×	用户独享带宽，增加了总容量
路由器	网络层	√	√
网关	运输层及以上	√	√

以太网的拓展例题1
以太网的拓展例题2

有 10 个站连接到以太网上。试计算以下三种情况下每一个站所能得到的带宽。

10 个站都连接到一个 10 Mbit/s 以太网集线器;
10 个站都连接到一个 100 Mbit/s 以太网集线器;
10 个站都连接到一个 10 Mbit/s 以太网交换机。

解

共享 10MBps
共享 100Mbps
独占 10Mbps

在下图中，某学院的以太网交换机有三个接口分别和学院三个系的以太网相连，另外三个接口分别和电子邮件服务器、万维网服务器以及一个连接互联网的路由器相连。图中的 A,B 和 C 都是 100 Mbit/s 以太网交换机。

假定所有的链路的速率都是 100 Mbit/s，并且图中的 9 台主机中的任何一个都可以和任何一个服务器或主机通信。试计算这 9 台主机和两个服务器产生的总的吞吐量的最大值。
假定在图中的所有链路的速率仍然为 100 Mbit/s，但三个系的以太网交换机都换成为 100 Mbit/s 的集线器。试计算这 9 台主机和两个服务器产生的总的吞吐量的最大值。

解

带宽= $11 \times 100 Mbit/s$ = $1100 Mbit/s$
带宽= $5 \times 100 Mbit/s$ = $500 Mbit/s$

（重要）信道冲突检测和解决

CSMA/CD 协议

概念：载波监听多点接入 / 碰撞检测

多点接入:表示许多计算机以多点接入的方式连接在一根总线上。
载波监听:是指每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞。
碰撞检测：计算机边发送数据边检测信道上的信号电压大小。

核心原理：

每一个正在发送数据的站，一旦发现总线上出现了碰撞，就要立即停止发送，免得继续浪费网络资源。
发生碰撞后，等待一段随机时间后再发送。

碰撞检测与争用期

最先发送数据帧的站，发送数据帧后，在 $(\tau,2 \tau )$ 内，检测到碰撞。

其次发送数据帧的站，在 $(0,\tau)$ 内检测到碰撞。

$\tau$ 是指端到端的传播时延

这个 $2 \tau$ 称为争用期，或者碰撞窗口。如果在争用期内没有检测到碰撞，那么就可以肯定这次发送不会出现碰撞。

争用期可以确定帧的最小长度： $2 \tau \times \text {传输速率}$ 。

10 Mbit/s 以太网取 $51.2 \mu s$ 为争用期的长度。对于 10 Mbit/s 以太网，在争用期内可发送 512 bit，即 64 字节。所以以太网规定了最短有效帧长为 64 字节，凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。

争用期与最小帧长

假定 1km 长的 CSMA/CD 网络的数据率为 1Gbit/s。设信号在网络上的传输速率为 200000km/s.求能够使用此协议的最短帧长。

解

\tau = \frac{1 km}{200000 km/s}=5 \mu s

\text{最短帧长}= 2 \tau \times \text{传输速率}=10^4

即最短帧长为 10000 位。

随机时间重传

采用了 二进制指数退避算法。

设 $k=\min \{ \text{重传次数},10 \}$ 。从集合 $\{0,1,...,2^k-1\}$ 中随机取出一个数，记为 $r$ 。

那么， $2\tau r$ 即为重传时间。

当重传达 16 次仍不能成功时即丢弃该帧，并向高层报告。

强化碰撞

发送数据的站检测到碰撞以后，立即停止发送数据，并发送 $32$ 或 $48$ 比特的人为干扰信号。

CSMA/CD 协议的基本流程

准备发送：发送之前，必须先检测信道。
- 若信道不空闲，则一直检测。待信道空闲后，等待 $9.6 \mu s$ 后发送。
- 若信道空闲，则直接发送。
检查碰撞：
- 在争用期内，如果没有检测到碰撞，那么就代表这个帧发送成功。
- 如果检测到碰撞，则立即停止发送，再发送一定长度的干扰信号，然后随机等待一段时间后重新发送。

CSMA/CD综合题

有两台主机 A 和 B 接在 $800m$ 长的电缆线的两端，并在 t=0 时各自向对方发送一个帧，长度为 $1500bit$ （包括首部和前同步码）。假定在 A 和 B 之间有 4 个转发器，在转发帧时会产生 20 比特的时延。设传输速率为 $100 Mbit/s$ ，而 CSMA/CD 的退避时间是随机数 r 倍的争用期，争用期为 $512bit$ ，在发生第一次碰撞后，在退避时 A 选择 $r=0$ 而 B 选择 $r=1$ 。忽略发生碰撞后的人为干扰信号和帧间最小间隔。

（1）设信号的传播速率是 $2×10^8$ m/s。试计算从 A 到 B（包括 4 个转发器）的传播时延。

（2）在什么时间（以秒为单位）B 完全收到了 A 发送的帧？

（3）现在假定只有 A 发送帧，帧长仍为 1500bit，但 4 个转发器都用交换机来代替。交换机在进行存储转发时还要产生额外的 20bit 的处理时延。在什么时间 B 完全收到了 A 发送的帧？

解

\tau = \frac{800 m}{2 \times 10^8 m/s}+ \frac{4 \times 20}{100 \times 10^6}=4.8 \mu s

\tau + \tau + \frac{1500}{100 \times 10^6} + 4.8 = 15 \mu s

15 \times 5 + 4.8 = 79.8 \mu s

解析

包含信道上的传播时延和四个转发器的发送时延。
时间情况：
- $\tau$ ：A、B 检测到碰撞
- $2\tau$ : B 传输完所有已传输的数据，由于 A 的等待时间为 0，立即重传。

所以总时间为： $2 \tau+\text{发送时延}+\text{传播时延}$

将转发器改成交换机后，数据会进行存储转发，因此，发送时延 $15 \times 5$
由于第一问算出来的时延已经包含了四个交换机的处理时延，因此总时间等于 $15 \times 5 + 4.8$

星型以太网 100BASE-T

含义：

100：传输速率为 $100 Mbps$
BASE：连接信号是基带信号
T：双绞线

特点：

可在全双工方式下工作而无冲突发生。在全双工方式下工作时，不使用 CSMA/CD 协议。
MAC 帧格式仍然是 802.3 标准规定的。
保持最短帧长不变，但将一个网段的最大电缆长度减小到 100 m。
帧间时间间隔从原来的 9.6 $\mu s$ 改为现在的 0.96 $\mu s$

网络层

IP 地址与子网划分

IP 地址的分类

类别	网络号	主机号	网络号开头
A	8 位	24 位	0
B	16 位	16 位	10
C	24 位	8 位	110

区分 A/B/C 类地址：看网络号的开头部分。

子网划分

从主机号借用若干个位作为子网号 subnet-id，而主机号 host-id 也就相应减少了若干个位。

划分子网纯属一个单位内部的事情，对外部网络透明，对外仍然表现为没有划分子网的一个网络。

划分子网后:

主机号全为 0 的 IP 地址通常表示这个网络
主机号全为 1 的 IP 地址通常表示广播地址

这个两个特殊地址通常不能分配给主机使用。所以子网个数 $=2^\text{主机号位数}-2$ 。

子网划分

试找出可产生以下数目的 A 类子网的子网掩码(采用连续掩码):(1)2; (2)6; (3) 30;(4)62:(5) 122;(6) 250。

解

（1）255.192.0.0
（2）255.224.0.0
（3）255.248.0.0
（4）255.252.0.0
（5）255.254.0.0
（6）255.255.0.0

分析

A 类地址占用 8 位，子网掩码前 8 位均为 1.

（1）2 个子网，需要 2 位子网号

（2）6 个子网，需要 3 位子网号

（3）30 个子网，需要 5 位子网号

（4）62 个子网，需要 6 位子网号

（5）122 个子网，需要 7 位子网号

（6）250 个子网，需要 8 位子网号

子网掩码

子网掩码和 IP 地址相与，可以得到主机号和子网号。

ARP 协议

概念

ARP：地址解析协议，IP 地址到 MAC 地址的映射。

工作原理

每一个主机都设有一个 ARP 高速缓存，里面有所在的局域网上的各主机和路由器的 IP 地址到硬件地址的映射表。
当主机 A 欲向本局域网上的某个主机 B 发送 IP 数据报时，就先在其 ARP 高速缓存中查看有无主机 B 的 IP 地址。如有，就可查出其对应的硬件地址，再将此硬件地址写入 MAC 帧，然后通过局域网将该 MAC 帧发往此硬件地址。
如没有，ARP 进程在本局域网上 广播发送一个 ARP 请求分组。收到 ARP 响应分组后，将得到的 IP 地址到硬件地址的映射写入 ARP 高速缓存。
路由器不会转发 ARP 分组。如果对应 MAC 不在局域网中，则将对应路由器的 MAC 写入缓存。当发送分组时，则交给路由器，然后再由路由器进行转发。

不需要发送 ARP 请求分组的一些情况：
- 主机 A 和主机 B 使用点对点链路时
- 主机 A 进行广播时

一些典型的情况

发送方	接收方	操作
主机	局域网的主机	直接使用 ARP 找到硬件地址
主机	另一个网络上的主机	使用 ARP 找到本网络中的路由器地址。请求分组通过路由器进行转发。
路由器	局域网的主机	直接使用 ARP 找到硬件地址
路由器	另外一个网络的主机	使用 ARP 找到本网络中的路由器地址。请求分组通过路由器进行转发。

无分类编址 CIDR

CIDR 消除了传统的 A 类、B 类和 C 类地址以及划分子网的概念，因而可以更加有效地分配 IPv4 的地址空间。

CIDR 使用/记法，表示网络前缀占用的位数：220.78.168.0/24。还有一种简写记法，例如 10.0.0.0/10 可简写为 10/10，也就是把点分十进制中低位连续的 0 省略。
CIDR 把网络前缀都相同的连续的 IP 地址组成“CIDR 地址块”。一个 CIDR 地址块可以表示很多地址，这种地址的聚合常称为 路由聚合，它使得路由表中的一个项目可以表示很多个（例如上千个）原来传统分类地址的路由。
前缀长度不超过 23 位的 CIDR 地址块都包含了多个 C 类地址。这些 C 类地址合起来就构成了超网。
最长前缀匹配原则:出现多个匹配结果时，选择最长的匹配前缀

路由聚合
路由聚合

有如下的 4 个/24 地址块，试进行最大可能的聚合。

212.56.132.0/24
212.56.133.0/24
212.56.134.0/24
212.56.135.0/24

解

共同前缀是 22 位，即:11010100 00111000 100001。聚合的 CIDR 地址块是:212.56.132.0/22。

已知地址块中的一个地址是 140.120.84.24/20。试求这个地址块中的最小地址和最大地址。地址掩码是什么?地址块中共有多少个地址?相当于多少个 C 类地址?

解

最小地址是 140.120.80.0/20。
最大地址是 140.120.85.255/20。
地址数是 4096。
相当于 16 个 C 类地址。

注意

最后一问是算地址块中 C 类地址网络号的个数。

IPv4 协议的数据报格式

结构

IP 数据报由首部和数据两部分组成
首部的前一部分是固定长度，共 $20$ 字节，是所有 IP 数据报必须具有的。
后一部分为固定长度，大小在 $0-40$ 字节不等。
IP 数据报的最大长度为 $65535$ 字节。

首部的内容

内容	长度	说明
版本	4 位	固定值 4
首部长度	4 位	最大值 15，即可以表示 $15 \times 4 = 60$ 个字节
区分服务	8 位	用来获得更好的服务
总长度	16 位	IP 数据报最长为 65535 字节
标识	16 位	它是一个计数器，用来产生 IP 数据报的标识
标志	3 位，目前前 2 位有意义	最低位是 MF: $1$ 为还有分片， $0$ 为没有分片中间的一位是 DF:表示是否允许分片， $0$ 为允许
片偏移	13 位	较长的分组在分片后某片的数据部分数据在原分组中的相对位置。片偏移以 8 个字节为偏移单位，其值为$ \text {相对位置} / 8$。
TTL,生存时间	8 位	指示数据报在网络中可通过的路由器数的最大值。若减小到 0，则丢弃该数据报，不再转发。
协议	8 位	指出此数据报携带的数据使用何种协议，以便目的主机的 IP 层将数据部分上交给那个处理过程
首部校验和	16 位	只检验数据报的首部，不检验数据部分。注意这里使用二进制反转求和算法。
源地址	32 位
目的地址	32 位

一数据报的总长度为 3820 字节，其数据部分的长度为 3800 字节（使用固定首部），需要分片为长度不超过 1420 字节的数据报片。

因固定首部长度为 20 字节，因此每个数据报片的数据部分长度不能超过 1400 字节。

于是分为 3 个数据报片，其数据部分的长度分别为 1400、1400 和 1000 字节。

一个 3200 位长的 TCP 报文传到 IP 层，加上 160 位的首部后成为数据报。下面的互联网由两个局域网通过路由器连接起来，但第二个局域网所能传送的最长数据帧中的数据部分只有 1200 位，因此数据报在路由器必须进行分片。试问第二个局域网向其上层要传送多少比特的数据（这里的“数据”当然指的是局域网看见的数据）?

解

注意，“帧” 是数据链路层的传输单位

IP 数据报中，数据部分最长为 $1200-160=1040$ 位

由于片偏移需要是 $64bit$ 的整数倍，因此，每片长度不超过 $1024$ 位。

一共需要 $\lceil 3200/1024\rceil =4$ 个数据片。总共传输 $3200+4 \times 160 = 3840$ 比特的数据。

首部校验

采用 16 位二进制反码求和算法。每个字的字长为 16 位。

发送端：首部的各个字反码算术运算求和，得到 校验码。
接收端：首部各个字和校验码反码算术运算求和，若结果不为 0，则丢弃该帧。

路由表与转发分组

路由表

最重要的部分：目的主机所在网络、下一跳(路由器)的地址

路由表与网络拓扑图

已知路由器 R1 的路由表如下，试画出各网络和必要的路由器的连接拓扑，标注出必要的 IP 地址和接口。对不能确定的情况应当指明。

解

注意

路由器中，不同的端口对应不同的 IP 地址，应当标在连接处。
未知情况使用虚线标示

特定主机路由

为特定的目的主机指明一个路由。

默认路由

只要找不到其他的数据报所在的网络号，就将分组转发给默认路由。

分组转发算法

根据这个主机的目的 IP 地址 $D$
如果这个主机和路由器在同一网络，那么就直接交付到指定的接口。
如果这个主机指定了特定主机路由 $D$ ，那么就把数据报转发给路由表指出的下一跳路由。
将 IP 地址与每个行的子网掩码相与，若得到的网络号和相与结果相同，则转发给对应的下一跳地址。
如果有默认路由，则转发给默认路由。
否则，报告转发错误。

路由表的计算

设某路由器建立了如下路由表：

现共收到 5 个分组，其目的地址分别为:

128.96.39.10
128.96.40.12
128.96.40.151
192.4.153.17
192.4.153.90

试分别计算其下一跳。

解

IP	子网掩码	网络号	下一跳
128.96.39.10	255.255.255.128	128.96.39.0	m0
128.96.40.12	255.255.255.128	128.96.40.0	R2
128.96.39.151	255.255.255.128	128.96.40.128
128.96.39.151	255.255.255.192	128.96.40.128	R4
192.4.153.17	255.255.255.128	192.4.153.0
192.4.153.17	255.255.255.192	192.4.153.0	R3
192.4.153.90	255.255.255.128	192.4.153.0
192.4.153.90	255.255.255.192	192.4.153.64	R4

路由表的建立和路由选择

两类路由选择协议

内部网关协议 IGP (Interior Gateway Protocol)：在一个自治系统内部使用的路由选择协议。目前这类路由选择协议使用得最多，如 RIP 和 OSPF 协议。
外部网关协议 EGP (External Gateway Protocol) ：若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。

自治系统 AS：在单一的技术管理下的一组路由器，而这些路由器使用一种 AS 内部的路由选择协议和共同的度量以确定分组在该 AS 内的路由，同时还使用一种 AS 之间的路由选择协议用以确定分组在 AS 之间的路由。

RIP 内部网关协议

概念

RIP 是一种分布式的、基于距离向量的路由选择协议。

这里的距离是拓扑图中的跳数。
直达时，距离为 1；非直达时，最短路径经过的节点数为距离。
“距离” 的值为 16(最大值)时，表示不可达。

特点

仅和相邻路由器交换信息。
交换的信息是当前本路由器所知道的全部信息，即自己的路由表。
按固定的时间间隔交换路由信息，例如，每隔 30 秒。当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。
好消息传播得快，坏消息传播得慢。

路由表的建立

路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为 1）。它的路由表是空的。

以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。

路由表的更新

按固定的时间间隔，如 30s。

网络拓扑结构发生变化时，与之相连的路由器会立即更新，但与这个路由器相邻的路由器很可能需要一段时间才能更新。

缺点

RIP 限制了网络的规模，它能使用的最大距离为 15。
路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。
当网络出现故障时，要经过比较长的时间 (例如数分钟) 才能将此信息传送到所有的路由器。(坏消息传播的更慢)

距离向量算法

修改路由器 $X$ 传来的 RIP 报文：
- 下一跳地址改为 $X$
- 所有的距离增加 1
原路由没有对应目的网络，添加记录
新路由没有对应目的网络，不变
目的网络相同，下一跳相同，直接替换
目的网络相同，下一跳不同，选择距离最小的。如果距离不变则不动。
若 3 分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达路由器，即将距离置为 16。

规则：先看目的网络，再看下一跳。

路由表更新1
网络故障时的路由表更新

假定网络中的路由器 B 的路由表有如下左表的项目。现在 B 收到从 C 发来的路由信息（右表），
试求出路由器 B 更新后的路由表（详细说明每一个步骤)。

目的网络	距离	下一跳路由器
$N_1$	7	A
$N_2$	2	C
$N_6$	8	F
$N_8$	4	E
$N_9$	4	F

目的网络	距离
$N_2$	4
$N_3$	8
$N_6$	4
$N_8$	3
$N_9$	5

解

对传入的路由信息，距离加 1：

目的网络	距离
$N_2$	5
$N_3$	9
$N_6$	5
$N_8$	4
$N_9$	6

目的网络	距离	下一跳	解释
$N_1$	7	A	未更新
$N_2$	5	C	目标网络相同，下一跳相同，更新距离
$N_3$	9	C	没有目的网络，则添加
$N_6$	5	F	目标网络相同，下一跳不同，选择距离最短的路由信息
$N_8$	4	E	目标网络相同，下一跳相同，距离不变
$N_9$	4	F	目标网络相同，下一跳不同，选择距离最短的路由信息

某网络结构如下图所示，如果 Router3 与网络 4 之间的线路突然中断，按照 RIP 协议的实现方法，路由表的更新时间间隔为 30s。分别给出中断 30s 后、500s 后 Router2 的路由信息表 1 和路由信息表 2。

注:

若到达目的网络不需转发或目的网络不可达，用“–”来表示“下一站地址”;
当目的网络不可达时，“跳数”为 16。
设直连的跳数为 1。

解

路由信息表 1：

目的网络	下一跳地址	跳数
10.0.0.0	20.0.0.1	2
20.0.0.0	–	1
30.0.0.0	–	1
40.0.0.0	30.0.0.2	4

路由信息表 2：

目的网络	下一跳地址	跳数
10.0.0.0	20.0.0.1	2
20.0.0.0	—	1
30.0.0.0	–	1
40.0.0.0	—	16

分析

T=0 时，网络 4 故障了，与网络 4 相连的路由器 3 立即修改自己的路由表： $(40.0.0.0,-,16)$ 。但是这个更新信息可能需要一段时间(30s)才能将这个更新转发给其他的路由器。但这时候路由器 2 已经发送了 $(40.0.0.0,30.0.0.2,2)$ ,那么很短的一段时间内，路由器 3 会误以为网络 4 需要通过网络 2 才能到。根据 RIP 规则，此时路由器 3 收到报文后，将其改为： $(40.0.0.0,30.0.0.1,3)$ 。

T=30 时，路由器 3 更新数据，向路由器 2 发送报文 $(40.0.0.0,30.0.0.1,3)$ ，同样的，路由器 2 更新自己，将对应数据改为 $(40.0.0.0,30.0.0.2,4)$ 。

如此循环下去…，每相互发送一次报文，路由器 2 中对应的数据增加 2。

很明显， $500s > 16 \times 30$ ，此时数据已经增加到 16 了， $40.0.0.0$ 已经算是不可达的。

OSPF 内部网关协议

特点

开放表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。
最短路径优先 是因为使用了 Dijkstra 提出的最短路径算法 SPF
采用分布式的链路状态协议 (link state protocol)。
OSPF 对于不同类型的业务可计算出不同的路由。
多路径间的负载平衡
分组鉴别
支持变长子网划分和 CIDR

核心原理

向本自治系统中所有路由器发送信息，这里使用的方法是洪泛法。
发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。
只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。

几个路由协议的比较

类型	RIP	OSPF	BGP
基于协议	UDP	IP	TCP
类型	内部	内部	外部

从服务/功能的角度来看，最终目的都是为了生成路由条目并服务于路由器，使得路由器根据路由表进行转发数据，从这个点来看，路由协议都可以归类为网络层；但是从数据包封装的角度来看，它们 RIP 和 BGP 是属于应用层协议,OSPF 属于传输层协议。

NAT 技术

解决了专用地址的主机如何与互联网上的主机通信的问题，同时不用分配更多的 IP 地址，缓解 IP 地址枯竭的问题。

运输层

TCP 的拥塞控制

慢开始 (slow-start)
拥塞避免 (congestion avoidance)
快重传 (fast retransmit)
快恢复 (fast recovery)

慢开始算法

简介

功能：用来确定网络的负载能力。
核心思路：由小到大逐渐增大拥塞窗口数值。
初始拥塞窗口(cwnd):设置为不超过 2 至 4 个 SMSS 的数值。
慢开始门限 (ssthresh)：防止拥塞窗口 cwnd 增长过大引起网络拥塞。

设计

拥塞窗口控制：在每收到一个对新的报文段的确认后，可以把拥塞窗口增加最多一个 SMSS 的数值。其中 N 是原先未被确认的、但现在被刚收到的确认报文段所确认的字节数。
传输轮次：使用慢开始算法后，每经过一个传输轮次 (transmission round)，拥塞窗口 cwnd 就加倍。一个传输轮次所经历的时间其实就是往返时间 RTT。

慢开始到拥塞避免的过渡
- 当拥塞窗口 cwnd < 慢开始门限 ssthresh 时，使用慢开始算法。
- 当拥塞窗口 cwnd > 慢开始门限 ssthresh 时，停止使用慢开始算法而改用拥塞避免算法。
- 当拥塞窗口 cwnd = 慢开始门限 ssthresh 时，既可使用慢开始算法，也可使用拥塞避免算法。

拥塞避免算法

思路：让拥塞窗口 cwnd 缓慢地增大，即每经过一个往返时间 RTT 就把发送方的拥塞窗口 cwnd 加 1，使拥塞窗口 cwnd 按线性规律缓慢增长。
网络拥塞的判断：若重传定时器超时，则判断网络出现拥塞
网络拥塞的处理：
- 重置慢开始门限为拥塞窗口的一半 $max(cwnd/2，2)$
- 重置拥塞窗口 cwnd 为 1
- 执行慢开始算法

快重传算法

前提：算法首先要求接收方不要等待自己发送数据时才进行捎带确认，而是要立即发送确认，即使收到了失序的报文段也要立即发出对已收到的报文段的重复确认。

思想：发送方只要一连收到三个重复确认，就知道接收方确实没有收到报文段，因而应当立即进行重传（即“快重传”），这样就不会出现超时，发送方也不就会误认为出现了网络拥塞。
这个算法不是取消重传定时器，而是在某些情况下可更早地重传丢失的报文段。

快恢复算法

条件：当发送端收到连续三个重复的确认时，发送方现在认为网络很可能没有发生拥塞
操作：
- 慢开始门限 ssthresh = 当前拥塞窗口 cwnd / 2 ；
- 新拥塞窗口 cwnd = 慢开始门限 ssthresh ；
- 开始执行拥塞避免算法，使拥塞窗口缓慢地线性增大。

整体流程

拥塞控制的举例

起始：慢开始门限的初始值为 $16$ ，初始拥塞窗口为 $1$
图中 1 处：拥塞窗口达到慢开始门限 ssthresh，改为拥塞避免
图中 2 处：网络出现超时，发生网络拥塞。此时调整慢开始门限为 $12$ ，拥塞窗口为 $1$ ，改为慢开始算法。
图中 4 处：发送方一连收到 3 个对同一个报文段的重复确认（图中记为 3-ACK）。发送方改为执行快重传和快恢复算法。
图中 5 处：发送方知道现在只是丢失了个别的报文段。于是不启动慢开始，而是执行快恢复算法。此时条件慢开始门限为 $8$ ,发送窗口为 $8$ ，并执行拥塞避免算法。

TCP 连接建立与释放

建立：三报文握手

A 的 TCP 向 B 发出连接请求报文段，其首部中的同步位 $SYN = 1$ ，并选择序号 $seq = x$ ，表明传送数据时的第一个数据字节的序号是 x。
B 的 TCP 收到连接请求报文段后，如同意，则发回确认。B 在确认报文段中应使 $SYN = 1$ ，使 $ACK = 1$ ，其确认号 $ack = x + 1$ ，自己选择的序号 $seq = y$ 。
A 收到此报文段后向 B 给出确认，其 $ACK = 1$ ，确认号 $ack = y + 1$ 。A 的 TCP 通知上层应用进程，连接已经建立。B 的 TCP 收到主机 A 的确认后，也通知其上层应用进程：TCP 连接已经建立。

SYN 同步位表示这个报文是建立连接的一个请求。
$SYN=1$ 但 $ACK=0$ ，表示这是一个连接请求。
$SYN=1$ 且 $ACK=1$ ，表示同意建立连接

ack 表示对方下次期望接收的对方报文段的第一个数据字节的序号。因此为对方报文的序号 seq 增加 1。
下一个请求的 seq 值为对方发来的 ack 值。

释放：四报文握手

数据传输结束后，通信的双方都可释放连接。现在 A 的应用进程先向其 TCP 发出连接释放报文段，并停止再发送数据，主动关闭 TCP 连接。A 把连接释放报文段首部的 $FIN = 1$ ，其序号 $seq = u$ ，等待 B 的确认。
B 发出确认，确认号 $ack = u + 1$ ，而这个报文段自己的序号 $seq = v$ 。TCP 服务器进程通知高层应用进程。从 A 到 B 这个方向的连接就释放了，TCP 连接处于半关闭状态。此时 B 若发送数据，A 仍要接收。
若 B 已经没有要向 A 发送的数据，其应用进程就通知 TCP 释放连接。
A 收到连接释放报文段后，必须发出确认。在确认报文段中 $ACK = 1$ ，确认号 $ack = w + 1$ ，自己的序号 $seq = u + 1$ 。
TCP 连接必须经过时间 2MSL 后才真正释放掉。

MSL 最大报文生存时间

FIN 表示请求释放连接

第三步中，发送给 A 的 ACQ 不变，因为这是 A 没有向 B 发送数据。

应用层

DNS

功能

负责域名到 IP 地址的解析。

查询过程

主机向本地域名服务器的查询一般都是采用递归查询。如果主机所询问的本地域名服务器不知道被查询域名的 IP 地址，那么本地域名服务器就以 DNS 客户的身份，向其他根域名服务器继续发出查询请求报文。

本地域名服务器向根域名服务器的查询通常是采用迭代查询。当根域名服务器收到本地域名服务器的迭代查询请求报文时，要么给出所要查询的 IP 地址，要么告诉本地域名服务器：“你下一步应当向哪一个域名服务器进行查询”。然后让本地域名服务器进行后续的查询。

几种域名服务器：
根域名服务器 所有的根域名服务器都知道所有的顶级域名服务器的域名和 IP 地址。
顶级域名服务器（即 TLD 服务器）负责管理在该顶级域名服务器注册的所有二级域名。
权限域名服务器 负责一个区的域名服务器。当一个权限域名服务器还不能给出最后的查询回答时，就会告诉发出查询请求的 DNS 客户，下一步应当找哪一个权限域名服务器。
本地域名服务器 当一个主机发出 DNS 查询请求时，这个查询请求报文就发送给本地域名服务器。

两种查询方式的区别：

递归查询中，客户只需要查询一次
迭代查询中，客户往往需要查询很多次

高速缓存：每个域名服务器都维护一个高速缓存，存放最近用过的名字以及从何处获得名字映射信息的记录。这可以大大减少网络请求。

实验

路由器常用命令

视图命令

命令	解释
`system-view`	进入系统视图
`int <接口名称>`	进入接口视图
`quit`	退出当前视图

接口视图下的命令

命令	解释
`ip address <IP地址> <子网掩码>`	配置当前视图的 IP 地址
`rip 2 multicast`	设置 RIP 协议的版本为 2，采用组播方式

系统视图下的命令

命令	解释
`sysname <名称>`	设置系统名称
`ip route-static <目的网段> <子网掩码> <下一跳> [preference <优先级>]`	配置一条静态路由
`dis ip rout`	查看路由表
`ping <IP地址>`	执行 ping 命令

静态路由配置实验

配置步骤：

进入各个端口的视图，配置各个端口的 IP 地址
进入系统视图，配置静态路由表
查看路由表，康康是否配置成功
配置主机的 IP 地址，默认网关为路由器的地址。ping对方主机，康康是否能够 ping 通。

Router A:

<Quidway>system-view /***切换到系统视图***/
[Quidway]sysname RouterA /***给设备当前的名称命名为Router A***/
[RouterA] int Ethernet0/0/0 /***进入端口视图***/
[RouterA-Ethernet0/0/0]ip address 2.2.2.1 255.255.255.0 /***配置接口IP地址***/
[RouterA-Ethernet0/0/0]int Ethernet0/0/1 /***进入端口视图***/
[RouterA-Ethernet0/0/1]ip address 1.1.1.1 255.255.255.0 /***配置接口IP地址***/
[RouterA-Ethernet0/0/1]quit /***退回系统视图***/
[RouterA] ip route-static 3.3.3.0 255.255.255.0 1.1.1.2 preference 60 /***配置静态路由***/

Router B:

<Quidway>system-view /***切换到系统视图***/
[Quidway]sysname RouterB /***给设备当前的名称命名为Router B***/
[RouterB] int Ethernet0/0/0 /***进入端口视图***/
[RouterB-Ethernet0/0/0]ip address 3.3.3.1 255.255.255.0 /***配置接口IP地址***/
[RouterB-Ethernet0/0/0]interface Ethernet0/0/1 /***进入端口视图***/
[RouterB-Ethernet0/0/1]ip address 1.1.1.2 255.255.255.0 /***配置接口IP地址***/
[RouterB-Ethernet0/0/1]quit /***退回系统视图***/
[RouterB] ip route-static 2.2.2.0 255.255.255.0 1.1.1.1 preference 60 /***配置静态路由***/

RIP 协议路由配置实验

配置步骤：

进入各个端口的视图，配置各个端口的 IP 地址、RIP 协议的版本号和组播
启动 RIP 协议，发送网段，同时可关闭路由聚合功能
查看路由表，康康是否配置成功
配置主机的 IP 地址，默认网关为路由器的地址。ping对方主机，康康是否能够 ping 通。

需要用到的命令：

命令	解释
`rip 2 multicast`	端口视图下，设置 RIP 协议的版本为 2，采用组播方式
`rip`	启动 RIP 协议
`net <网段 \| all>`	RIP 视图下，发布一个网络
`undo summary`	RIP 视图下，取消路由聚合功能

Router A:

<Quidway>system-view /***切换到系统视图***/
[Quidway]sysname RouterA /***给设备当前的名称命名为Router A***/
[RouterA] int Ethernet0/0/0 /***切换到接口视图***/
[RouterA-Ethernet0/0/0]ip address 2.2.2.1 255.255.255.0 /***配置接口IP地址***/
[RouterA-Ethernet0/0/0]rip version 2 multicast /***指定接口RIP工作的版本***/
[RouterA-Ethernet0/0/0]int Ethernet0/0/1 /***切换到接口视图***/
[RouterA-Ethernet0/0/1]ip address 1.1.1.1 255.255.255.0 /***配置接口IP地址***/
[RouterA-Ethernet0/0/1] rip version 2 multicast /***指定接口RIP工作的版本***/
[RouterA-Ethernet0/0/1]quit /***退回系统视图***/
[RouterA]rip /***启动RIP协议***/
[RouterA-rip]net 1.0.0.0 /***发布网段***/
[RouterA-rip]net 2.0.0.0 /***同上 ***/
[RouterA-rip]undo summary /***取消路由聚合功能***/

Router B:

<Quidway>system-view /***切换到系统视图***/
[Quidway]sysname RouterB /***给设备当前的名称命名为Router B***/
[RouterB] int Ethernet0/0/0 /***切换到接口视图***/
[RouterB-Ethernet0/0/0]ip address 3.3.3.1 255.255.255.0 /***配置接口IP地址***/
[RouterB-Ethernet0/0/0] rip version 2 multicast /***指定接口RIP工作的版本***/
[RouterB-Ethernet0/0/0]int Ethernet0/0/1 /***进入端口视图***/
[RouterB-Ethernet0/0/1]ip address 1.1.1.2 255.255.255.0 /***配置接口IP地址***/
[RouterB-Ethernet0/0/1] rip version 2 multicast /***指定接口RIP工作的版本***/
[RouterB-Ethernet0/0/1]quit /***退回系统视图***/
[RouterB]rip /***启动RIP协议***/
[RouterB-rip]net 1.0.0.0 /***发布网段***/
[RouterB-rip]net 3.0.0.0 /***同上 ***/
[RouterB-rip]undo summary /***取消路由聚合功能***/

OSPF 协议路由配置实验

配置各个端口的 IP 地址
定义路由 ID，要求整个自治网络唯一
启动 OSPF 协议
配置各个区域的网段和反掩码（不是掩码）。配置完一个区域后使用 quit 退出。

命令	解释
`router id <ID>`	定义自治系统中的路由 ID
`ospf`	启动 OSPF
`area <区域号>`	创建一个区域
`network <网段> <反掩码>`	区域视图下，发布一个网络

RouterA:

<Quidway>system-view /***切换到系统视图***/
[Quidway]sysname RouterA /***给设备当前的名称命名为Router A***/
[RouterA] int Ethernet0/0 /***进入E0/0接口***/
[RouterA-Ethernet0/0]ip address 2.2.2.1 255.255.255.0 /***配置接口IP地址***/
[RouterA-Ethernet0/0]int serial 0/0 /***进入S0/0接口***/
[RouterA-serial 0/0]ip address 1.1.1.1 255.255.255.0 /***配置接口IP地址***/
[RouterA-serial 0/0]quit /***退回系统视图***/
[RouterA]router id 1.1.1.1 /***定义设备的Router id ***/
[RouterA]ospf /***启动OSPF协议***/
[RouterA-ospf-1]area 0 /***创建区域0***/
[RouterA-ospf-1-area0.0.0.0]network 1.1.1.0 0.0.0.255 /***发布网段***/
[RouterA-ospf-1-area0.0.0.0]quit /***退出当前视图***/
[RouterA-ospf-1]area 1 /***创建区域1***/
[RouterA-ospf-1-area0.0.0.1]network 2.2.2.0 0.0.0.255 /***发布网段***/

Router B:
<Quidway>system-view /***切换到系统视图***/
[Quidway]sysname RouterB /***给设备当前的名称命名为Router B***/
[RouterB] int Ethernet0/0 /***进入E0/0接口***/
[RouterB-Ethernet0/0]ip address 3.3.3.1 255.255.255.0 /***配置接口IP地址***/
[RouterB-Ethernet0/0]int serial 0/0 /***进入S0/0接口***/
[RouterB-serial 0/0]ip address 1.1.1.2 255.255.255.0 /***配置接口IP地址***/
[RouterB-serial 0/0]quit /***退回系统视图***/
[RouterB]router id 1.1.1.2 /***定义设备的Router id ***/
[RouterB]ospf /***启动OSPF协议***/
[RouterB-ospf-1]area 0 /***创建区域0***/
[RouterB-ospf-1-area0.0.0.0]network 1.1.1.0 0.0.0.255 /***发布网段***/
[RouterB-ospf-1-area0.0.0.0]quit /***退出当前视图***/
[RouterB-ospf-1]area 2 /***创建区域2***/
[RouterB-ospf-1-area0.0.0.1]network 3.3.3.0 0.0.0.255 /***发布网段***/

考研题

1

某网络拓扑如图 A-3 所示，路由器 R1 通过接口 E1、E2 分别连接局域网 1、局域网 2，通过接口 L0 连接路由器 R2，并通过路由器 R2 连接域名服务器与互联网。Rl 的 L0 接口的 P 地址是 202.118.2.1，R2 的 L0 接口的 IP 地址是 202.118.2.2，L1 接口的 IP 地址是 130.11.120.1，EO 接口的 P 地址是 202.118.3.1，域名服务器的 P 地址是 202.118.3.2。

R1 和 R2 的路由表结构为：目的网络 IP 地址、子网掩码、下一跳 IP 地址、接口

将 IP 地址空间 202.118.1.0/24 划分为 2 个子网，分别分配给局域网 1、局域网 2，每个局域网需分配的 IP 地址数不少于 120 个。请给出子网划分结果，说明理由或给出必要的计算过程。
请给出 R1 的路由表，使其明确包括到局域网 1 的路由、局域网 2 的路由、域名服务器的主机路由和互联网的路由。
请采用路由聚合技术，给出 R2 到局域网 1 和局域网 2 的路由。

解

2

某局域网采用 CSMA/CD 协议实现介质访问控制，数据传输速率为 10Mbit/s，主机甲和主机乙之间的距离为 2km，信号传播速度为 200 000km/s。请回答下列问题，要求说明理由或写出计算过程。

若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间？最长需经过多长时间（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）？
若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1 518B）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个 64B 的确认帧，主机甲收到确认帧后方可发送下一个数据帧。此时主机甲的有效数据传输速率是多少（不考虑以太网的前导码）？

解