计算机网络-笔记

October 6, 2020 · 51 min read

Ferdinand Su

Prospective doctoral student @ HIT-ICES, C# developer.

概述

计算机网络

互联，自治设备的集合
功能组成上分为通信子网和资源子网
评价指标包括带宽和时延
协议定义两个对象之间交换报文格式及其响应
协议的三要素包括语法，语义和同步
从结构上划分为网络边缘，网络核心和接入网

功能

数据通信：最基本最重要的功能
资源共享
分布式处理
提高可靠性
负载均衡

参考模型

协议，服务和接口是关键。传输层(含)之上的称为端到端层。

OSI

应用层：用户与网络的界面
表示层：数据压缩、加密解密、数据交换
会话层：建立、管理和终止会话，完成同步
运输层：进程通信，可靠数据传输、流量控制、差错控制、服务质量、数据传输管理
网络层：传输数据报，实现流量控制、拥塞控制、差错控制和网际互连
链路层：组帧，差错检测、流量控制和传输管理
物理层：透明传输比特流

TCP/IP协议栈

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

应用层

原理

体系结构

C/S体系结构：一个长期在线的服务器和若干客户端
P2P：间断连接的主机之间直接通信
混合式

进程通信

网络中标识一个应用进程的信息包括端口号和IP地址。
TCP提供可靠的数据传输，无差错、有序，同时有阻塞控制机制
UDP是轻量级服务，提供不可靠的数据传输，不保证顺序和到达

HTTP

WebPage由对象组成，对象包括各种文件(html, jpg, etc.)

HTTP基于TCP，无状态记录。HTTP默认使用持续连接，但也可使用非持续连接。

对于非持续连接，每个TCP连接只传输一个对象就关闭，每个连接用时2个RTT+对象传输时间(RTT：往返时间，即一次客户与服务器通信所需的时间, 一个RTT用于前两次握手，第二个用于请求)。

HTTP1.1采用持续连接，如果采用流水线，甚至可以不等待响应就发送请求。

cookie使得HTTP拥有了身份识别等功能。

电子邮件

常用协议SMTP：

只支持7位ASCII码(可通过MIME来传输二进制内容)
一般不使用中间邮件服务器
使用只包含'.'(CRLF.CRLF)的行来表示邮件内容结束
端口25

另有POP3，IMAP，基于TCP；POP协议不加密。

DNS

基于UDP，端口53
负责主机名到IP，主机别名、邮件服务器别名到主机名的转换
DNS还可实现负载分配
分布式、分层存储

DNS查询路径

根DNS服务器：提供顶级域名服务器的地址
顶级域(com, org, edu, cn, etc.)都有对应的TLD顶级域服务器，其提供权威DNS服务器的IP
权威DNS服务器提供每个组织机构的所有主机名
本地DNS服务器：代理本地机器，进行查询

查询方式

递归查询：DNS客户端和本地DNS服务器之间，DNS客户端直接获得结果的过程
迭代查询：本地DNS服务器和其它服务器间，依次查询各级服务器地址的过程

DNS资源记录(RR)

RR=(Name, Value, Type, TTL)

Type取值及含义：

A 主机名到IP的映射
NS 域到权威服务器名称的映射
CNAME 别名到规范主机名的映射
MX 邮件服务器别名到规范主机名的映射

DNS报文格式

前12字节是首部，包含标识符，标志（问/答、以及查询方式等）,以及后面几个段的大小
问题，包含查询的名称和类型
回答，响应查询的RR
权威，权威服务器的记录
附加信息

P2P文件分发

D_{cs}\ge max\left\{\frac{NF}{u_s},\frac{F}{d_{min}}\right\}\\ D_{P2P}\ge max\left\{\frac{F}{u_s},\frac{F}{d_{min}},\frac{NF}{u_s+\sum_{i=1}^Nu_i}\right\}

BitTorrent中所有对等方的集合称为一个洪流，互相下载文件块，下载顺序采用最稀缺优先技术。

FTP

两条TCP连接
控制连接21，数据连接20
跨平台，允许指明文件格式、权限和类型
控制信息全部使用7位ASCII，带外传送；控制连接始终联通。
匿名ftp可使用anonymous用户

Telnet

TCP-23

传输层

主机才会有
进程间的逻辑通信
复用和分用
差错检测

多路复用和多路分解

不同端口->主机间的IP连接->不同端口

UDP

无连接
面向报文，每次发送完整的一个报文
不保证可靠交付
无拥塞控制，适合实时应用

UDP报文结构

头部4*2字节

2字节源端口号
2字节目的端口号
2字节长度(总长度)
2字节校验和(包含了伪首部：源IP，目的IP，协议号，全0一字节，UDP长度2字节)

UDP检验和

先对所有16-bit字进行求和，反码加法-溢出的1回卷(加到最低位)，然后取反码，称为UDP校验和。接收方将所有16-bit字进行求和并加上校验和，若获得0xFFFF则说明大概无差错

校验和并非必须。如果不使用校验和，则将该字段置0.如果校验和结果为0，则将此字段置全1.

TCP

面向连接
点对点
可靠有序，不丢不重
全双工(双缓存)
面向字节流

TCP首部

20B固定首部：

2B源端口，2B目的端口
4B序号(本报文第一个字节的序号)
4B确认号(期望收到下一个报文的第一个字节序号)
1B数据偏移(TCP首部长度)，单位4B
6位控制位：
- URG紧急位，配合紧急指针使用；无需排队
- ACK确认位；确认号有效。
- *PSH推送位；接收方尽快交付数据至应用进程
- *RST复位；连接中出现严重差错，必须释放连接再重新建立
- SYN同步位；标识连接请求/接受报文
- FIN终止位：发送方数据发送完毕，请求释放连接
2字节当前发送方的接收窗口大小
2字节检验和，和UDP相似(仅协议不同)
2字节紧急指针，指出紧急数据的字节数

还可包含长度可变的选项；总长度4B对齐。

TCP连接管理

C/S模式
连接
1. 客户端发送连接请求(SYN=1,seq=x)
2. 服务端发送连接请求确认(SYN=1,ACK=1,seq=y,ack=x+1), 同时分配缓存和变量
3. 客户端分配缓存和变量，发送确认(SYN=0,ACK=1,seq=x+1,ack=y+1)，可携带数据
- 洪泛式攻击
断开
- 双方均可发起断开，设发起方为客户端
1. 客户端发送连接释放报文段(FIN=1,seq=u)
2. 服务端回送确认(ACK=1,seq=v,ack=u+1)，客户到服务器的连接释放(半关闭)
3. 服务端发送释放报文段(FIN=1,ACK=1,seq=w,ack=u+1)
4. 客户端回送确认(ACK=1,seq=u+1,ack=w+1)，等待计时器结束后彻底关闭连接

TCP可靠数据传输

保证双方字节流完全一致
累积确认
超时重传
自适应算法计算超时时间
快速重传：三个冗余ACK直接重传

TCP流量控制

基于滑动窗口
接收方根据接收缓存大小，通知发送方
rwnd=0则不允许发送方继续发送新数据，但是可以重传旧的。
当收到0通知窗口时，持续计时器启动。计时器到期时，发送零窗口探测报文段；如果仍收到0，则重新设置持续计时器。

TCP拥塞控制

全局性问题，针对堵塞

慢开始&拥塞避免

默认cwnd=1
慢开始：在小于拥塞阈值时，指数增长
拥塞避免：在大于等于拥塞阈值时，一次增加一个MSS
当网络拥塞(超时)时，立即修改窗口为cwnd=1；然后新的拥塞阈值是刚才拥塞发生时窗口的值的一半

快重传&快恢复

收到了三个ACK时，执行快重传算法
快重传将cwnd调为新的拥塞阈值(刚才窗口的值的一半)
如此可以避免超时导致的慢开始，因此称为快恢复

题型

求某网络的最大cwnd尺寸(按段长度记录) $\frac{CWND_{max}*MSS}{链路带宽}=Rtt$
总是在拥塞避免阶段，求平均CWND和平均吞吐量 $CWND_{avg}=\frac{3}{4}CWND_{max}$ , $平均吞吐量=\frac{CWND_{avg}*MSS}{Rtt}$
窗口恢复时间 $t_{recover}=\frac{CWND_{max}}{2}*Rtt$
求估计RTT $新估计RTT=(1-\alpha)\times旧RTT+\alpha\times新RTT样本$
信道效率： $信道效率=吞吐率/信道带宽$

网络层

网络层概述

网络层实际上有多种协议：IPv4和IPv6。

网络层功能

路由选择与分组转发
异构网络互联
拥塞控制

数据交换

电路交换

如：电话网络。

独占资源，使用效率低
延迟小，实时性强
无冲突，有序传输
灵活性差，无差错控制

报文交换

完整的报文被一次性从一个节点发送到下一处节点。未传输完成前，信息不会继续向下流动。

储存-转发是分组交换和报文交换的基本工作方式。

无需建立连接
动态分配线路
线路可靠性和利用性高
多目标服务
报文大小不稳定
有存储转发时延

分组交换

完整的报文被分组地进行报文交换。具有更高的效率，但是可能会导致额外的排队开销时延和丢包(排队缓冲区溢出)。

d_{端到端}=N\frac{L}{R}

其中N为路径数，即节点数(含始末)-1；L为分组大小，R为传输速率

无需建立连接
动态分配线路
线路可靠性和利用性高
储存管理更容易
有存储转发时延
额外传输的信息量
乱序到达时，需要重新排序

数据报与虚电路

都属于分组交换
虚电路提供连接服务
- 分组只携带虚电路编号
- 所有结点都维护相关信息
- 可永久可临时
数据报提供无连接服务
- 每个分组携带源和目的地址
- 路由器根据目的地址进行转发

路由算法

静态/非自适应算法

简便可靠
变化不大的网络中运行效果好
路由更新慢，不适合大型网络

动态/自适应算法

路由器之间交换信息
更新快，适合大型网络
算法复杂，增加网络负担

路由选择协议 \begin{cases} 内部网关协议IGP(AS内使用) \begin{cases} RIP\\ OSPF \end{cases}\\ 外部网关协议EGP(AS间使用) ：BGP \end{cases}

RIP协议/距离向量算法

适用于小网络
每个路由器维护到每一个目的网络的唯一最佳距离(跳数)记录
最多包含15个路由器
距离16表示不可达
仅和相邻的路由器交换自己的路由表
30s交换一次信息，然后根据信息更新路由表；如果超过180s没有收到邻居通告，则认为邻居丢失(更新路由表)
若干次更新后，路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由地址(收敛)
应用层协议，基于UDP
慢收敛，坏消息传得慢，断开的网络不能立刻被所有路由器得知

修改邻居路由器发来的所有表项
1. 下一跳地址改为来源邻居
2. 距离+1
合并本地路由表和收到表项的数据; 对每一项：
1. 如果表中无目的网络，则添加
2. 如果表中有目的网络，且下一跳相同，则更新
3. 如果表中有目的网络，且下一跳不同，则在更短距离时更新
如果180s没有收到邻居信息，则把距离设为16

OSPF协议/链路状态算法

洪泛法发送信息到自治系统中的所有路由器
交换的信息是相邻所有路由器的链路状态
仅当链路状态变化时，才洪泛发送信息
最后所有路由器都能建立完整的链路状态库
分区，分为主干区域和一般区域，从而路由器分为区域边界路由器，主干路由器，自治系统边界路由器，区域内路由器。
分层使得OSPF更复杂，但是提高了效率
直接放入IP数据报
适合大规模网络
快速收敛

发现邻居节点(HELLO问候分组)
设置到每个邻居的成本度量
向邻站给出自己链路状态数据库中所有链路状态项目的摘要信息[DD数据库描述分组]
对邻站：如果信息自己都有，则不处理；如果没有或者更新，则发送[LSR链路状态请求分组]
收到LSR后，发送[LSU链路状态更新分组]进行更新
对邻站：更新完成后发送[LSAck链路状态确认分组]
使用Dijkstra计算最短路径

BGP

与其它AS的邻站BGP发言人交换
交换网络可达性信息(到达某个网络需要经过的AS)
发生变化时更新有变化的部分
只选择较好路径，而非最佳路径
交换路径向量
应用层协议，基于TCP

三种协议对比

协议	最小值前缀	最大值前缀	大小
类型	RIP	OSPF	BGP
算法	距离向量算法	链路状态	路径向量算法
传输协议	UDP	IP	TCP
路由策略	跳数最少	代价最大	较好，不是最佳
交换节点	邻居	整个区域	邻居
交换内容	整个路由表	所有邻居的链路状态	整个路由表(首次),或变化部分

IP数据报

IpHeader

20字节固定部分
4位版本，4位首部长度(单位是4Byte), 8位区分服务，16位总长
生存时间TTL(每过一个路由则-1，为0丢弃)八位，8位(数据部分)协议[TCP6,UDP17]
16位首部检验和
32位源和目的地址
4字节对齐

IP分组分片

16位标识，同一个数据报的分片都相同
3位标志，2位有效
- DF(Don't Fragment)=1不许分片，否则允许
- MF(More Fragment)=1还有分片，否则这是最后一片
片偏移表示当前片在原分组中的位置，单位是8Byte

题型：计算分片情况

计算分片时，注意有效载荷长度和报文总长的差异性。如果经过不同的网络，MTU不同从而导致分片情况会非常复杂，此时需要逐次计算，而不能直接使用最小的MTU计算。

最大分片长度=\left\lfloor\frac{MTU-20(IP首部长度)}{8}\right\rfloor\times8+20\\ MaxOffset=\left\lfloor\frac{MTU-20(IP首部长度)}{8}\right\rfloor

IPv4地址

32位点分十进制标识符，包含网络号与主机号

分类编址

类	最小值前缀	最大值前缀	大小	用途
A	1	126	$(2^7-2)\times(2^{24}-2)$	包含0.0.0.0和127.x.x.x两种特殊地址，其余均为普通IP
B	128.1	191.255	$(2^{14}-1)\times (2^{16}-2)$	-
C	192.0.1	223.255.255	$(2^{21}-1)\times (2^8-2)$	-
D	224	239		多播地址
E	240	255		保留为今后使用

特殊地址

网络号	主机号	可作为源	可作为目的	用途
全0	全0	T	F	本网范围内表示主机，路由表中的默认路由(对应子网掩码也是0.0.0.0)
全0	特定值	F	T	本网中的特定主机
全1	全1	F	T	本网广播地址(路由器不转发)
特定值	全0	F	F	网络地址
特定值	全1	F	T	广播地址，对特定网络广播
127	任何数(全1和全0除外)	T	T	Loopback

私有IP，用于内网

不会被路由器转发

类别	范围	网段个数
A	10.0.0.0-10.255.255.255	1
B	172.16.0.0-172.31.255.255	16
C	192.168.0.0-192.168.255.255	256

NAT网络地址转换

NAT路由器至少有一个有效的外部全球IP地址
修改IP和端口号
条目是管理员手动添加

子网划分与子网掩码

分类IP的缺点：

利用率低
不够灵活
主机号字段可以将其中的高位作为子网号
子网对外部不可见。
主机号不能全0/全1，故最少两位。
子网掩码：把网络号(和子网号)换位全1，主机号换为全0
子网掩码和IP作与运算可获得子网地址
计算时建议全部转为二进制再计算。
不同子网掩码的网络必然属于不同网段，需要路由器连接。

无分类编址CIDR

消除了ABC类地址和划分子网的概念
回归二级地址(网络前缀+主机号)
记法是IP地址+'/<位数>'
方便子网划分
归并技术，把小网络汇聚成大网络
路由聚合：把相同网络前缀、且下一跳相同的网络，只保留相同部分前缀；查找时采用最长前缀匹配法

ARP协议

封装链路层帧时/实际链路上传送数据帧，需要MAC地址
ARP高速缓存储存IP到MAC地址的映射
如果缓存没有，则广播ARP请求分组
网络层协议
对应机器单播ARP响应分组
如果对应IP不在本网段内，则MAC地址填写默认网关的MAC地址

DHCP

基于广播交互和UDP
动态配置
应用层协议

主机广播DHCP发现报文
DHCP服务器广播DHCP提供报文
主机广播DHCP请求报文
DHCP服务器广播DHCP确认报文

ICMP

提高交付成果的机会
网络探寻和差错报告
IP数据报
Traceroute根据超时报告报文，跟踪一个分组从源点3到终点的路径。

差错报文包括：

终点不可达
源点抑制(网络拥塞)
超时(TTL=0)
参数问题(IP首部字段有问题)
改变路由

以下情况不发送差错报文：

对于ICMP报文的差错
对于第一个分片之外的后续分片不再发送
对于组播地址的数据报
对特殊地址

ICMP询问报文包括：

回送请求及回答(Ping)
时间戳请求和回答(用于同步时间和测量时间)
掩码地址请求和回答
路由器请求和回答

IPv6

根本上解决地址耗尽问题
基本首部40字节
支持扩展首部，扩展首部和数据共65535字节
4位版本，优先级8位，流(特定源点到终点的一系列数据报)标签20位
有效载荷长度16位
下一个首部8位(扩展首部，或者运输层首部)，跳数限制(相当于TTL)8位
源和目的地址均为128位
支持即插即用，不需要DHCP
8字节对齐
只能在主机处分片
重点：无校验和，不分片，过大丢弃

组播/多播

选择性地对有需求的主机发送数据
只在分叉路由器时进行复制
一个组播组有专门的组播地址(224.0.0.0-239.255.255.255), 只能做目的地址
专门的以太网组播MAC地址(01:00:5E::-01:00:5E:7F:FF:FF)中的后23位和组播IP后23位一一对应。
应用于UDP
不产生ICMP差错
并非所有D类地址都可以使用

IGMP

网际组管理协议
组播路由器用来获取当前网络内是否有组播的接收者

加入组播组时，向组播地址发送IGMP报文
本地组播路由器收到IGMP报文后，利用组播路由选择协议将成员关系转发到其它组播路由器
本地组播路由器周期性探寻本地局域网上的主机，确认它们是否是组播组的成员

组播路由选择协议

获取组播转发树的方式

移动IP

移动结点以固定IP进行漫游
移动节点：具有永久IP的移动设备
归属代理：在归属网络中，代表移动节点执行移动管理功能的实体
外部代理：在外部网络中，代表移动节点执行移动管理功能的实体
永久地址(主地址)：移动结点归属网络终点原始地址
转交地址(辅地址)：移动结点在外部网络中使用的临时地址

在外部代理登记获得转交地址，离开时注销
外部代理向本地代理登记转交地址
到移动结点的数据报由本地代理截获并转发数据报到外部代理(以隧道方式)
外部代理拆封后转发数据报给A
来自移动结点的数据报无需处理，直接发送

网络层设备

路由器

具有多个输入端口和多个输出端口的专用计算机，用于转发分组
输入输出队列会导致分组丢失
转发表由路由表产生，路由表由路由算法产生

数据链路层

结点：主机路由器
链路：结点间的物理通道
数据链路：结点间的逻辑通道
帧：协议数据单元，封装数据报

数据链路层负责通过一条链路从一个结点向相邻节点发送数据报。提供逻辑上无差错的可靠数据传输。

数据链路层的功能

为网络层提供服务
- 有确认无连接
- 无确认无连接
- 有确认面向连接
链路管理：主要针对连接
组帧
流量控制
差错控制

封装成帧和透明传输

在数据前后添加头尾，一个作用是帧定界。帧的长度称为帧长。其中数据部分有最大传送单元MTU

透明传输：无论数据是什么样的比特，都可以在链路上传输(如果和控制信息重复，就必须采取措施)。

字符计数法

首部使用计数字段来标明帧内字符数。

易出错

字符填充法

特定的头尾比特组合；对于数据报中的控制字节，则添加转义。

零比特填充法-常用

特殊头尾：相同的01111110 然后数据部分每遇到5个1就添加一个0.

违规编码法-常用

通过物理层编码中的空余编码完成

差错控制

随机噪声：全局性，来自线路本身，可通过传感器改进
冲击噪声：局部性，差错的主要来源，用编码技术解决

为了提高传输效率(减少主机到主机的重传)而需要。

差错 \begin{cases} 位错\\ 帧错 \begin{cases} 丢失\\ 重复\\ 失序 \end{cases} \end{cases}

位错控制

位错控制 \begin{cases} 纠错编码：海明码\\ 检错编码 \begin{cases} 奇偶校验\\ 循环冗余码CRC \end{cases} \end{cases}

奇偶校验

n-1个信息元和1个校验元

奇校验：1的个数为奇数
偶校验：1的个数为偶数

只能检查奇数个比特错误，检错能力50%

CRC

计算D/G，最终发送D+FCS

计算FCS: <设生成多项式10011>

加0：假设生成多项式阶为r，则加上r个0(阶=位数-1) [1101011011>>11010110110000]
模2除法：数据加0后除以多项式，余数为FCS[除法实际上采用异或进行计算]

海明码

发现双比特错，纠正单比特错。

确定校验码位数r：海明不等式 $2^r-r\ge k+1$ ；r为冗余信息位，k为信息位。
确定校验码位置：校验位放置在 $2^k, k=0,1,3,\cdots$ 的位置
求校验码的值：令所有要校验的位(第 $2^k$ 位的校验码检验所有第(k+1)位为1的位)异或=0
检错并纠错

海明距离

在一个码组集合中，任意两个码字之间对应位上码元取值不同的位的数目定义为这两个码字之间的海明距离。任意两个编码之间海明距离的最小值称为这个码组的最小海明距离。最小海明距离越大，码组越具有抗干扰能力。最小海明距离d有如下数量关系：

当码组用于检测错误时，设可检测e个位的错误，则 $d \ge e+1$
若码组用于纠错，设可纠错t个位的错误，则 $d \ge 2t+1$
如果码组用于纠正t个错，检测e个错，则 $d \ge e+t+1$

流量控制与可靠传输机制/帧错控制

流量控制手段

数据链路层：接收方收不下就不回复确认
传输层：接收端给发送端一个窗口公告

停止等待协议

防止丢包。只需要1bit编号即可；超时重传。

发完一个帧后，必须保留副本
数据帧和确认帧必须编号

信道利用率： $\frac{L/C}{T}$

L为T时间内发送的数据量；C为发送方数据传输速率。

信道吞吐率=信道利用率*发送速率

GBN

发送方需要增加缓存，增加序号范围。发送窗口>1，接收窗口1.

累积确认
超时时重传所有已发送但未被确认的帧。
$W\lt 2^n -1$ ；W为发送窗口大小

SR

接收窗口>1，缓存失序的包。

逐一确认
只重传出错帧
$W_T+W_R\le 2^n;W_R\le W_T$
$W_{T-max}=W_{R-max}=2^{n-1}$

信道划分介质访问控制MAC

点对点链路：广域网
广播式链路：局域网

介质访问控制 \begin{cases} 静态划分信道 \begin{cases} 频分FDM\\ 时分TDM\\ 波分WDM\\ 码分CDM \end{cases} \\ 动态分配信道 \begin{cases} 轮询访问介质访问控制：令牌传递协议\\ 随机访问介质访问控制 \begin{cases} ALOHA\\ CSMA\\ CSMA/CD\\ CSMA/CA \end{cases} \end{cases} \\ \end{cases}

静态划分

FDM

用户分配一定频带后，可同时使用。

TDM

按时轮流占用信道，频率无区分； STDM统计时分复用可提高效率

WDM

光的频分多路复用

CDM

1个比特可分为多个码片，一个站点被指定一个唯一的m位的芯片序列。

若如此做，发送1时发送芯片序列，发送0时发送序列反码(通常把0写作-1)。

CDMA是码分复用的一种方式。
多个站点的芯片序列要求互相正交
合成只需各路数据线性相加
分离只需和源芯片序列作规格化内积

随机访问介质访问控制

用户可随机发送信息；信息占用全部带宽。

ALOHA

想发就发
随机重发(超时后随机时间重发)
数据帧发送时间假定相同
吞吐量低，效率低

时隙ALOHA协议

将时间分为若干时间片，所有用户同步接入于时间片开始，重发也必须等到下一个时间片。

CSMA

载波监听多路访问协议。

发送帧前先监听信道

1-坚持CSMA：
- 空闲则立即发送
- 对于忙的信道一直监听，等到空闲马上传输。如果未收到ACK，则等待随机长的时间重传。
非坚持CSMA：
- 空闲则立即发送
- 对于忙的信道，则等待一个随机的时间后再次监听。如此可以减少冲突发生的可能性
p-坚持CSMA：
- 对于空闲信道以p的概率直接传输，否则等待下一个时间槽
- 忙则等待随机时间再监听

CSMA/CD

载波监听多点接入/碰撞检测协议

发送数据时，也检测信道；半双工网络。使用截断二进制指数规避算法确定碰撞后的重传时机。

确定基本退避时间 $2\tau$
定义参数 $k=min(重传次数,10)$
从离散整数集 $[0,1,\cdots,2^k-1]$ 中随机取数r，则重传时间为 $2r\tau$
如果16次重传仍然无法成功，则报错。

规定最小帧长，要求帧的传输时延不少于 $2\tau$ ；即， $最小帧长=总线传播时延\times 数据传输率\times 2$

以太网规定最小帧长64B，故 $2\tau =51.2\mu s$ .

CSMA/CA

载波监听多点接入/碰撞避免协议

常用于无线局域网

发送前检测空闲
如果空闲，等待DIFS时间发送RTS(包含发送和接收地址，下一份数据的持续发送时间)；忙则等待随机退避时间。计时器超时则发送；如果没有收到ACK则二进制指数退避
接收端收到RTS，延迟SIFS( $\lt$ DIFS)则发送CTS
收到CTS后，延迟SIFS，开始发送，同时预约信道
收到数据帧后，延迟SIFS，向接收端返回ACK

无ACK也使用二进制指数退避算法。 RTS/CTS帧是可选的

轮询访问介质控制

轮询协议

主节点轮流邀请从属结点发送数据

令牌传递协议

令牌是特殊格式的MAC控制帧，不含任何信息。令牌环网无碰撞。

常用于负载较重，信息量较大的网络。

有令牌的主机可以修改标志位，附带数据然后发送数据；
如果再次收到自己的帧有误则重发
发送完可以重置令牌标志位
令牌占用时间有限制

局域网

LAN使用广播信道，
覆盖范围小
使用专门传输介质，传输速率高
低延迟，误码率低，可靠性高
各站平等，共享传输信道
采用分布式控制和广播通信

MAC地址

适配器拥有全球唯一的48位二进制地址

以太网(IEEE 802.3)

基带总线局域网规范，采用CSMA/CD

造价低廉
满足速率要求
无连接不可靠服务
只能实现无差错接收
逻辑上总线型，物理上星型
100Mbps以上的以太网称为高速以太网
10BASE-T以太网：使用无屏蔽双绞线，每段双绞线最多100m
100BAST-T以太网：使用光纤(全双工，不使用CSMA/CD)或者双绞线(半双工，使用CSMA/CD)，帧长不变，电缆长度减小为100
吉比特以太网：与10BAST-T和100BASE-T向后兼容。使用光纤(全双工，不使用CSMA/CD)或者双绞线(半双工，使用CSMA/CD)。
10吉比特以太网：只支持全双工，使用光纤，不使用CSMA/CD。

以太网MAC帧

6B目的，6B源，2B类型；数据46-1500字节(不足则填充)，4B FCS

以太网帧无帧结束位置，而且有最小发送间隔

帧长64-1518；数据46-1500.

WLAN(IEEE 802.11)

WLAN的MAC帧头

2帧控制，2生存周期ID，6接收地址，TA发送地址，6目的地址，2序列控制，6源地址。

需要通过基站完成通信，故有4个地址。

说明	ToDS	FromDS	地址2	地址2	地址3	地址4
直接发到路由的帧	0	0	目的地址	源地址	系统BSSID	未使用
发往AP	1	0	AP地址	源地址	目的地址	未使用
来自AP	0	1	目的地址	AP	源地址	未使用
AP到AP(无线桥接)	1	1	接收端地址	发送端地址	目的地址	源地址

总结：

地址1总是"当前要接受帧的目标"的地址
地址2总是"当前发送帧的目标"的地址
地址3就是剩下的那个参数。如果需要4个地址，则为目的地址
地址4要么未使用，要么是源地址(用于自组网)

AP扫描：

AP发送扫描
主机发送请求
AP发送确认

请求AP：

主机广播请求
AP响应
主机请求AP
AP确认

广域网

分组交换技术
强调资源共享
延迟较大
除了物理层和数据链路层，还包含网络层

PPP协议

点对点协议
只支持全双工
最广泛
提供差错检测：错就丢弃，无需纠错
无编号，不可靠
支持同时使用不同的网络层协议
面向字节，在异步线路使用字节填充，同步线路使用比特填充

三个部分：

支持封装IP数据报道串行链路
身份验证：链路控制协议LCP
网络控制协议NCP，为网络层协议建立和配置逻辑上的连接(PPP协议允许多种多种网络层协议同时工作，但各协议均需相应的NCP配置)

5首部，3尾部，1500 MTU

7E首位定界符

HDLC协议

高级数据链路控制协议

同步网
面向比特
全双工
有编号，可靠数据传输

首位各8位标志，8位地址8位控制，可变信息，16位FCS

分为信息帧、监督帧和无编号帧

采用0比特插入法

3种相应方式：

正常响应：非平衡结构(主从站)，主站发送从站响应，从站在收到主站许可后才可传输
异步平衡：平衡结构(复合站)，每个复合站都可以进行数据传输
异步响应：非平衡结构，从站即使未收到主站允许也可传输

链路层设备

网桥

根据MAC帧的目的地址进行转发和过滤
交换机的前身
多为2个端口
分割冲突域
- 增大吞吐量
- 扩大了物理范围
- 提高了可靠性
透明网桥：即插即用(利用源地址自学习填满转发表)，站点不知道其存在
源路由网桥：在发送帧时，将详细的最佳路由信息放在帧首部(源以广播方式向目的站发送发现帧，然后发现帧原路返回).

自学习

收到帧时，根据源地址更新转发表
对于未记录的目的地址，向所有其他端口转发
对于有记录的，向目的端口转发，或丢弃（）

以太网交换机

接口较多
直通式：查看完目的地址就转发，不支持速率不同端口的交换
储存转发式：缓存帧，并检验，支持不同速率端口。

冲突域和广播域

冲突域

同一时间内只能有一台设备发送信息的范围，通常是物理层设备连接的范围

广播域

网络中能接收任意设备发出的广播域的所有设备的集合。

隔离问题

	隔离冲突域	隔离广播域
物理层设备	F	F
链路层设备	T	F
网络层设备	T	T

物理层

确定与传输媒体接口有关的一些特性。

数据：传送信息的实体，有意义的符号序列
信号：数据的电气表现，是数据在传输过程中的形式
信源：产生和发送数据到源头
信宿：接收数据的终点
信道：信号的传输媒介；一条线路通常包含双向的信道
并行：适合近距离

码元

用一个固定时长的信号波形，代表不同离散数值的基本波形，是数字通信中信号的计量单位；时长内的信号称为k进制(k种离散状态)码元，时长称为码元宽度

速率

单位时间内传输的数据量，可用码元传输速率和信息传输速率表示。

码元传输速率

波特率，单位：波特(Baud)；1波特表示一秒传输一个码元，与进制数无关。脉冲个数，信号变化次数。

信息传输速率

信息速率，比特率。单位时间内传输二进制码元个数。注意以太网使用曼彻斯特编码，故比特率是波特率的一半。

带宽

从网络中某一点到另一点所能通过的最高数据率。

信道带宽

最高频率与最低频率之差；频率太高会导致码间串扰。

奈氏准则

在理想低通条件下，为了避免码间串扰，极限码元传输速率为2*信道带宽W(单位是Hz)波特。

从而理想低通信道下的极限数据传输率为 $2Wlog_2V(b/s)$ V:码元的离散电平数目。

香农定理

信噪比 $dB=10log_{10}\frac{S}{N}$ ; S为信息，N为噪声。在带宽受限且有噪声的信道中，信息的数据传输速率有上限 $Wlog_2(1+\frac{S}{N})(b/s)$

注：如果奈氏准则和香农定理都可用，则选取二者最小值

编码与调制

基带与宽带

基带信号：直接01表示，然后送到数字信道上传输；1、0的表示称为编码方式
宽带信号：调制后到模拟信道中传输。

数字>>数字

NRZ

高1低0-非归零编码，无检错，难同步。

RZ/归零编码

每个码元结束时都会归0的编码。仍然是高1低0.

NRZI/反向不归零编码

信号翻转表示0，否则为1

曼彻斯特编码

一个码元分为2个相等的间隔，前高后低为1，否则为0.中间的跳变可用于同步，但是占用的频带宽度是原始基带宽度的两倍。

差分曼彻斯特编码

同1异0(后一个和前一个的后半部分相比)。可自同步，抗干扰。

4B/5B

插入额外的Bit来编码

数字>>模拟

调幅 ASK：易实现，抗干扰差
调频 FSK：易实现，抗干扰强，应用广泛。
调相 PSK：分绝对调相和相对调相
调幅+调相 QAM

模拟>>数字

脉冲编码调制PCM：

抽样：周期扫描，频率 $f_{采样}\ge2f_{信号最高频率}$
量化
编码

传输媒体

传输媒体不是物理层。其在物理层之下。

导向性

电磁波沿着固体传播。

双绞线

并排绞合的绝缘铜线。绞合可减少电磁干扰。需要放大器和中继器来增加传输距离。

UTP无屏蔽层，STP有屏蔽层
在10BASE-T中，UTP最大长度100m

同轴电缆

基带同轴电缆-局域网
宽带同轴电缆-有线电视

抗干扰性强，传输距离更长；更贵。

光纤

光脉冲通信，带宽非常大。传输损耗小，中继距离长，抗电磁干扰，保密性好，体积小。

单模光纤：光线直径减小到一个光波长度，就像博导一样可以让光一直向前传播。使用激光二极管，适合远距离传输
多模光纤：利用光的全反射·

非导向性

无线电波

发散，广播

微波/红外线/激光

信号定向传播

设备

中继器

将信号再生还原。两端是网段，是两类完全相同的网络互联，网段速率也相同。只处理电气部分。

集线器

再生，放大；将输入向所有端口转发，是一个共享式设备，无定向传输能力。可能出现冲突。平分带宽。

接口规范

机械特性：物理连接的规范
电气特性：规定传输二进制位时，线路上的电压、阻抗、距离
功能特性：规定电平的含义
规程特性：各条物理线路的工作规程和时序关系

实际上还有许多本博客内容以外的试题知识点(比如VLAN，PPP的细节等等)，但是👴选择躺平，不卷了不卷了

概述​

计算机网络​

功能​

参考模型​

OSI​

TCP/IP协议栈​

应用层​

原理​

体系结构​

进程通信​

HTTP​

电子邮件​

DNS​

DNS查询路径​

查询方式​

DNS资源记录(RR)​

DNS报文格式​

P2P文件分发​

FTP​

Telnet​

传输层​

多路复用和多路分解​

UDP​

UDP报文结构​

UDP检验和​

TCP​

TCP首部​

TCP连接管理​

TCP可靠数据传输​

TCP流量控制​

TCP拥塞控制​

慢开始&拥塞避免​

快重传&快恢复​

题型​

网络层​

网络层概述​

网络层功能​

数据交换​

电路交换​

报文交换​

分组交换​

数据报与虚电路​

路由算法​

静态/非自适应算法​

动态/自适应算法​

RIP协议/距离向量算法​

OSPF协议/链路状态算法​

BGP​

三种协议对比​

IP数据报​

IP分组分片​

题型：计算分片情况​

IPv4地址​

分类编址​

特殊地址​

私有IP，用于内网​

NAT网络地址转换​

子网划分与子网掩码​

无分类编址CIDR​

ARP协议​

DHCP​

ICMP​

IPv6​

组播/多播​

IGMP​

组播路由选择协议​

移动IP​

网络层设备​

路由器​

数据链路层​

数据链路层的功能​

封装成帧和透明传输​

字符计数法​

字符填充法​

零比特填充法-常用​

违规编码法-常用​

差错控制​

位错控制​

奇偶校验​

CRC​

概述