计算机网络笔记

本页面主要总结计算机网络的部分考核内容。

电路交换

电路交换必定是面向连接的。

电路交换分为三个阶段：

建立连接：建立一条专用的物理通路，以保证双方通话时所需的通信资源在通信时不会被其他用户占用；
通信：主叫和被叫双方就能互相通电话；
释放连接：释放刚才使用的这条专用的物理通路（释放刚才占用的所有通信资源）。

特点

计算机数据具有突发性，这导致在传送计算机数据时，通信线路的利用率很低（用来传送数据的时间往往不到 10% 甚至不到 1% ）。

分组交换

分组交换则采用存储转发技术。

在发送端，先把较长的报文划分成较短的、固定长度的数据段。

分组交换示例

接收端收到分组后剥去首部还原成报文。

性质

每一个分组的首部都含有地址（诸如目的地址和源地址）等控制信息。

分组交换网中的结点交换机根据收到的分组首部中的地址信息，把分组转发到下一个结点交换机。

每个分组在互联网中独立地选择传输路径。

用这样的存储转发方式，最后分组就能到达最终目的地。

路由器处理分组

在路由器中的输入和输出端口之间没有直接连线。路由器处理分组的过程是：

把收到的分组先放入缓存（暂时存储）；
查找转发表，找出到某个目的地址应从哪个端口转发；
把分组送到适当的端口转发出去。

提示

主机与路由器不同：

主机是为用户进行信息处理的，并向网络发送分组，从网络接收分组。

路由器对分组进行存储转发，最后把分组交付目的主机。

优点

优点	所采用的手段
高效	在分组传输的过程中动态分配传输带宽，对通信链路是逐段占用。
灵活	为每一个分组独立地选择最合适的转发路由。
迅速	以分组作为传送单位，可以先建立连接就能向其他主机发送分组。
可靠	保证可靠性的网络协议；分布式多路由的分组交换网，使网络有很好的生存性。

问题

分组在各结点存储转发时需要排队，这就会造成一定的时延。
分组必须携带的首部（里面有必不可少的控制信息）也造成了一定的开销。

时延

时延 (delay 或 latency) ，有时也称为延迟或迟延，是指数据（一个报文或分组，甚至比特）从网络（或链路）的一端传送到另一端所需的时间。

数据在网络中经历的总时延是发送时延、传播时延、处理时延和排队时延之和。

总时延 = 发送时延 + 传播时延 + 处理时延 + 排队时延

发送时延

发送时延：也称为传输时延。

发送数据时，数据帧从结点进入到传输媒体所需要的时间。

也就是从发送数据帧的第一个比特算起，到该帧的最后一个比特发送完毕所需的时间。

发送时延 = 数据帧长度 (bit) / 发送速率 (bit/s)

传播时延

传播时延是电磁波在信道中需要传播一定的距离而花费的时间。

注意

发送时延与传播时延有本质上的不同。

信号发送速率和信号在信道上的传播速率是完全不同的概念。

传播时延 = 信道长度（米）/ 信号在信道上的传播速率（米/秒）

处理时延

主机或路由器在收到分组时，为处理分组（例如分析首部、提取数据、差错检验或查找路由）所花费的时间。

排队时延

分组在路由器输入输出队列中排队等待处理所经历的时延。

排队时延的长短往往取决于网络中当时的通信量。

时延带宽积

链路的时延带宽积又称为以比特为单位的链路长度。

时延带宽积 = 传播时延 × 带宽

往返时间

互联网上的信息不仅仅单方向传输，而是双向交互的。因此，有时很需要知道双向交互一次所需的时间。

往返时间 RTT (round-trip time) 表示从发送方发送数据开始，到发送方收到来自接收方的确认，总共经历的时间。

在互联网中，往返时间还包括各中间结点的处理时延、排队时延以及转发数据时的发送时延。

当使用卫星通信时，往返时间 RTT 相对较长，是很重要的一个性能指标。

协议概览

OSI

OSI 的七层协议体系结构的概念清楚，理论也较完整，但它既复杂又不实用。

其划分为：

应用层表示层会话层运输层网络层数据链路层物理层

TCP/IP

应用层（各种应用层协议，如 DNS, HTTP, SMTP 等）

运输层（TCP或UDP）

网际层（IP）

网络接口层（这一层并没有具体内容）

5层协议

采取折中的办法，即综合 OSI 和 TCP/IP 的优点，采用一种只有五层协议的体系结构。

应用层运输层网络层数据链路层物理层

5层协议

其发送、接收步骤如下：

发送

应用进程数据报文 (Message) 先传送到应用层，加上应用层首部，成为应用层 PDU

PDU (Protocol Data Unit)：协议数据单元。

OSI 参考模型把对等层次之间传送的数据单位称为该层的协议数据单元 PDU。
加上运输层首部，成为段 (Segment)
加上网络层首部，成为 IP 数据包 (Packet)（或分组）
加上链路层首部和尾部，成为数据链路层帧 (Frame)
最下面的物理层把比特流传送到物理媒体，作为独立的比特 (bit) 来传输
电信号（或光信号）在物理媒体中传播从发送端物理层传送到接收端物理层

接收

物理层接收到比特流，上交给数据链路层
数据链路层剥去帧首部和帧尾部，取出数据部分，上交给网络层
网络层剥去首部，取出数据部分上交给运输层
运输层剥去首部，取出数据部分上交给应用层
应用层剥去首部，取出应用程序数据上交给应用进程

5层传输过程

协议和服务

协议的实现保证了能够向上一层提供服务。

本层的服务用户只能看见服务而无法看见下面的协议。即下面的协议对上面的服务用户是透明的。

协议是“水平的”，即协议是控制对等实体之间通信的规则。

服务是“垂直的”，即服务是由下层向上层通过层间接口提供的。

上层使用服务原语获得下层所提供的服务。

时分复用

时分复用则是将时间划分为一段段等长的时分复用帧（TDM帧）。每一个时分复用的用户在每一个 TDM 帧中占用固定序号的时隙。

每一个用户所占用的时隙是周期性地出现（其周期就是TDM帧的长度）的。

TDM 信号也称为等时 (isochronous) 信号。

时分复用的所有用户在不同的时间占用同样的频带宽度。

码分复用

常用的名词是码分多址 CDMA (Code Division Multiple Access)。

各用户使用经过特殊挑选的不同码型，因此彼此不会造成干扰。

这种系统发送的信号有很强的抗干扰能力，其频谱类似于白噪声，不易被敌人发现。

码片序列

每一个比特时间划分为 m 个短的间隔，称为码片 (chip)。

每个站被指派一个唯一的 m bit 码片序列。

如发送比特 1，则发送自己的 m bit 码片序列。
如发送比特 0，则发送该码片序列的二进制反码。

例如，S 站的 8 bit 码片序列是 00011011。

发送比特 1 时，就发送序列 00011011，
发送比特 0 时，就发送序列 11100100。

S 站的码片序列：(–1 –1 –1 +1 +1 –1 +1 +1)

扩频特性

假定S站要发送信息的数据率为 b bit/s。由于每一个比特要转换成 m 个比特的码片，因此 S 站实际上发送的数据率提高到 mb bit/s，同时 S 站所占用的频带宽度也提高到原来数值的 m 倍。

这种通信方式是扩频(spread spectrum)通信中的一种。

扩频通信通常有两大类：

一种是直接序列扩频DSSS (Direct Sequence Spread Spectrum)，如上面讲的使用码片序列就是这一类。
另一种是跳频扩频FHSS (Frequency Hopping Spread Spectrum)。

特点

每个站分配的码片序列不仅必须各不相同，并且还必须互相正交 (orthogonal)。

在实用的系统中是使用伪随机码序列。

数据链路层协议

封装成帧

封装成帧 (framing) 就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。

封装成帧

首部和尾部的一个重要作用就是进行帧定界。

当数据是由可打印的 ASCII 码组成的文本文件时，帧定界可以使用特殊的帧定界符。

帧定界符

控制字符 SOH (Start Of Header) 放在一帧的最前面，表示帧的首部开始。另一个控制字符 EOT (End Of Transmission) 表示帧的结束。

透明传输

如果数据中的某个字节的二进制代码恰好和 SOH 或 EOT 一样，数据链路层就会错误地“找到帧的边界”。

解决方法：字节填充 (byte stuffing) 或字符填充 (character stuffing)。

发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是1B)。

接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。

如果转义字符也出现在数据当中，那么应在转义字符前面插入一个转义字符 ESC。当接收端收到连续的两个转义字符时，就删除其中前面的一个。

透明传输解决

差错检测

在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。

误码率与信噪比有很大的关系。

为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。

在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。

循环冗余检验

在发送端，先把数据划分为组。假定每组 k 个比特。

在每组 M 后面再添加供差错检测用的 n 位冗余码，然后一起发送出去。

冗余码计算过程：

用二进制的模 2 运算进行 \(2^n\) 乘 M 的运算，这相当于在 M 后面添加 n 个 0。
得到的 (k + n) 位的数除以事先选定好的长度为 (n + 1) 位的除数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 少 1 位，即 R 是 n 位。
将余数 R 作为冗余码拼接在数据 M 后面，一起发送出去。

冗余码计算和检验

接收端检验：

若得出的余数 R = 0，则判定这个帧没有差错，就接受 (accept)。
若余数 R ≠ 0，则判定这个帧有差错，就丢弃。

但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。

只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。

计算示例

现在 k = 6, M = 101001。

设 n = 3, 除数 P = 1101，

被除数是 ( M << n ) = 101001000。

模 2 运算的结果是：商 Q = 110101，余数 R = 001。

把余数 R 作为冗余码添加在数据 M 的后面发送出去。发送的数据是：2nM + R，即：101001001，共 (k + n) 位。

CSMA / CD

CSMA/CD 含义：载波监听多点接入 / 碰撞检测 (Carrier Sense Multiple Access with Collision Detection) 。

“多点接入”表示许多计算机以多点接入的方式连接在一根总线上。

“载波监听”是指每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞。

总线上并没有什么“载波”。因此， “载波监听”就是用电子技术检测总线上有没有其他计算机发送的数据信号。

“碰撞检测”就是计算机边发送数据边检测信道上的信号电压大小。

当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。

当一个站检测到的信号电压摆动值超过一定的门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。

所谓“碰撞”就是发生了冲突。因此“碰撞检测”也称为“冲突检测”。

在发生碰撞时，总线上传输的信号产生了严重的失真，无法从中恢复出有用的信息来。

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

争用期

最先发送数据帧的站，在发送数据帧后至多经过时间 \(2 \tau\) （两倍的端到端往返时延）就可知道发送的数据帧是否遭受了碰撞。

以太网的端到端往返时延 \(2 \tau\) 称为争用期，或碰撞窗口。

经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

退避算法

常用二进制指数类型退避算法：

发生碰撞的站在停止发送数据后，要推迟（退避）一个随机时间才能再发送数据。

基本退避时间取为争用期 \(2 \tau\) 。
从整数集合 [0, 1, … , (2k - 1)] 中随机地取出一个数，记为 r。重传所需的时延就是 r 倍的基本退避时间。
参数 k 按下面的公式计算：

k = Min[重传次数, 10]
当 k ≤ 10 时，参数 k 等于重传次数。
当重传达 16 次仍不能成功时即丢弃该帧，并向高层报告。

示例

第 1 次冲突重传时：

k = 1，r 为 {0，1} 集合中的任何一个数。

第 2 次冲突重传时：

k = 2，r 为 {0，1，2，3} 集合中的任何一个数。

第 3 次冲突重传时：

k = 3，r 为 {0，1，2，3，4，5，6，7} 集合中的任何一个数。

最短有效帧长

如果发生冲突，就一定是在发送的前 64 字节之内。

由于一检测到冲突就立即中止发送，这时已经发送出去的数据一定小于 64 字节。

以太网规定了最短有效帧长为 64 字节，凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。

流程图

CSMA-CD

特性

使用 CSMA/CD 协议的以太网不能进行全双工通信而只能进行双向交替通信（半双工通信）。

每个站在发送数据之后的一小段时间内，存在着遭遇碰撞的可能性。

这种发送的不确定性使整个以太网的平均通信量远小于以太网的最高数据率。

MAC 层

在局域网中，硬件地址又称为物理地址，或 MAC 地址。

802 标准所说的“地址”严格地讲应当是每一个站的“名字”或标识符。

但鉴于大家都早已习惯了将这种 48 位的“名字”称为“地址”，所以本书也采用这种习惯用法，尽管这种说法并不太严格。

IEEE 802 标准规定 MAC 地址字段可采用 6 字节 (48 位) 或 2 字节 (16 位) 这两种中的一种。

IEEE 的注册管理机构 RA 负责向厂家分配地址字段 6 个字节中的前三个字节 (即高位 24 位)，称为组织唯一标识符。

地址字段 6 个字节中的后三个字节 (即低位 24 位) 由厂家自行指派，称为扩展唯一标识符，必须保证生产出的适配器没有重复地址。

一个地址块可以生成 224 个不同的地址。这种 48 位地址称为 MAC-48，它的通用名称是 EUI-48。

生产适配器时，6 字节的 MAC 地址已被固化在适配器的 ROM，因此，MAC 地址也叫做硬件地址 (hardware address) 或物理地址。

“MAC 地址”实际上就是适配器地址或适配器标识符 EUI-48。

MAC 帧格式

MAC帧格式

目的地址字段 6 字节

源地址字段 6 字节

类型字段 2 字节

数据字段 46 ~ 1500 字节

数据字段的正式名称是 MAC 客户数据字段。

最小长度 64 字节 - 18 字节的首部和尾部 = 数据字段的最小长度（46字节）

FCS 字段 4 字节

当数据字段的长度小于 46 字节时，应在数据字段的后面加入整数字节的填充字段，以保证以太网的 MAC 帧长不小于 64 字节。

在帧的前面插入（硬件生成）的 8 字节中，第一个字段共 7 个字节，是前同步码，用来迅速实现 MAC 帧的比特同步。第二个字段 1 个字节是帧开始定界符，表示后面的信息就是 MAC 帧。

帧间最小间隔

帧间最小间隔为 9.6 μs，相当于 96 bit 的发送时间。

一个站在检测到总线开始空闲后，还要等待 9.6 μs 才能再次发送数据。

这样做是为了使刚刚收到数据帧的站的接收缓存来得及清理，做好接收下一帧的准备。

交换机自学习

以太网交换机可以运行自学习算法自动维护交换表。

交换机自学习

虚拟局域网

利用以太网交换机可以很方便地实现虚拟局域网 VLAN (Virtual LAN)。

IEEE 802.1Q 对虚拟局域网 VLAN 的定义：

虚拟局域网 VLAN 是由一些局域网网段构成的与物理位置无关的逻辑组，而这些网段具有某些共同的需求。每一个 VLAN 的帧都有一个明确的标识符，指明发送这个帧的计算机是属于哪一个 VLAN。

虚拟局域网其实只是局域网给用户提供的一种服务，而并不是一种新型局域网。

由于虚拟局域网是用户和网络资源的逻辑组合，因此可按照需要将有关设备和资源非常方便地重新组合，使用户从不同的服务器或数据库中存取所需的资源。

优点

改善了性能：虚拟局域网限制了接收广播信息的工作站数，使得网络不会因传播过多的广播信息 (即“广播风暴”) 而引起性能恶化。
简化了管理
降低了成本：性能提高，开销降低。
改善了安全性：独立广播域

虚拟局域网的以太网帧

IEEE 批准了 802.3ac 标准，该标准定义了以太网的帧格式的扩展，以支持虚拟局域网。

虚拟局域网协议允许在以太网的帧格式中插入一个4字节的标识符，称为 VLAN 标记 (tag)，用来指明该帧属于哪一个虚拟局域网。

插入VLAN标记得出的帧称为 802.1Q 帧或带标记的以太网帧。

虚拟局域网以太网帧

地址解析协议

已经知道了一个机器（主机或路由器）的IP地址，如何找出其相应的硬件地址？

地址解析协议 ARP 就是用来解决这样的问题的。

不管网络层使用的是什么协议，在实际网络的链路上传送数据帧时，最终还是必须使用硬件地址。

每一个主机都设有一个 ARP 高速缓存 (ARP cache)，里面有所在的局域网上的各主机和路由器的 IP 地址到硬件地址的映射表。

< IP address；MAC address；TTL > TTL (Time To Live)：地址映射有效时间。

ARP 高速缓存存放最近获得的 IP 地址到 MAC 地址的绑定，以减少 ARP 广播的数量。

为了减少网络上的通信量，主机 A 在发送其 ARP 请求分组时，就将自己的 IP 地址到硬件地址的映射写入 ARP 请求分组。

当主机 B 收到 A 的 ARP 请求分组时，就将主机 A 的这一地址映射写入主机 B 自己的 ARP 高速缓存中。这对主机 B 以后向 A 发送数据报时就更方便了。

地址解析流程

当主机 A 欲向本局域网上的某个主机 B 发送 IP 数据报时，就先在其 ARP 高速缓存中查看有无主机 B 的 IP 地址。

如有，就可查出其对应的硬件地址，再将此硬件地址写入 MAC 帧，然后通过局域网将该 MAC 帧发往此硬件地址。
如没有， ARP 进程在本局域网上广播发送一个 ARP 请求分组。收到 ARP 响应分组后，将得到的 IP 地址到硬件地址的映射写入 ARP 高速缓存。

ARP请求分组：包含发送方硬件地址 / 发送方 IP 地址 / 目标方硬件地址(未知时填 0) / 目标方 IP 地址。

本地广播 ARP 请求（路由器不转发ARP请求）。

ARP 响应分组：包含发送方硬件地址 / 发送方 IP地址 / 目标方硬件地址 / 目标方 IP 地址。

ARP 分组封装在物理网络的帧中传输。

注意的问题

ARP 用于解决同一个局域网上的主机或路由器的 IP 地址和硬件地址的映射问题。

如果所要找的主机和源主机不在同一个局域网上，那么就要通过 ARP 找到一个位于本局域网上的某个路由器的硬件地址，然后把分组发送给这个路由器，让这个路由器把分组转发给下一个网络。剩下的工作就由下一个网络来做。
从 IP 地址到硬件地址的解析是自动进行的，主机的用户对这种地址解析过程是不知道的。

只要主机或路由器要和本网络上的另一个已知 IP 地址的主机或路由器进行通信，ARP 协议就会自动地将该 IP 地址解析为链路层所需要的硬件地址。

使用场景

发送方是主机，要把 IP 数据报发送到本网络上的另一个主机。这时用 ARP 找到目的主机的硬件地址。
发送方是主机，要把 IP 数据报发送到另一个网络上的一个主机。这时用 ARP 找到本网络上的一个路由器的硬件地址。剩下的工作由这个路由器来完成。
发送方是路由器，要把 IP 数据报转发到本网络上的一个主机。这时用 ARP 找到目的主机的硬件地址。
发送方是路由器，要把 IP 数据报转发到另一个网络上的一个主机。这时用 ARP 找到本网络上另一个路由器的硬件地址。剩下的工作由这个路由器来完成。

IP 数据报格式

IP数据报格式

一个 IP 数据报由首部和数据两部分组成。

首部的前一部分是固定长度，共 20 字节，是所有 IP 数据报必须具有的。

在首部的固定部分的后面是一些可选字段，其长度是可变的。

各字段简述如下：

版本：占 4 位，指 IP 协议的版本。目前的 IP 协议版本号为 4 (即 IPv4)。

首部长度：占 4 位，可表示的最大数值是 15 个单位(一个单位为 4 字节)，因此 IP 的首部长度的最大值是 60 字节。

区分服务：占 8 位，用来获得更好的服务。在旧标准中叫做服务类型，但实际上一直未被使用过。1998 年这个字段改名为区分服务。

只有在使用区分服务（DiffServ）时，这个字段才起作用。

在一般的情况下都不使用这个字段

总长度：占 16 位，指首部和数据之和的长度，单位为字节，因此数据报的最大长度为 65535 字节。

总长度必须不超过最大传送单元 MTU。

标识(identification) ：占 16 位，它是一个计数器，用来产生 IP 数据报的标识。

标志(flag) ：占 3 位，目前只有前两位有意义。

标志字段的最低位是 MF (More Fragment)。

MF=1 表示后面“还有分片”。MF=0 表示最后一个分片。
标志字段中间的一位是 DF (Don't Fragment) ，只有当 DF=0 时才允许分片。

片偏移：占 13 位，指出：较长的分组在分片后，某片在原分组中的相对位置。片偏移以 8 个字节为偏移单位。

分片示例

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

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

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

原始数据报首部被复制为各数据报片的首部，但必须修改有关字段的值。

分片示例

	总长度	标识	MF	片偏移
原始数据报	2820	12345	0	0
数据报片1	1420	12345	1	0
数据报片2	1420	12345	1	175
数据报片3	1020	12345	0	350

生存时间：占8 位，记为 TTL (Time To Live)，指示数据报在网络中可通过的路由器数的最大值。

协议：占8 位，指出此数据报携带的数据使用何种协议，以便目的主机的 IP 层将数据部分上交给哪种处理过程，例如 ICMP，TCP，UDP，OSPF 等多种协议 PDU。

首部检验和：占16 位，只检验数据报的首部，不检验数据部分。这里不采用 CRC 检验码而采用简单的 16 位二进制反码求和算法。

源地址和目的地址都各占 4 字节

可变部分就是一个选项字段，用来支持排错、测量以及安全等措施，内容很丰富。

选项字段的长度可变，从 1 个字节到 40 个字节不等，取决于所选择的项目。

增加首部的可变部分是为了增加 IP 数据报的功能，但这同时也使得 IP 数据报的首部长度成为可变的。这就增加了每一个路由器处理数据报的开销。

实际上这些选项很少被使用。

子网划分

A 类地址最高位固定为 0，默认子网掩码为 255.0.0.0

B 类地址最高位固定为 10，默认子网掩码为 255.255.0.0

C 类地址最高位固定为 110，默认子网掩码为 255.255.255.0

D 类地址最高位固定为 1110，从224.0.0.0到239.255.255.255。

E 类地址最高位固定为 1111，为保留地址。

CIDR

无分类域间路由选择 CIDR (Classless Inter-Domain Routing) 消除了传统的 A 类、B 类和 C 类地址以及划分子网的概念，因而可以更加有效地分配 IPv4 的地址空间。

CIDR使用各种长度的“网络前缀”(network-prefix)来代替分类地址中的网络号和子网号。

IP 地址从三级编址（使用子网掩码）又回到了两级编址。

无分类的两级编址的记法是：

IP地址 ::= {<网络前缀>, <主机号>}

CIDR 使用“斜线记法”(slash notation)，它又称为 CIDR 记法，即在 IP 地址面加上一个斜线“/”，然后写上网络前缀所占的位数（这个数值对应于三级编址中子网掩码中 1 的个数）。例如： 220.78.168.0/24

CIDR 把网络前缀都相同的连续的 IP 地址组成“CIDR 地址块”。

128.14.32.0/20 表示的地址块共有 \(2^{12}\) 个地址（因为斜线后面的 20 是网络前缀的位数，所以这个地址的主机号是 12 位）。

这个地址块的起始地址是 128.14.32.0。
在不需要指出地址块的起始地址时，也可将这样的地址块简称为“/20 地址块”。
128.14.32.0/20 地址块的最小地址：128.14.32.0
128.14.32.0/20 地址块的最大地址：128.14.47.255
全 0 和全 1 的主机号地址一般不使用。

路由聚合

一个 CIDR 地址块可以表示很多地址，这种地址的聚合常称为路由聚合，它使得路由表中的一个项目可以表示很多个（例如上千个）原来传统分类地址的路由。

路由聚合有利于减少路由器之间的路由选择信息的交换，从而提高了整个互联网的性能。

路由聚合也称为构成超网 (supernetting)。

CIDR 虽然不使用子网了，但仍然使用“掩码”这一名词（但不叫子网掩码）。

对于 /20 地址块，它的掩码是 20 个连续的 1。斜线记法中的数字就是掩码中1的个数。

前缀长度不超过 23 位的 CIDR 地址块都包含了多个 C 类地址。

这些 C 类地址合起来就构成了超网。

CIDR 地址块中的地址数一定是 2 的整数次幂。网络前缀越短，其地址块所包含的地址数就越多。而在三级结构的IP地址中，划分子网是使网络前缀变长。

CIDR 的一个好处是：可以更加有效地分配 IPv4 的地址空间，可根据客户的需要分配适当大小的 CIDR 地址块。

最长前缀匹配

使用 CIDR 时，路由表中的每个项目由“网络前缀”和“下一跳地址”组成。在查找路由表时可能会得到不止一个匹配结果。

应当从匹配结果中选择具有最长网络前缀的路由：最长前缀匹配 (longest-prefix matching)。

网络前缀越长，其地址块就越小，因而路由就越具体 (more specific) 。

最长前缀匹配又称为最长匹配或最佳匹配。

静态路由

静态路由选择策略：即非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。

动态路由

动态路由选择策略：即自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。

路由信息协议 RIP

路由信息协议 RIP (Routing Information Protocol) 是内部网关协议 IGP 中最先得到广泛使用的协议。

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

RIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。

从一个路由器到直接连接的网络的距离定义为 1。
从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。

RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。

这里的“距离”实际上指的是“最短距离”。

RIP 认为一个好的路由就是它通过的路由器的数目少，即“距离短”。

RIP 允许一条路径最多只能包含 15 个路由器。 “距离”的最大值为 16 时即相当于不可达。可见 RIP 只适用于小型互联网。

RIP 不能在两个网络之间同时使用多条路由。RIP 选择一个具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。

特点

仅和相邻路由器交换信息。
交换的信息是当前本路由器所知道的全部信息，即自己的路由表。
按固定的时间间隔交换路由信息，例如，每隔 30 秒。当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。
RIP 协议让互联网中的所有路由器都和自己的相邻路由器不断交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。
虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也应当是不同的。

路由表建立

路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为 1）。它的路由表是空的。
以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。
经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。

RIP 协议的收敛 (convergence) 过程较快。“收敛”就是在自治系统中所有的结点都得到正确的路由选择信息的过程。

距离向量算法

其逻辑如下所示

路由器收到相邻路由器（其地址为 X）的一个 RIP 报文：
(1) 先修改此 RIP 报文中的所有项目：把“下一跳”字段中的地址都改为 X，并把所有的“距离”字段的值加 1。
(2) 对修改后的 RIP 报文中的每一个项目，重复以下步骤：
     若项目中的目的网络不在路由表中，则把该项目加到路由表中。
         否则
             若下一跳字段给出的路由器地址是同样的，则把收到的项目替换原路由表中的项目。
                否则 
                    若收到项目中的距离小于路由表中的距离，则进行更新，
       否则，什么也不做。
(3) 若 3 分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达路由器，即将距离置为 16（表示不可达）。
(4) 返回。

距离向量算法的基础就是 Bellman-Ford 算法（或 Ford-Fulkerson 算法）。

这种算法的要点是这样的：

设X是结点 A 到 B 的最短路径上的一个结点。
若把路径 A→B 拆成两段路径 A→X 和 X→B，则每一段路径 A→X 和 X→B 也都分别是结点 A 到 X 和结点 X 到 B 的最短路径。

RIP2 报文格式

RIP2

RIP 协议优缺点

优点：

实现简单，开销较小。

缺点：

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

开放最短路径优先 OSPF

“开放”表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。

“最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法 SPF

采用分布式的链路状态协议 (link state protocol)。

注意：OSPF 只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。

要点：

向本自治系统中所有路由器发送信息，这里使用的方法是洪泛法。

发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。

“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”(metric)。

只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。

链路状态数据库

由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库。

这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的同步）。

OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。

OSPF 的更新过程收敛快是其重要优点。

区域

为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，叫做区域。

每一个区域都有一个 32 位的区域标识符（用点分十进制表示）。

区域也不能太大，在一个区域内的路由器最好不超过 200 个。

划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。

在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。

OSPF 使用层次结构的区域划分。在上层的区域叫做主干区域 (backbone area)。

主干区域的标识符规定为0.0.0.0。主干区域的作用是用来连通其他在下层的区域。

协议特征

OSPF 不用 UDP 而是直接用 IP 数据报传送。

OSPF 构成的数据报很短。这样做可减少路由信息的通信量。

数据报很短的另一好处是可以不必将长的数据报分片传送。

但分片传送的数据报只要丢失一个，就无法组装成原来的数据报，而整个数据报就必须重传。
OSPF 对不同的链路可根据 IP 分组的不同服务类型 TOS 而设置成不同的代价。因此，OSPF 对于不同类型的业务可计算出不同的路由。
如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径。这叫做多路径间的负载平衡。
所有在 OSPF 路由器之间交换的分组都具有鉴别的功能。
支持可变长度的子网划分和无分类编址 CIDR。
每一个链路状态都带上一个 32 位的序号，序号越大状态就越新。
OSPF 还规定每隔一段时间，如 30 分钟，要刷新一次数据库中的链路状态。
由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF 协议要比距离向量协议 RIP 好得多。
OSPF 没有“坏消息传播得慢”的问题，据统计，其响应网络变化的时间小于 100 ms。

OSPF 分组

OSPF分组

五种分组类型：

类型1，问候 (Hello) 分组。

类型2，数据库描述 (Database Description) 分组。

类型3，链路状态请求 (Link State Request) 分组。

类型4，链路状态更新 (Link State Update) 分组，用洪泛法对全网更新链路状态。

类型5，链路状态确认 (Link State Acknowledgment)分组。

发送流程：

OSPF分组发送

边界网关协议 BGP

BGP 是不同自治系统的路由器之间交换路由信息的协议。

互联网的规模太大，使得自治系统之间路由选择非常困难。对于自治系统之间的路由选择，要寻找最佳路由是很不现实的。

当一条路径通过几个不同 AS 时，要想对这样的路径计算出有意义的代价是不太可能的。
比较合理的做法是在 AS 之间交换“可达性”信息。

自治系统之间的路由选择必须考虑有关策略。

因此，边界网关协议 BGP 只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由。

BGP 发言人

每一个自治系统的管理员要选择至少一个路由器作为该自治系统的“ BGP 发言人” (BGP speaker) 。

一般说来，两个 BGP 发言人都是通过一个共享网络连接在一起的，而 BGP 发言人往往就是 BGP 边界路由器，但也可以不是 BGP 边界路由器。

交换路由信息

一个 BGP 发言人与其他自治系统中的 BGP 发言人要交换路由信息，就要先建立 TCP 连接，然后在此连接上交换 BGP 报文以建立 BGP 会话(session)，利用 BGP 会话交换路由信息。

使用 TCP 连接能提供可靠的服务，也简化了路由选择协议。

使用 TCP 连接交换路由信息的两个 BGP 发言人，彼此成为对方的邻站(neighbor)或对等站(peer) 。

特点

BGP 协议交换路由信息的结点数量级是自治系统数的量级，这要比这些自治系统中的网络数少很多。

每一个自治系统中 BGP 发言人（或边界路由器）的数目是很少的。这样就使得自治系统之间的路由选择不致过分复杂。

BGP 支持 CIDR，因此 BGP 的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列。

在 BGP 刚刚运行时，BGP 的邻站是交换整个的 BGP 路由表。但以后只需要在发生变化时更新有变化的部分。这样做对节省网络带宽和减少路由器的处理开销都有好处。

BGP 报文

BGP报文

打开 (OPEN) 报文，用来与相邻的另一个BGP发言人建立关系。

更新 (UPDATE) 报文，用来发送某一路由的信息，以及列出要撤消的多条路由。

保活 (KEEPALIVE) 报文，用来确认打开报文和周期性地证实邻站关系。

通知 (NOTIFICATION) 报文，用来发送检测到的差错。

TCP 与 UDP 区别

TCP 传送的数据单位协议是 TCP 报文段(segment)。

UDP 传送的数据单位协议是 UDP 报文或用户数据报。

UDP与TCP区别

TCP 与 UDP 典型应用

TCP与UDP典型应用

TCP

TCP 是面向连接的运输层协议。

每一条 TCP 连接只能有两个端点 (endpoint)，每一条 TCP 连接只能是点对点的（一对一）。

TCP 提供可靠交付的服务。

TCP 提供全双工通信。

面向字节流

TCP 中的“流”(stream) 指的是流入或流出进程的字节序列。
“面向字节流”的含义是：虽然应用程序和 TCP 的交互是一次一个数据块，但 TCP 把应用程序交下来的数据看成仅仅是一连串无结构的字节流。
TCP 不保证接收方应用程序所收到的数据块和发送方应用程序所发出的数据块具有对应大小的关系。
但接收方应用程序收到的字节流必须和发送方应用程序发出的字节流完全一样。

提示

TCP 连接是一条虚连接而不是一条真正的物理连接。

TCP 对应用进程一次把多长的报文发送到 TCP 的缓存中是不关心的。

TCP 根据对方给出的窗口值和当前网络拥塞的程度来决定一个报文段应包含多少个字节（UDP 发送的报文长度是应用进程给出的）。

TCP 可把太长的数据块划分短一些再传送。

TCP 也可等待积累有足够多的字节后再构成报文段发送出去。

建立 TCP 连接

TCP 把连接作为最基本的抽象。

每一条 TCP 连接有两个端点。

TCP 连接的端点不是主机，不是主机的IP 地址，不是应用进程，也不是运输层的协议端口。TCP 连接的端点叫做套接字 (socket) 或插口。

端口号拼接到 (contatenated with) IP 地址即构成了套接字。

套接字 socket = (IP地址 : 端口号)

例如 套接字 socket = (192.169.1.20 : 2028)

每一条 TCP 连接唯一地被通信两端的两个端点（即两个套接字）所确定。即：

TCP 连接 ::= {socket1, socket2} = {(IP1: port1)，(IP2: port2)}

TCP 连接的特征：

TCP 连接就是由协议软件所提供的一种抽象。
TCP 连接的端点是个很抽象的套接字，即（IP 地址：端口号）。
同一个 IP 地址可以有多个不同的 TCP 连接。
同一个端口号也可以出现在多个不同的 TCP 连接中。

停止等待协议

“停止等待”就是每发送完一个分组就停止发送，等待对方的确认。在收到确认后再发送下一个分组。

全双工通信的双方既是发送方也是接收方。

为了讨论问题的方便，我们仅考虑 A 发送数据，而 B 接收数据并发送确认。因此 A 叫做发送方，而 B 叫做接收方。

超时重传

A 为每一个已发送的分组都设置了一个超时计时器。

A 只要在超时计时器到期之前收到了相应的确认，就撤销该超时计时器，继续发送下一个分组 M2 。

若A在超时计时器规定时间内没有收到B的确认，就认为分组错误或丢失，就重发该分组。

编号

A为每一个发送的分组都进行编号。若B收到了编号相同的分组，则认为收到了重复分组，丢弃重复的分组，并回送确认。

B为发送的确认也进行编号，指示该确认是对哪一个分组的确认。

A根据确认及其编号，可以确定它是对哪一个分组的确认，避免重发发送。若为重复的确认，则将其丢弃。

确认丢失

若 B 所发送的对 M1 的确认丢失了，那么 A 在设定的超时重传时间内不能收到确认，但 A 并无法知道：是自己发送的分组出错、丢失了，或者是 B 发送的确认丢失了。因此 A 在超时计时器到期后就要重传 M1。

假定 B 又收到了重传的分组 M1。这时 B 应采取两个行动：

第一，丢弃这个重复的分组 M1，不向上层交付。
第二，向 A 发送确认。不能认为已经发送过确认就不再发送，因为 A 之所以重传 M1 就表示 A 没有收到对 M1 的确认。

确认迟到

传输过程中没有出现差错，但 B 对分组 M1 的确认迟到了。
A 会收到重复的确认。对重复的确认的处理很简单：收下后就丢弃。
B 仍然会收到重复的 M1，并且同样要丢弃重复的 M1，并重传确认分组。

自动重传请求 ARQ

通常 A 最终总是可以收到对所有发出的分组的确认。如果 A 不断重传分组但总是收不到确认，就说明通信线路太差，不能进行通信。

使用上述的确认和重传机制，我们就可以在不可靠的传输网络上实现可靠的通信。

像上述的这种可靠传输协议常称为自动重传请求 ARQ (Automatic Repeat reQuest)。意思是重传的请求是自动进行的，接收方不需要请求发送方重传某个出错的分组。

停止等待协议的优点是简单，缺点是信道利用率太低。

为了提高传输效率，发送方可以不使用低效率的停止等待协议，而是采用流水线传输。

流水线传输就是发送方可连续发送多个分组，不必每发完一个分组就停顿下来等待对方的确认。这样可使信道上一直有数据不间断地传送。

由于信道上一直有数据不间断地传送，这种传输方式可获得很高的信道利用率。

连续 ARQ 协议

基本思想：

发送方一次可以发出多个分组。
使用滑动窗口协议控制发送方和接收方所能发送和接收的分组的数量和编号。
每收到一个确认，发送方就把发送窗口向前滑动。
接收方一般采用累积确认的方式。
采用回退N（Go-Back-N）方法进行重传。

接收方一般采用累积确认的方式。即不必对收到的分组逐个发送确认，而是对按序到达的最后一个分组发送确认，这样就表示：到这个分组为止的所有分组都已正确收到了。

优点：容易实现，即使确认丢失也不必重传。

缺点：不能向发送方反映出接收方已经正确收到的所有分组的信息。

回退 N

如果发送方发送了前 5 个分组，而中间的第 3 个分组丢失了。这时接收方只能对前两个分组发出确认。发送方无法知道后面三个分组的下落，而只好把后面的三个分组都再重传一次。

这就叫做 Go-back-N（回退 N），表示需要再退回来重传已发送过的 N 个分组。

可见当通信线路质量不好时，连续 ARQ 协议会带来负面的影响。

比较

	连续ARQ协议	停止等待协议
发送的分组数量	多个分组	一个分组
传输控制	滑动窗口协议	停等-等待
确认	累积确认	个别确认
超时定时器	每个发送的分组	每个发送的分组
编号	序号编号	序号编号
重传	回退N，多个分组	一个分组

TCP 报文

TCP报文

MSS (Maximum Segment Size)

是 TCP 报文段中的数据字段的最大长度。

数据字段加上 TCP 首部才等于整个的 TCP 报文段。

所以，MSS是“TCP 报文段长度减去 TCP 首部长度”。

拥塞控制

在某段时间，若对网络中某资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏。这种现象称为拥塞 (congestion)。

拥塞原因

网络拥塞往往是由许多因素引起的。例如：

点缓存的容量太小；
链路的容量不足；
处理机处理的速率太慢；
拥塞本身会进一步加剧拥塞；

慢开始

慢开始 (Slow start)

目的：用来确定网络的负载能力或拥塞程度。

算法的思路：由小到大逐渐增大拥塞窗口数值。

两个变量：

拥塞窗口：

初始拥塞窗口值：2 种设置方法。

1 至 2 个最大报文段（旧标准）

2 至 4 个最大报文段（RFC 5681）
慢开始门限：防止拥塞窗口增长过大引起网络拥塞。

拥塞窗口 cwnd 控制方法：在每收到一个对新的报文段的确认后，可以把拥塞窗口增加最多一个 SMSS 的数值。

拥塞窗口 cwnd 每次的增加量 = min (N, SMSS)

其中 N 是原先未被确认的、但现在被刚收到的确认报文段所确认的字节数。

不难看出，当 N < SMSS 时，拥塞窗口每次的增加量要小于 SMSS。

用这样的方法逐步增大发送方的拥塞窗口 cwnd，可以使分组注入到网络的速率更加合理。

慢开始流程

使用慢开始算法后，每经过一个传输轮次 (transmission round)，拥塞窗口 cwnd 就加倍。

一个传输轮次所经历的时间其实就是往返时间 RTT。

“传输轮次”更加强调：把拥塞窗口 cwnd 所允许发送的报文段都连续发送出去，并收到了对已发送的最后一个字节的确认。

例如，拥塞窗口 cwnd = 4，这时的往返时间 RTT 就是发送方连续发送 4 个报文段，并收到这 4 个报文段的确认，总共经历的时间。

设置慢开始门限状态变量 ssthresh

慢开始门限 ssthresh 的用法如下：

当 cwnd < ssthresh 时，使用慢开始算法。
当 cwnd > ssthresh 时，停止使用慢开始算法而改用拥塞避免算法。
当 cwnd = ssthresh 时，既可使用慢开始算法，也可使用拥塞避免算法。

拥塞避免算法

思路：让拥塞窗口 cwnd 缓慢地增大，避免出现拥塞。

每经过一个传输轮次，拥塞窗口 cwnd = cwnd + 1。

使拥塞窗口 cwnd 按线性规律缓慢增长。

在拥塞避免阶段，具有 “加法增大” (Additive Increase) 的特点。

网络出现拥塞时：

无论在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（重传定时器超时）：

ssthresh = max (cwnd/2，2)
cwnd = 1
执行慢开始算法

目的：迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕。

拥塞控制示例

慢重传和拥塞避免例子

快重传

发送方只要一连收到三个重复确认，就知道接收方确实没有收到报文段，因而应当立即进行重传（即“快重传”），这样就不会出现超时，发送方也不就会误认为出现了网络拥塞。

使用快重传可以使整个网络的吞吐量提高约20%。

采用快重传 FR (Fast Retransmission) 算法可以让发送方尽早知道发生了个别报文段的丢失。

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

快恢复

当发送端收到连续三个重复的确认时，由于发送方现在认为网络很可能没有发生拥塞，因此现在不执行慢开始算法，而是执行快恢复算法 FR (Fast Recovery) 算法：

慢开始门限 ssthresh = 当前拥塞窗口 cwnd / 2 ；
新拥塞窗口 cwnd = 慢开始门限 ssthresh ；
开始执行拥塞避免算法，使拥塞窗口缓慢地线性增大。

慢重传和拥塞避免例子

因此，在示例图的点 ④ 发送方知道现在只是丢失了个别的报文段。于是不启动慢开始，而是执行快恢复算法。这时，发送方调整门限值 ssthresh = cwnd / 2 = 8，同时设置拥塞窗口 cwnd = ssthresh = 8（见图中的点），并开始执行拥塞避免算法。

TCP 拥塞控制的流程图

拥塞控制流程图

TCP 三次握手

TCP三次握手

B 的 TCP 服务器进程先创建传输控制块TCB，准备接受客户进程的连接请求。
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 连接已经建立。