【计算机网络期末复习】

前言

建议课后下来多花点时间，不然到了期末这些内容就是依托答辩

第一章 概述

什么是协议和体系结构？

协议(protocol)：计算机（节点）通信时对信息内容、信息表示以及交换过程遵循的共同约定

体系结构（architecture)：计算机网络非常复杂，一般被分成多个层次，如何分层以及各层采用的协议总和称为体系结构

了解网络应用的两种模型：C/S和P2P模型

客户-服务器C/S(Client-Server)模型：客户方主动发送请求给服务方，请求对方提供相应的服务

P2P(Peer-to-Peer)模型：都是客户方和服务方

什么是资源子网和通信子网？

ARPANET的中概念

资源子网：网络的边缘，提供信息的处理和共享，由运行网络应用程序的主机（端系统）等组成，Internet内容提供者ICP(Internet Content Provider)通过网站(Website)等形式提供内容服务

通信子网：接入网 + 网络的核心，提供信息的传输，由传输媒体(通信线路)以及转发器、集线器、网桥、交换机、路由器等网络互连设备组成

各种网络设备（转发器、集线器、网桥、路由器等）所工作的层次和基本特性

转发器（repeater）：物理层互连设备。连接两段电缆，从它连接的电缆上收到的数字信号转发给连接的另一条电缆中

集线器（Hub）：物理层互连设备。实际上是一个多口转发器。当从一条线路上接收到信号时，集线器会向其他线路转发，如果多于两个端口同时传输，产生并发送一个冲突存在信号，某个网段出现故障时可以关闭对应的端口。转发器和集线器都：工作在物理层，和MAC协议无关，既无缓冲功能，也无分段功能。通过其连接的网段本质上仍然属于同一个冲突域（在同一个冲突域内，任何两个节点同时传输都会遇到冲突）

网桥：数据链路层的网络互连设备，具体见后面。交换机实际上是一种高性能的多端口网桥，也在数据链路层。

路由器：工作在网络层。

了解计算机网络的分类方式：拓扑结构/传输媒体/地理范围等

• 从拓扑角度：不规则网形(mesh)、星形（树形）、总线形、环形网络

• 从传输媒体角度：同轴电缆网/双绞线网/光纤网或无线网等

• 从覆盖范围角度：个人区域网、局域网、城域网、广域网、全球网等

计算机网络的度量：带宽、延迟、RTT和吞吐率，掌握如何计算延迟，如何计算吞吐率等

带宽（Bandwidth）：指某个信号具有的频带宽度，即该信号所包含的各种不同频率的范围，单位是赫兹（Hz）。链路允许通过的信号的频带宽度称为该链路的带宽

延迟：指数据从一端传送到另一端所需的时间

• 处理延迟

• 排队延迟

• 传输延迟：数据首到尾，与数据长度有关

• 传播延迟：点到点，与链路距离有关
  

往返时间RTT：从发送方发送数据开始，到发送方收到来自接收方的确认，总共经历的时间

吞吐率：单位时间内通过某个链路的实际数据量(bps)，

掌握分组交换(报文交换)和电路交换的工作方式，特别是经历的延迟

为什么要采用层次模型？

计算机网络非常复杂，技术更新迭代快。需要把一个复杂的系统分解成多个可管理、好研究、相对独立的层次。

掌握层次模型的封装和解封装

封装：每一层从高层接收数据(SDU)，然后添加头部信息封装成新的数据单元(PDU)，再把新的数据单元通过服务接口传递给更低层

解封装：每一层从底层接收到数据后，剥离该层协议所添加的头部，同时根据该头部给出的解复用关键字(SAP)将解封装后的数据单元交给更高层

OSI 7层模型，每层大概的功能

由低层到高层——

物理层：如何传输比特
数据链路层：如何在相邻节点间传输帧
网络层：如何在节点间传输（路由）分组
运输层：如何在端系统间发送数据
会话层：如何把分组流联系在一起
表示层：信息表示形式、安全等
应用层：如何实现某种类型的网络应用

Internet的4层模型，与OSI模型的对应

第二章 物理层

传输媒体：了解双绞线、同轴电缆、光纤等导向媒体的基本特性

掌握香农定理和那奎斯特定理的应用

有限带宽为H的无噪声信道：

受噪声干扰的信道：

• 假设分贝值为x db，则信噪比=$10^{x/10}$

信道的最大数据速率应该受到这两者的制约，取两者的最小值

了解波特率和数据速率的关系

$C=Blo{g}_{2}L$

• L为信号可取的离散值的个数（状态数）

掌握NRZ、NRZI、曼彻斯特和差分曼彻斯特编码、4B5B、MLT-3

Clock先低后高

曼彻斯特和差分曼彻斯特编码是Clock分别与NRZ和NRZI异或，NRZ或NRZI为0为Clock，为1则是Clock反转

MLT-3在0时的跳变方向与之前最后的非0位置相反

4B5B编码：4bit转5bit，保证码组的前面没有多于1个“0”，尾部没有多于2个“0”，5bit的码组再用NRZI编码

了解什么是模拟传输和数字传输？放大器和转发器

模拟传输：模拟信号传输的方式，不关心数据信号的内容。放大器会放大噪声信号

数字传输：信道上可以是数字信号也可以是模拟信号，关心数据信号的内容，需要能还原为数字数据。转发器：恢复为数字数据，然后重新生成相应信号传递

掌握数字调制的3种基本方法：频率、幅度、相位，掌握星座图

A sin⁡( 2πft+φ)：幅度A、频率f、相位φ

星座图可表示调制的幅度和相位，有几个点就有几个离散值（L）

了解多路复用技术：FDM、OFDM、TDM、WDM、SDM、CDM

• 频率多路复用: Frequency Division Multiplexing
• 正交频分复用: Orthogonal frequency-division multiplexing
• 波分多路复用: Wavelength Disivion Multiplexing
• 时分多路复用: Time Division Multiplexing
• 码分多路复用: Code Division Multiplexing
• 空分多路复用: Space Division Multiplexing

第三章 数据链路层

帧同步：了解有哪些同步机制，掌握字符填充和比特填充机制

帧同步：帧的起始和结束定位

字符填充：特殊定义的字符SYN(0x7E=01111110)来标识帧的起始和结束位置。但特殊字符可能在数据部分出现：

• 特殊字符有：SYN（0x7E）/DLE（0x7D）
• 发送方： 如果特殊字符(如SYN, 0x7E)在数据部分出现，在其前面添加DLE（0x7D），同时该字符半加0x20（保证其大于等于0x20，即32）：如7E变5E，7D变5D
• 接收方： 看到DLE(0x7D)，去掉DLE，后面的字节半加0x20来恢复原来的数据（逆操作）

比特填充：通过一个特定的比特模式“01111110”来标识帧的起始和结束位置

• 发送时：帧中的其他字段中如果出现连续5个1，则之后插入一个0
• 接收时：如果出现连续5个1后跟一个0，则删除0

差错编码：

什么是随机差错和突发差错

随机差错：即随机热噪声，是信道固有的、持续存在的。码元（比特）的差错是独立的，和前后的码元无关

突发差错：即冲击噪声，外界的因素，持续时间短，突发性，是传输中产生差错的主要原因。差错有关，突发长度：突发差错发生的第一个码元到有错的最后一个码元间所有码元的个数。

了解分组码和卷积码的区别，线性分组码的基本概念

分组码：冗余码元仅仅和当前信息码元（当前一组）相关

卷积码：冗余码元和当前以及最近（多组）的信息码元相关

分组：见上定义

线性：信息码元与监督（冗余）码元之间的关系可以用一组线性方程来表示

掌握CRC

• 比特串与多项式的对应

  有$x^k$项，则k位为1（从0开始）

• 如何进行编码：

  $x^{r}K(x)=G(x)•Q(x)+R(x)$

  G(x)为生成多项式，k为其最高次，将K(x)和R(x)对应的串拼起来

• 如何判断出错？

  用收到的拼起来的串除（二进制）以G(x)，无余数则无措

• 差错多项式：怎么判断漏检

  若差错多项式E(x)能被G(x)整除，则不能检测这样的错误

掌握海明码

• 需要添加多少个冗余位

  $2^r\ge k+r+1$，r为冗余位，k为信息位

• 如何构造监督关系式

  全0表示无错，把监督位为1的异或起来

• 海明距离与检错和纠错能力之间的关系

  海明距离d

  检e个错：d>=e+1

  纠t个错：d>=t+1

了解Internet检验和

头部检验和采用Internet检验和算法

• 16-bit word反码加法求和后取反码
• 检验：反码加法后验证是否为全1
• 途中路由器转发时TTL减1，需要重新计算检验和

例如要发送的 packet 内容是 ：E3 4F 23 96 44 27 99 F3 【00 00】 （checksum 字段清零）

将整个序列看成 16 位的整数，一个十六进制数是 4 bits，所以要看成 4 个十六进制数为一个整数。

• 补码和：E34F + 2396 + 4427 + 99F3 = 1E4FF
• 反码和：进位的数字加到最低位：E4FF + 1 = E500
• 取反：checksum = ~(E500) = 1AFF

则填充 checksum 之后发送的 packet 内容变成：E3 4F 23 96 44 27 99 F3 【1A FF】

接收方检测过程：计算包括 checksum 在内的整个 packet 的反码和，再取反。

• 补码和：E34F + 2396 + 4427 + 99F3 + 1AFF = 1FFFE
• 反码和：进位的数字加到最低位：FFFE + 1 = FFFF

掌握基本的差错控制方法，怎样处理帧的丢失、失序，ACK帧的丢失等

差错控制方式

• 自动请求重发ARQ：接收方检测错误，通知发送方重传；双向信道，发送方缓存发送的数据
• 前向纠错FEC：接收方不仅可以检测错误，而且知道错误的位置；采用纠错码，无需反向信道，无需重发
• 混合纠错HEC：ARQ和FEC结合（误码率较高时采用ARQ，低时采用FEC）

以下两种协议来具体处理帧的丢失、失序，ACK帧的丢失等

停等协议：性能分析方法

如果收到重复的数据帧，也发送ACK（why?可能是之前的ACK丢失导致的重传)

有没有可能出现重复的ACK？

• 有些底层信道传输时可能失序，可能重复
• ACK并没有丢失，虚假超时导致数据帧提早重传，从而发送重复ACK

问题：采用停等协议，数据帧和ACK帧头部的顺序号字段需要多少个比特呢？

• 发送方只有在收到正确的ACK帧之后才会发送新的帧，只要能够区分是新帧还是重传帧即可

• 接收方收到的是新帧或重传帧，发送的ACK可能是新的ACK或重复的ACK

• 顺序号字段只要1个比特即可，采用模2运算，顺序号为0、1、0、1…

信道效率或有效利用率：吞吐率与信道带宽的比率

信道容量B bps；帧长L bit；往返传播延迟2R秒；忽略ACK的开销

滑动窗口协议

• GBN和选择重传有什么区别:确认和重传

  重传：计时器超时时，GBN重传所有分组；选择重传只重传超时的分组

  接收方，GBN只允许顺序接收，接收窗口=1；选择重传则允许失序接收，接收窗口>1

  确认：GBN累加确认；选择重传对每个分组单独确认

• 发送窗口大小与信道有效利用率之间的关系

• 顺序号的比特数与窗口大小的关系

  顺序号m比特

  GBN：接收窗口=1，发送窗口最大为$2^{\mathbf{m}}-1$

  选择重传：一般接收窗口=发送窗口，最大为$2^{\mathbf{m}-1}$

掌握HDLC和PPP协议所采用的帧同步机制（字符填充和比特填充机制）

HDLC：比特填充

异步PPP：字符填充，常用软件实现

同步PPP：比特填充，常用硬件实现

第四章 媒体访问控制

ALOHA协议

• 标准和分槽Aloha协议的吞吐率（信道的最大利用率）的推导方法

  无限用户：

  标准（纯Aloha）在任何时间可发，冲突区为2t

  分槽（k槽） ：冲突区为2k-1，k->无穷，即为标准；k=1即为书中分槽

• G和S的概念（每帧时多少个帧，负载和吞吐率）

• 固定用户吞吐率公式的推导方法

CSMA协议：了解0坚持、1坚持和p坚持的区别

0-坚持：
• 若媒体空闲就（以概率P=1)传输
• 若媒体忙，等待一段随机的延迟时间，再重新监听媒体

1-坚持：
• 若媒体空闲就（以概率P=1)传输
• 若媒体忙则继续监听，直到检测到信道空闲然后立即传输
• 如果有冲突，则等待一段随机的时间后再次监听媒体

P-坚持：
• 若媒体忙，继续监听直到媒体空闲
• 若媒体空闲，以概率P传输，以概率(1-P)延迟一个时间单位（该时间单位通常等于最大的传播
延迟的两倍）后再次监听媒体

以太网：

• 了解以太网的体系结构：LLC、MAC、物理层

逻辑链路控制LLC： 隐藏下层媒体访问控制的细节，为高层提供统一的接口

媒体访问控制MAC：规范对媒体的访问， 提供节点间帧的传输

• LAN地址：48比特的平坦地址空间， OUI+OUA

最低位在前，最低位I/G为0表示单播地址，为1表示组播地址；次低位U/L为0表示全局地址，为1表示本地地址

0101倒过来（1010）即是A，依次类推

• 了解以太网单播、组播和广播地址的区分方法

• IEEE地址格式：最低位（单播或组播）在前

• 了解以太网帧主要包含的字段的含义，为什么以太网有两种帧格式？是否能同时使用这两种帧格式

  不同：2字节的类型（标识该帧递交给哪个高层协议）和2字节的长度（用户数据的长度）

  最小帧长64B，除数据+填充占了18B，故数据不足46B由填充补出

可以同时使用，不会发送冲突，因为DIX的类型字段取值大于1500，不会与802.3的长度冲突。

CSMA/CD机制

载波监听多路访问/冲突检测

帧间间隔IFG的作用

96bit时间，检测到媒体空闲IFG时间后才可传输

why？

网卡在发送模式和接收模式之间转换需要时间，可以让最近传输的节点能够将其收发器硬件从发送模式转向接收模式

掌握冲突检测：最小帧长

帧最小传输时间>=冲突检测时间=2*传播延迟

最小帧长=2*传播延迟*数据传输速率

若在传输中监听到冲突，发出一个至少32比特的jamming信号后停止传输，以便让所有的节点都知道发生了冲突

why 至少32bit？

• 距离较远时信号衰减大，少数比特传播到时可能没有足够的能量让另一个发送者检测到冲突
• 让接收者发现帧的CRC校验码错误，从而丢弃该帧

掌握二进制指数退避算法

i<=10次冲突时，等待的时槽数从0～$2^{i-1}$中随机选出

10<i<16次冲突后，等待的时槽数从0～$1023$中随机选出

i=16次冲突后，节点放弃传输，并报告一个错误

了解千兆以太网的CSMA/CD扩展：载波扩展、帧突发

• 载波扩展：增加帧的最小传输时间，从512比特时间变为4096比特（512字节）时间

• 问题：站点有连续多个短帧发送时，大量的媒体时间被浪费

  解决方式——帧突发：第一帧仍采用载波扩展，在传输完成后并不释放对媒体的访问权，而是准备传输下一个短帧（<=64kb）

掌握CSMA/CD协议的性能分析方法

什么是全双工以太网？与CSMA/CD的区别，了解PAUSE帧所实现的流量控制机制

半双工：一个节点要么传输，要么接收，不能同时做两件事(CSMA/CD)

全双工：节点能同时传输和接收数据(全双工以太网)

全双工以太网不会出现冲突，不再需要采用CSMA/CD协议

以太网媒体选项：了解命名方式，了解冲突域的概念，了解物理层的设备：转发器和集线器

媒体选项的命名策略：<数据速率><信号方式><网段最大长度/媒体描述>

冲突域/访问域：通过集线器连接的网段本质上仍然属于同一个冲突域，采用CSMA/CD规则共享同一个信道的所有节点位于同一个冲突域，在同一个冲突域内，任何两个节点同时传输都会遇到冲突

第五章 网络互连

交换和路由：

了解数据平面和控制平面的不同要求

数据平面负责如何转发分组，要求转发速度尽可能地快

控制平面负责为数据平面的分组转发提供支持，最主要功能是路由，构建转发表，因为节点和网络拓扑结构较稳定，其性能不需要尽可能快

了解虚电路和数据报的基本特性和区别，什么是动态虚电路？

虚电路：源和目的节点之间建立了一条逻辑上的连接，分为连接建立、数据传输和连接释放三个阶段，也称面向连接的方式。连接建立时进行一次路由选择，仍然采用分组交换方式。每个节点需维护一张虚电路表，记录着路由信息（前一个节点和后一个节点的标识）和虚电路号（到上一个节点链路的虚电路号，动态虚电路还包含到下一个节点链路的虚电路号）

全局虚电路：虚电路号在整个网络唯一，需要知道哪些号被使用了，开销大

动态虚电路：虚电路号在链路上唯一。链路双向，新的虚电路号不能使用当前节点和下一节点在链路上使用过的虚电路号

数据报：每个分组的头部包含了源地址和目的地址等字段，节点以此来决定路由，也称无连接方式。不同分组路径可能不相同，可能会出现延迟、失序到达；某个节点缓冲区已满则丢弃分组，分组可能会丢失

逐跳路由和源路由：扩散法和逆向学习法

扩散法： 将收到的分组向除到来链路外的所有其他链路转发

​ 抑制重复分组

• 节点计数器（可设置为网络的直径）：每个收到该分组的节点将该计数器-1，为0则丢弃
• 记录扩散路径：可以记录已经经过的节点列表；也可以记录源节点和顺序号，这样就可以唯一地标识分组
• 选择扩散：不是向其他所有节点转发，而是选择很可能向目的方向去的节点进行转发

逆向学习法：根据本地信息进行路由选择，每个分组记录源节点和节点计数器（每到一个节点+1）。当一个节点从链路L收到一个分组，源节点为S，计数器为n，若以前到S的路径长度大于n，则把链路L作为该节点到S的路由选择，n为到S最短路径长度

网桥：

什么是冲突域和广播域？

集线器下连接的所有端口共享整个带宽，位于同一个冲突域

通过网桥连接的节点位于同一个广播域

冲突域是基于第一层（物理层），广播域是基于第二层（链路层）

掌握网桥是如何工作的

透明网桥：负责处理不同局域网之间帧的转发

基于扩散法和逆向学习法来维护一个转发表，记录节点通过那个端口可达

• 通过收到帧的源地址和端口可知从该端口可达源地址（逆向学习）
• 如果收到帧的目的地址在转发表找不到，就扩散
• 如果目的地址可达端口与到来端口相同，则过滤不转发
• 转发表表项的TTL每秒都增加，超过某个值则从转发表中清除

掌握生成树算法：如何选取根桥，如何确定根端口，如何确定选取端口

如何选取根桥：BID（优先级+MAC地址）最小的网桥

如何确定根端口：当前网桥到根桥最少路径花费使用的端口，多选时取端口号最小的端口，根桥无根端口

如何确定选取端口：当前局域网最靠近根桥的网桥作为选取桥，多选时取BID最小的网桥。选取桥连接到当前局域网的端口作为选取端口，多选时取端口号最小的端口

了解VLAN支持哪3种划分VLAN的方法

基于端口划分

基于MAC地址划分

基于协议划分

了解VLAN帧相比传统的以太网帧有什么不同：优先级+VLAN ID

VLAN帧相比以太网帧多了4个字节，包括2个字节的VLAN协议（0x8100）和2个字节的TCI（3bit优先级，1bitDEI可丢弃指示，剩下的为VLAN ID）

了解局域网交换机支持哪三种帧转发技术？

存储转发：等需转发的帧都到了在发送到目的端口，转发前要进行差错检测，转发延迟较长

直通：收到帧的目的地址字段就开始转发，无差错检测，可能把坏帧也转发，浪费部分带宽，转发延迟小

无残帧：在收到帧的前64字节才开始转发

了解Internet的设计原则：

目标1：连接各种类型的异构网络

目标2：路由器和链路故障仍能通信

目标3：有效利用网络的资源，支持各种类型的应用

掌握什么是命运共享（无状态）、软状态、端到端

（目标2）命运共享：路由器采用无状态的路由设计，不需要为端系统间的分组流维护状态信息

软状态：状态（路由表）的维护通过定期刷新（路由信息交换）完成，一段时间没刷新，状态超时而被移走

端到端：在端系统实现差错控制、流量控制和拥塞控制，在逐跳实现这些功能仅仅优化性能，不能保证正确性

了解IP提供的单播、组播、广播和联播服务的特性

单播：一到一

组播/多播：一到多或者多到多

广播：一到所有

联播/任播：一到多中任意一个

掌握IP分组主要字段的作用，包括TTL/总长度/头部长度/Checksum等

TTL：: IP分组的生命期，经过中间节点转发时：TTL减1，为0时丢弃并发送通知给发送者

总长度：IP分组长度，最长为65535字节（16bit表示）

头部长度：4bit表示，1bit单位为32bit，取值5-15，对应长度20-60字节

Checksum：头部检验和，采用Internet检验和算法

了解IP选项的局限性

地址空间(32比特) 有限，路由表越来越庞大，路由效率低，头部过于复杂而无法快速处理和转发，没有安全性考虑，无法提供QoS保障

掌握分段和重组：分段ID/分段偏移/长度/MF/DF

MF：后面是否还有分段，只有最后一个分段MF=0

DF：为1表示不允许分段，如果必须分段则丢弃该分组并发送一个ICMP差错报告给发送者

IP地址：了解A/B/C和D类地址

掌握子网分配方案，包括变长子网掩码

引入IP子网后，变成了三层结构

如何知道对方用的是两层还是三层？

利用子网掩码（与IP一样长，32bit。用来区分地址中有没有子网号，所以都是一串01字符串来表示；网络号和子网号用1表示，主机号用零表示）

IP地址与子网掩码相与，得出的就是网络地址

变长子网掩码：不同子网可采用不同长度的子网掩码

CIDR：掌握如何进行汇集

路由汇集：把多个连续的地址块汇集成一个大的地址块，缩小了路由表的规模

转发表中可能会有多个表项匹配，需要采取最长前缀匹配原则：网络掩码最长的匹配

IP转发： 掌握IP转发的基本过程，掌握如何进行最长前缀匹配。了解Trie

转发过程：接收分组，查找转发表将分组转发到相应的外出接口

转发表：根据路由表来确定，一般包含目的网络/网络掩码/下一跳/网络接口

收到IP分组后如何匹配转发表中的表项？

​ 目的IP地址&网络掩码 == 目的网络&网络掩码 ？多选则进行最长前缀匹配

采用一个称为Trie的前缀树的数据结构进行最长前缀匹配

掌握ARP的基本操作过程

地址解析协议ARP：用于以太网等广播网络中，将IP地址映射为MAC地址

当主机A要与主机B通信时，ARP可以将主机B的IP地址（192.168.1.2）解析成主机B的MAC地址，以下为工作流程：
第1步：根据主机A上的 ARP缓存内容，IP确定用于访问主机B的转发IP地址是192.168.1.2。然后A主机在自己的本地ARP缓存中检查主机B的匹配MAC地址。
第2步：如果主机A在ARP缓存中没有找到映射，它将询问192.168.1.2的硬件地址，从而将ARP请求帧广播到本地网络上的所有主机。源主机A的IP地址和MAC地址都包括在ARP请求中。本地网络上的每台主机都接收到ARP请求并且检查是否与自己的IP地址匹配。如果主机发现请求的IP地址与自己的IP地址不匹配，它将丢弃ARP请求。
第3步：主机B确定ARP请求中的IP地址与自己的IP地址匹配，则将主机A的IP地址和MAC地址 映射添加到本地ARP缓存中。
第4步：主机B将包含其MAC地址的ARP回复消息直接发送回主机A。
第5步：当主机A收到从主机B发来的ARP回复消息时，会用主机B的IP和MAC地址映射更新ARP缓存。本机缓存是有生存期的，生存期结束后，将再次重复上面的过程。主机B的MAC地址一旦确定，主机A就能向主机B发送IP通信了。

了解什么是gratutious ARP

无故ARP：发送一个要求解析自己IP地址的ARP请求，可检查此IP地址是否已经使用，也可让其他节点更新发送者的MAC地址

掌握ARP伪装攻击

A要和B通信，攻击者C伪造一个ARP响应，单播发送给被攻击者（B和A），A和B都认为对方的MAC地址是C的MAC地址，这样A、B之间的IP分组都会先发给C，C便可篡改其中的数据再进行转发，进行中间人攻击。

ICMP：了解ICMP差错报告：哪些IP分组会发送差错报告，差错报告包含哪些信息

哪些IP分组会发送差错报告：TTL超时，目的不可达，不能分段等

差错报告包含哪些信息：原IP分组头部+数据部分的前8字节

掌握Ping/traceroute/path MTU Discovery如何实现？

ping：测试主机到目的地之间是否可达且正常运行。源端发送ICMP Echol请求给目的地，目的地收到后发送ICMP Echol响应给源，这便知道是否可达。ping还可用于测试RTT、测试丢包情况，-R选项可以记录途中经过的路由器，但最多9个路由器

traceroute：记录俩台主机之间经过的路由器。利用TTL超时ICMP消息，逐步扩大TTL，便能返回不同经过的路由器信息

path MTU Discovery：路径MTU发现，通过ICMP协议探测途中允许的MTU的下界，以后发送的IP分组都不超过该 MTU。先发送一个足够大（MTU）的IP分组（DF=1，不允许分段），途中路由器一旦发现一个链路的MTU更小便会发送ICMP分段差错报告给发送者，发送者更新MTU再发送，直至没有差错报告。

掌握DHCP的基本工作过程，主要是DHCPDISCOVER/OFFER/REQUEST/ACK的作用

发现阶段

DHCP客户端通过发送DHCP-DISCOVER报文来寻找DHCP服务器

提供阶段

网络中接收到DHCP-DISCOVER报文的DHCP服务器，会选择一个合适的IP地址，连同IP地址租约期限和其他配置信息（如网关地址，域名服务器地址等）一同通过DHCP-OFFER报文发送给DHCP客户端。

选择阶段

如果有多台DHCP服务器向DHCP客户端回应DHCP-OFFER报文，则DHCP客户端只接受第一个收到的DHCP-OFFER报文，然后以广播方式发送DHCP-REQUEST请求报文，该报文中包含Option 54（服务器标识选项），即它选择的DHCP服务器的IP地址信息

确认阶段

收到DHCP客户端发送的DHCP-REQUEST请求报文后，DHCP服务器根据DHCP-REQUEST报文中携带的MAC地址来查找有没有相应的租约记录。如果有，则发送DHCP-ACK报文作为应答，通知DHCP客户端可以使用分配的IP地址；否则，发送DHCP-NAK报文作为应答，通知DHCP客户端无法分配合适IP地址。DHCP客户端需要重新发送DHCP-DISCOVER报文来请求新的IP地址。

DHCP客户端收到DHCP服务器返回的DHCP-ACK确认报文后，会以广播的方式发送免费ARP报文，探测是否有主机使用服务器分配的IP地址，如果在规定的时间内没有收到回应，客户端才使用此地址。否则，客户端会发送DHCP-DECLINE报文给DHCP服务器，通知DHCP服务器该地址不可用，并重新申请IP地址。

了解DHCP Relay

用DHCP Relay代理可以去掉在每个物理的网段都要有DHCP服务器的必要，它可以传递信息到不在同一个物理子网的DHCP服务器，也可以将服务器的消息传回给不在同一个物理子网的DHCP客户机

掌握NAT和NAPT的工作原理

NAT：负责在内部网络用到的内部IP地址与外部用于连接到Internet的公共IP地址（从地址池中选择）之间进行地址转换

• 从内部网络到外部网络：转换源地址

• 从外部网络到内部网络： 转换目的地址

NAPT：基于端口的NAT

• 从内部网络到外部网络：转换源地址+端口号

• 从外部网络到内部网络： 转换目的地址+端口号

掌握IP隧道的基本思想

IP隧道指采用IP协议的网络上的任意两个节点之间建立的一条虚拟链路，通过这些虚拟链路连接的节点构成了一个覆盖网

了解GRE封装方式

通用封装协议（版本号为1）：为任何网络层协议之上传输任何协议的分组提供封装支持；用于IP网络时，IP分组头部协议字段为0x47表示GRE分组

了解自治系统的概念，自治系统间和自治系统内部路由的区别

自治系统：由一个或者多个独立的管理实体控制的采用相同路由策略的网络和路由器组成

自治系统内部路由策略相同，不同自治系统之间路由策略可能各不相同。自治系统内部选择各自的内部路由协议（IGP），自治系统之间运行外部路由协议（EGP）

掌握Dijkstra算法

基于最优原理：如果节点A到节点B的最优路由经过了节点C (A->C->B)，则该路由上的A到C和C到B分别也是节点A和节点C、节点C和节点B的最优路由

掌握链路状态路由算法的基本步骤

dijkstra算法计算最短路由，链路状态路由算法则是通过扩散让每个路由器都知道网络的的全局信息

了解什么是链路状态分组LSP，了解为什么要进行以及如何进行可靠地扩散

LSP：每个路由器周围的链路情况，需要传播给所有路由器

why？

因为不能利用路由器的路由表来将LSP发送给每个节点，否则就会LSP依赖于路由表，路由表又依赖于LSP，产生递归问题，故要采用扩散法

how？

LSP中有路由器ID，再引入顺序号和年龄字段，来解决重复分组和路由器崩溃后新的LSP顺序号小于旧的LSP的问题。具体包含顺序号重复使用（回环），age以合适的速度减小，为0超时，丢弃。

OSPF：

掌握点到点链路、广播链路如何转换为LSA

LSA：链路状态通告，路由器周围的链路状况，路由器ID+顺序号+age + 链路信息，可看作是改进的LSP

点到点链路：路由器LSA（第1类 LSA）描述路由器周围情况。对于当前路由器的链路情况，即是这一条链路与其另一端路由器（邻居）的信息

广播链路：网络LSA（第2类 LSA）描述广播网络的链路状况。连接在广播链路上的路由器互为邻居。

掌握广播链路上为什么需要选取路由器，选取路由器的基本功能

why？

如果邻居之间互相扩散LSA，链路上会出现$O(n^2)$个相同的LSA

基本功能：引入邻接关系，只有选取路由器DR和备份选取路由器BDR（DR故障时启用）与广播链路上的其他路由器有邻接关系。LSA只在邻接关系的节点之间传递，故普通的节点要先传给DR，再又DR传给其他节点。DR还负责扩散网络LSA

掌握区域的概念

把许多网络和主机以及连接在这些网络上的路由器，合起来称为一个区域

了解5种LSA的作用

第3类LSA：汇集LSA，由ABR产生，描述ABR可以到达哪个网络，到该网络的花费是多少

第4类 LSA：ASBR汇集LSA，描述ABR到哪个ASBR的花费是多少

第5类LSA：AS外部LSA，说明ASBR连接到哪个(汇集后的)网络，花费是多少

掌握各种LSA的构造和扩散范围

路由器LSA和网络LSA会在其所在的区域中扩散

汇集LSA由ABR生成扩散到主干区域，再经过其他区域的ABR扩散到其他本地区域

AS外部LSA由ASBR生成扩散到其所在的区域，再经由ABR扩散到主干和其他本地区域

ASBR汇集LSA由其所在区域的ABR生成，扩散到主干区域，再扩散到其他本地区域

掌握距离向量路由协议的基本工作过程，无穷计数问题

思路：A到B的最短路径，等于min{A到A的邻居的路径+A的邻居到B的最短路径}

无穷计数问题：坏消息的传播非常缓慢，假设BD链路断开时，距离缓慢增加，直到最后为无穷大，才知道不可达。坏消息意味着原来的最短路径不可用，可是新老信息混合在一起，之前的老信息仍然在传播，导致了路由回路的出现

掌握水平分割以及反向抑制的水平分割

产生环路的一种情况是：路由器A将从路由器B学习到的路由信息又告诉给了路由器B。水平分割的思想就是：在路由信息传送过程中，不再把路由信息发送到接收到此路由信息的接口上。从而在一定程度上避免了环路的产生。

带反向抑制的水平分割：给邻居路由器发送路由信息时将那些从该邻居了解到的路由信息的距离设为无穷大

了解RIP，了解RIP-1和RIP-2的区别

RIP：距离向量路由协议

了解任意源组播服务模型和单一源组播服务

任意源组播ASM服务模型

• 发送者没有限制，可不属于组播组
• 接收者属于同一个组播组，通过组播地址标识
• 组播组可任意规模，接收者可在Internet上任何地
  方，动态加入或退出
• 组播路由器间维护一个组播分发树，组播分组沿
  着该分发树发送

单一源组播SSM模型:

• 只有一个发送者
• 一个组播会话通过<source, group>标识，避免了
  原ASM模型中组播地址分配的问题
• 组播路由维护一个基于源的分发树，更加简单和
  高效

如果要限制接收分组的成员(提供付费服务）

• 对于内容加密
• 不采用组播

掌握IGMPv2协议的基本工作方式：软状态、反馈抑制和离开组播组

软状态机制：定期发送Query以刷新状态；超时时移走状态信息

反馈抑制：Query包含最大响应时间，主机选择[0,Max Resp. Time]时刻准备发送Report

离开组播组：可悄悄离开，但会浪费带宽

掌握IPv6相比IPv4的改进，分组格式之间的变化

更大的地址空间（128bit）、更加有效的路由、更简化的头部格式、更加安全等等

IPv4要求MTU最少为576字节，IPv6要求MTU最少为1280字节

掌握128比特的地址空间，如何压缩IPv6地址

分为8组，每组以十六进制书写，组与组之间用冒号分割。每组中前面的0可以移走，连续的为全0的组可以省略，但仅仅缩写一次

了解IPv6的过渡方法（可以和IP隧道的概念结合起来）

• 双协议栈：同时运行IPv4和IPv6协议栈

• 协议转换：类似于NAT，负责分组格式转换

• 隧道

第六章 端到端的运输协议

掌握TCP主要字段的作用：顺序号和确认号，窗口大小，SYN/FIN/ACK等

SYN：同步顺序号，建立TCP连接

FIN：无数据发送，连接释放

掌握TCP的基本特性，提供面向字节流的双向可靠数据传输服务

掌握MTU、MSS的概念

链路层帧携带的用户数据部分最长为1500字节（MTU=1500字节）

最大分段大小MSS: TCP段中用户数据的最大长度，以太网上的MSS <= 1500 - 20 - 20 = 1460字节（MTU-IP头部-TCP头部）

掌握三次握手的连接建立过程

第一次握手：建立连接时,客户端发送SYN包(seq=x)到服务器,并进入SYN_SEND状态,等待服务器确认；
第二次握手：服务器收到SYN包,必须进行确认，同时自己也发送一个SYN包,即SYN+ACK包（ack=x+1，seq=y）,此时服务器进入SYN_RECV状态；
第三次握手：客户端收到服务器的SYN＋ACK包,向服务器发送确认包ACK(seq=x+1，ack=y+1),此包发送完毕,客户端和服务器进入ESTAB状态,完成三次握手

了解连接释放过程

四次握手

掌握什么是TIME-WAIT状态

TCP 连接中，主动关闭连接的一方出现的状态

TCP流量控制：可变窗口的滑动窗口协议，掌握收到DATA和ACK之后窗口的变化情况

rwnd

TCP拥塞控制：

掌握慢启动、拥塞避免、快速重传和快速恢复

超时则慢开始

掌握TCP吞吐率模型的分析方法

掌握重传计时器：要考虑哪些方面的要素：基于RTT和标准偏差的估计（不需要记忆各个权重是多少），重传TCP段的超时如何处理？

基于RTT：EstimatedRTT=(1-$a$)EstimatedRTT+$a$SampleRTT（EstimatedRTT估计值，SampleRTT采样当前值）

基于标准差：Deviation=(1-$\beta$)Deviation+$\beta$|SampleRTT-EstimatedRTT|（Deviation初始值为SampleRTT/2）

RTO（Timeout）=EstimatedRTT+4*Deviation

超时则回到慢启动

特殊环境下的TCP：了解在高速网络环境（长肥网络Long Fat Networks)下最初的TCP协议有哪些问题。

需要很长时间cwnd才能达到网络的容量

了解UDP协议的特性。了解检验和字段为可选的。

无连接、不可靠

第七章 网络应用

DNS

掌握如何维护域名树：NS资源记录、域名和区域的概念

整棵域名树采用分布式方式管理，首先将整棵树下的第一层子树分割交给不同的 (TLD)DNS服务器管理，TLD域名服务器可将其管理的子树进一步分割并授权给更下一层的域名服务器管理

子树的某些分支授权给其他域名服务器管理，通过NS资源记录来定义

域名：由一串字符组成，指向某一个IP地址

域名服务器管理的基本单位为区域（修剪的子树）

掌握常用的资源纪录：NS/A/AAAA，CNAME和MX

掌握域名解析过程：递归和迭代查找过程以及缓冲

递归：发送请求给下一个服务器，对方给出解析结果

迭代：发送请求给下一个服务器，对方给出一个可能知道答案的域名服务器

缓存：DNS客户、途中的DNS服务器都会将解析结果缓存，收到新的请求在缓存查找时采用最长后缀匹配。缓存有一定的生存时间TTL。成功的DNS响应被缓存，DNS响应报告不存在该域名时也可以缓存

了解DNS消息的传递方式（TCP和UDP）

区域传输一般采用TCP，DNS查询一般采用UDP

FTP：掌握控制连接和数据连接的概念

控制连接用于在两个主机之间传输控制信息，如用户认证，列目录，下载和上传文件等，使用端口21。数据连接用于实际传输一个文件，使用端口20。

了解主动和被动模式数据传输

电子邮件：邮件地址：user@domain

了解发送电子邮件时怎样与DNS结合

通常来说，电子邮件(email)地址的写法为:user@domain。当你发出一封电子邮件时，首先，你的邮件服务器会向DNS服务器查找server.name这个主机名对应的IP地址与MX记录，然后这封信会先送到优先级最高的MX服务器上，如果没有找到MX记录，则送到优先级次高的服务器，以此类推，信件最终会送达用户邮箱。在邮件到达之后，该主机则根据@地址符号前面的帐户名将信件传送到各用户的邮件目录下。

掌握SMTP协议的主要命令

了解POP3协议的基本工作方式，了解POP3和IMAP的区别

认证阶段、事务阶段、更新阶段

当客户机与服务器建立连接时，客户机向服务器发送自己身份并由服务器成功确认，即客户端由认证阶段转入事务阶段，在完成列出未读邮件等相应的操作后客户端发出quit命令，退出事务阶段进入更新阶段，开始下载未阅读过的邮件到计算机本地之后最后重返认证状态确认身份后断开与服务器的连接。

POP3和IMAP的区别：

• 二者功能不同：POP3允许用户从服务器上把邮件存储到本地主机（即自己的计算机）上,同时删除保存在邮件服务器上的邮件，而SMTP服务器则是遵循POP3协议的接收邮件服务器，用来接收电子邮件的。

• 二者客户端操作的反馈不同：POP3协议允许电子邮件客户端下载服务器上的邮件，但是在客户端的操作（如移动邮件、标记已读等），不会反馈到服务器上。而IMAP提供webmail与电子邮件客户端之间的双向通信，客户端的操作都会反馈到服务器上，对邮件进行的操作，服务器上的邮件也会做相应的动作。

• 二者服务不同：IPOP3提供了方便的邮件下载服务，让用户能进行离线阅读。IMAP提供的摘要浏览功能可以让在阅读完所有的邮件到达时间、主题、发件人、大小等信息后才作出是否下载的决定。

了解RFC 822邮件格式，了解主要的邮件头部，包括FROM,TO/CC等

From：邮件的源

To：邮件的接收者，可以多个，之间以逗号隔开

Cc：邮件的(抄送)接收者，可以多个

MIME: 了解Content-Transfer-Encoding，掌握quoted-printable和Base64编码方法

Content-Transfer-Encoding设计的目的：在有效地传输巨大的二进制数据和便于阅读的编码数据之间要有一个折中

了解Web体系结构

掌握HTTP的无状态特征

HTTP服务器并不维护之前收到的HTTP请求的状态，简化了服务器的设计，容易支持大量并发的HTTP请求。但提供cookie机制来传递状态信息

掌握非持续连接和持续连接，持续连接的非流水线和流水线方式

非持续连接：响应时间（一次）= 2RTT+传输时间。如果一个HTML页面包含了N个同一服务器上的其他 Web对象，假设这些对象都可容纳在一个TCP段中（忽略TCP的拥塞控制），则要建立N+1条连接（一个页面+N个其他对象），响应时间= 2(N+1)RTT+传输时间

持续连接（非流水线）：一次连接，后面只需要请求（相当于后面每个都少了RTT），还是上面的例子，相当于少了N*RTT，响应时间= (N+2)RTT+传输时间

持续连接（非流水线）：一次连接和请求，后面的立即跟着发就行，也相当于非流水线的N取1，响应时间= 3RTT+传输时间

掌握HTTP请求和响应的基本格式，了解Host头部的意义，给出一个HTTP请求和响应，可以了解到该请求和响应所执行的动作

请求：请求行、头部行、实体主体

响应：状态行、头部行、实体主体

引入虚拟主机，即一台主机可提供多个Web站点，通过Host头部描述是哪个Web站点

简答题

考试真题

1、简答题（15%）

1. 在分组交换网络中，延迟是一个主要的性能度量指标，请问有哪四种不同类型的延迟？
2. Ethernet 标准规定一个帧的长度最大不能超过 1518 个字节，并且长度最小不能小于 64个字节，请说明为什么对帧的长度限制其最大值和最小值？
3. SMTP 协议在通过 DATA 命令发送电子邮件时，是怎么标识该邮件的结束的？HTTP 可以采用类似的方法吗？请说明理由。
4. 如果网络的拓扑有回路，请问IP分组会不会一直在网络中循环转发？
5. 在OSPF路由协议中，对于一个广播链路，会通过hello协议选取一个选取路由器，请简单描述选取路由器的功能。

2、物理层(6%)
下图给出了一个信道上监测到的信号波形，如果信道编码方式为曼彻斯特编码，发送者所发送的比特串是什么？如果信道编码为差分曼彻斯特编码，初始为高电平，请问发送者所发送的比特串是什么？

3、数据链路层（18%）

1. 考虑 CRC 差错编码，生成多项式G(x) = $x^3+x^2+1$。（10%）
   (a) 现在要传输数据 D= 1101 1010 1000，经过 CRC 编码后实际传输的比特串是什么？
   (b) 步骤(a)计算出来的比特串在传输过程中出现的许多差错可以通过 CRC 检测出来，但是有些 6 比特突发差错（即长度为 6 的突发差错）会被漏检，请给出接收方接收到的比特串出现了 6 比特的突发差错但是被漏检的一个例子。

2. 考虑一个数据速率为 40Mbps 的点到点链路，距离为 200 千米，信号传播速度为 2x108米/秒。数据帧长度为 1000 字节，不采用捎带确认，接收者在收到数据帧之后发送确认帧的处理时间为 20 微秒，确认帧长度为 100 字节，发送者总是有数据要发送。请问如果采用选择重传（发送窗口等于接收窗口）滑动窗口协议，为了获得至少 60%的信道利用率：（8%）
   a. 发送窗口最小为多少个帧？
   b. 顺序号字段至少为多少个比特？

4、媒体访问控制（6%）
假设有 2N 个节点采用分槽 ALOHA 来共享无线媒体，这 2N 个节点进一步被分为两组，每组各 N 个节点。第一组中的每个节点在每个时槽以概率 p 传输，第二组的每个节点在每个时槽以概率 2p 传输。假设 p<0.5，并且每个节点都总是有数据要传输。请问系统的吞吐率（即每个时槽成功传输的平均分组数）是多少？

5、生成树算法 (10%)
下图给出了一个有 5 个端口的网桥，其桥 ID 为 45，运行生成树算法，端口号以及每个端口的花费在图中标出，该网桥通过每个端口收到如图所示的 5 个 BPDU 消息，其中 BPDU消息(R. C. B. P) 表示 R 为根桥，C 为根路径花费，B 为发送该 BPDU 消息的网桥 ID，P 为端口号。
请给出网桥 45 的每个端口的角色（是根端口、选取端口还是阻塞端口?）。接下来网桥 45 从端口 1、端口 2 和端口 3 各收到一个广播帧 A、B 和 C，请问网桥 45 怎么处理这 3个广播帧？

6、网络层(17%)

1. 一个 TCP 段携带了 2048 字节的用户数据，该 TCP 段交给主机 A 的 IP 模块发送，途中通过路由器 R 转发，最后发送给目的主机 B，如下图所示。第 1 条链路的 MTU 为 1024 字节，第 2 条链路的 MTU 为 512 字节。假设不使用 IP 选项和 TCP 选项，如果有可能，总是发送尽可能大的 IP 分段。请给出在目的主机 B 收到的 IP 分段的情况，请给出每个 IP 分段的分段偏移、总长度和 More 标志的情况。(9%)
   
2. 下面给出了一个路由器的路由表的一部分，尽最大可能将这些路由表项汇集，使得汇集后的路由表与之前的路由表等价（即正好包含了原来的路由表项给出的那些地址）且路由表项最少。(8%)
   
   7、路由协议(9%)
   考虑如下图所示的网络，采用带反向抑制的水平分割的距离向量路由协议。假设：
   • 链路为双向链路，并且两个方向的花费相同。
   • 如果一个节点发现有多个邻居都可以作为到某个目的地的下一跳路由器，节点选择 ID最小的邻居（A<B<C<D）。
   • 节点之间每隔 1 秒交换路由表，并且假设路由信息的交换完全同步，而且忽略传输延迟。也就是说，在每个时刻 i，其中 i=1,2,3…，每个节点发送自己的路由表，然后接收邻居节点的路由表，并且在 i+0.1 时刻完成路由表的更新。
   • 在时刻 0.1，假设路由表为稳定状态，各个链路的花费如图所示。在时刻 0.5，A 和 B 之间的链路花费从 1 变为 200。除此之外链路花费不再改变。注意每个节点会记录上一轮所收到的距离向量。
   • 不采用触发更新
   请把下面的距离表填写完整（你并不一定需要表格中的所有行），该表格给出了不同时刻 0.1、0.5、1.1、2.1, … （直到确认系统处于稳定状态为止）在节点 A、B 和 C 中对于目的地 D 的路由表项（即到目的地 D 的距离）的变化过程。
   
   8、TCP(11%)
   下图给出了一个采用 TCP Reno 拥塞控制机制的 TCP 连接的拥塞窗口的变化情况。横坐标表示时刻，以往返延迟 RTT（固定大小）为单位。纵坐标表示拥塞窗口，以一个携带 MSS 用户数据的 TCP 段为单位。为了简便起见，图中忽略了快速恢复阶段。假设发送者发送的所有TCP 段都携带了 MSS 用户数据。请问：
   a) B 和 D 分别对应什么事件？在该事件发生后，拥塞窗口(cwnd)和慢启动阈值(ssthresh)分别是多少？
   b) 考虑从 E 到 F 之间的这段时间，请问该时间段的平均吞吐率是多少？
   c) 考虑从 F 到 G 之间的快速恢复阶段（图中并没有绘出），请问在这个阶段，拥塞窗口最大可以达到多少？
   
   9、DNS(8%)
   下面给出了 3 个域名服务器的当前了解到的资源记录：
   

a. 假设一个 client 设置本地域名服务器为 202.120.224.26，client 采用递归查询方式，本地域名服务器为 client 提供递归解析服务，而本地域名服务器自身采用迭代查询方式。现在要解析 www.google.com 的 IP 地址，请给出域名解析过程。
b. client 在进行 a 的域名解析后的 11 分钟时刻再次查找 www.google.com 的 IP 地址，请给出域名解析过程。