按复习顺序（目前的顺序是：绪论→链路层→网络层→传输层→网络安全）整理计网复习知识点。🐛🐛🐛
绪论
什么是因特网
“网络的网络”
从多维度分析：
| 维度 | 解释 |
|---|---|
| 设备 | 端设备、通信链路、路由器 |
| 服务 | 分布式应用程序&套接字接口 |
| 协议 | TCP/IP… |
连接到因特网，然后传输
端系统-边缘路由器-核心路由器-边缘路由器-端系统
| 类型 | 举例 |
|---|---|
| 网络边缘 | 端系统（主机）：client, server, data center… |
| 网络接入 | 电缆、光纤、卫星… |
| 网络核心 | 分组交换机&路由器构成的网络 |
传输方式：电路交换（独占，e.g.专用电话线）；分组交换（分块传输，核心路由器负责调度）；虚电路（分组交换方式实现电路交换，固定的路由为其预留带宽）
协议体系结构
分层的
OSI:物理、数据链路、网络、传输、会话、表示、应用，后三层在TCP/IP中均在应用层实现
网络性能评估
| 时延类型 | 产生方式 |
|---|---|
| 传输时延 | 将分组发送出去所需要的时间，Length / Rate |
| 传播时延 | 分组在网络中传播所需要的时间，RTT = 2 * propagation delay |
| 排队时延 | 分组在缓冲区等待 |
| 处理时延 | 检错、查看首部并导向正确位置 |
顺序：4-3-1-2
丢包原因：缓冲区不足 or 传播中出错
吞吐量：可用带宽，路径上获得的带宽的最小值
链路层
核心服务
分帧（frame = 头+datagram+尾）、MAC（媒介访问控制，在共享广播信道时协调节点）
差错检测
奇偶校验、CRC（循环冗余检测）
二维奇偶校验的定位：横轴、纵轴各有一个出错→交叉定位→纠正；对于两个出错可以检测
CRC：传输d比特的数据D，考虑r比特的CRC比特R，$D*2^r{\oplus}R$ 记为<D, R>（形式上为D和R比特的组合）。提前选取r+1位的生成多项式G，然后发送方计算出R，满足<D, R> mod G = 0，发送<D, R>。接收方用G检验发送方数据。
在CRC计算的加减法中使用模2运算（加法不进位减法不借位）。计算R时在D后补r个0，除以G，得到的余数为R
$e.g. D=101110,r=3,G=1001,R=?$
局域网 LAN
拓扑结构
星形、环形（token ring：sender发送数据并最终吸收数据，吸收完后释放令牌）、树形…
以太网的总线拓扑：使用同轴电缆总线互联节点（广播局域网）
传输媒介
网线、WiFi
以太网 Ethernet
服务
对网络层提供不可靠服务：若未通过CRC检测则直接丢弃，通过则啥也不做（不发送ACK,Non ACK)
无连接服务（类似UDP，不握手）
以太网帧的格式
| 前导码 | Dst Addr | Src Addr | Type | Data | CRC |
|---|---|---|---|---|---|
| 标记帧的开始 | 目的地址 | 源地址 | 类型（如arp） | 数据，即IP数据报 | 校验码 |
| 8字节 | 6字节 | 6字节 | 2字节 | 46-1500字节，不足补全 | 4字节 |
地址称为MAC地址，固定值，AB-CD-EF-GH-IJ-LM，前3字节为厂商；可重复
前导码前7个字节均为10101010，最后一个是10101011，为避免Data等中出现前导码，可以用一定规则插入字节，例如每遇到101010则插入0，这样只会在前导码中出现1010101
地址解析协议 ARP
通过IP获取同一局域网内某主机的MAC地址。
方式：广播“谁是IP：xxx”，所有接收方将其与自己的IP相比对，若成功则发送回自己的MAC地址
网桥和交换机
将多个以太网连接成更大的以太网的局域网组网设备
功能：路由转发和过滤（转发表+地址学习）、生成树算法
转发表初始为空，收到A->B，由端口a到达，则记录A对应端口a
生成树算法：分布式算法
*广播风暴问题：由于成环导致的，因此使用生成树避免成环
- 一定规则确定树根，如MAC地址最小值
- 每个节点向邻居发送Message(Y, d, X)，其中Y为自己目前认为的根，d为自己到根的距离，X为自己，初始时均发送M(X, 0, X)
- 当节点X收到M(Y, d, Z)，且Y更适合当根（按照1，即Y < X），则更新，X发送M(Y, d+1, X)给邻居
对比
Hub, Bridge, Layer2 switch, Layer3 switch
| Hub | 只提供物理转发 |
|---|---|
| Bridge | 有转发表，可自学习 |
| Layer2 switch | 增加了交换功能，可避免冲突（一个端口就是一个冲突域） |
| Layer3 switch | 加入一些路由器功能 |
*共享媒介（Hub、网桥）和交换机的区别：
- 能力区别，switch交换逻辑下速度更高且collision free（crossbar连接）
- 端口数区别，网桥2-4个，交换机很多
媒介访问控制 MAC
三大方式：信道切分、轮流访问、随机访问
媒介利用率U = 传输帧的时间/总时间=效率
相对传播时间a=传播时间/传输时间=传播时间（传输时间被正则化为1）
基础效率分析：point-to-point方式，总时间为1（传输）+a（传播），传输帧的时间为1，则 $U=\frac{1}{1+a} $
信道切分
- 时分多址 TDMA：每个时间帧分为固定个时隙，每个节点只能在每个帧中给定的时隙使用；在人少时效率低
- 频分多址 FDMA：每个节点占用R bps信道的一定频段，故仅有R/N带宽
- 码分多址 CDMA：每个需要发送的比特拥有1时隙，比特为1或-1；对每个发送方进行特殊编码，将其每个比特编码为M个比特序列，同时发送的发送方的比特序列将作异或，接收方按一定规则解码即可。例如，发送方的编码为1 1 1 -1 1 -1 -1 -1，则1即为上述编码，-1转为-1 -1 -1 1 -1 1 1 1
轮流访问
-
轮询：选定主节点轮流告诉其余节点可传输帧的数量，鲁棒性低（主节点不可故障）、有轮询时延。e.g.蓝牙
-
令牌传递协议（令牌环）：拥有令牌的sender发送数据，指明receiver，然后数据在环上运输，某节点发现自己是receiver则接收数据；当sender再次收到该数据时，回收并释放令牌给下一节点
效率分析：假设有N个站点，令牌环下的传播时间a即为绕一圈的时间，总时间为传输帧的时间+将令牌送往下一节点的时间（这时候视为发送完成）。设0时刻开始发送。
什么时候可以释放令牌：①已发送完毕，即要在1时刻之后；②已回收数据，即要在a时刻之后。
故对于大帧（a<1)，在1时刻开始释放令牌，对于小帧（a>1），在a时刻开始释放令牌，释放令牌需要的时间为a/N；
故大帧效率：$U=\frac{1}{1+\frac{a}{N}} $，小帧效率：$U=\frac{1}{a+\frac{a}{N}} $。
随机访问
ALOHA
立刻传输，若传输过程中发生碰撞，在传输完后立刻以p概率重传，否则等待一个帧的时间，再以p概率重传。
效率分析：设一个帧时间为1，某节点的某帧在t~0~时间开始传输（概率为p），则若成功，[t~0~-1, t~0~]以及[t~0~, t~0~+1]时间内均不能有其他帧的传输，概率为 $p(1-p)^{(N-1)}$，故总的成功概率为 $p(1-p)^{2(N-1)}$，效率为 $Np(1-p)^{2(N-1)}$。当N趋于无穷时，求极限得其最大效率为p = 1 / (2N - 1)时，效率 $U=\frac{1}{2e} $.
时隙ALOHA
帧：L比特，一个时隙：L/R，在每个时隙的起点以ALOHA的方式发送（即若碰撞则等待一个时隙，再以p概率）
效率分析：t~0~时刻其他不发送即可，即 $Np(1-p)^{N-1}$。当p = 1/N时，最大效率 $U=\frac{1}{e} $.
载波侦听多路访问 CSMA
先听信道是否繁忙，若不繁忙则传输，否则：
非持续：等待随机一段时间
1-持续：一直等待直到空闲，然后抢占
p-持续：一直等待直到空闲，然后按p概率抢占，一般p=1/N
CSMA/CD：以太网的方法，引入碰撞检测，在传输过程中若发生碰撞（故为全双工）则立即停止，然后发送jam信号（全1）提醒其他节点（用以保证其余所有节点都检测到该次冲突）。在这之后，使用二进制指数后退算法（BEB），即在碰撞n次后，从[0, 2^n^-1]大小的窗口中选择一个随机数K，等待K个时隙。在0-10次，窗口放大，11-16次，窗口不变，仍失败则丢包。
*时隙被定义为512bit在10Mbps或100Mbps网络的发送时间
*最小帧长：传输时间≥2a，从而保证能被检测到冲突
CSMA与ALOHA相比，多了“听”的过程，即若繁忙会等待到不繁忙。
效率分析：
假设是p-持续的，而不是BEB算法
某个节点在某个slot成功发送的概率为 $A=Np(1-p)^{N-1}$
取极限，可得 $p=\frac{1}{N}$ 时， $A=(1-\frac{1}{N})^{N-1}$，当N趋于无穷时 $A=1/e$
某个节点用j个slots发送出去的概率为 $A(1-A)^j$
假设一个contention slot为2a（最坏情况下需要两倍传播时间检测到冲突），在每一个contention slot，所有节点都以概率p抢占信道，直到某个节点抢到并成功发送数据。
平均情况下，需要 $\sum_{j}^{\infty}jA(1-A)^j$ 个slots（几何分布），该值为$B=\frac{1-A}{A}$。
故
$U=\frac{Frame\ time}{Frame\ time+Propagation\ time+Average\ contention time}$
$=\frac{1}{1+a+2aB}$
$=\frac{1}{1+\frac{2-A}Aa}\approx \frac{1}{1+4.44a}$
对于实际的CSMA/CD，其近似值为：
$U=\frac{1}{1+5d_{prop}/d_{trans}}=\frac{1}{1+5a}$
无线局域网 WLAN
基本术语
基站：负责协调与之相关联的多个无线主机的传输。例子：蜂窝塔、接入点（AP）
终端设备 STA(tion)：如手机等
基本服务集 BSS：1个AP和若干个STA构成，是该AP的管辖范围
SSID：用来区分不同的网络，是无线局域网的名称，例如：TP-LINK_ABCD
扩展服务集 ESS：由多个使用相同SSID的BSS组成
自由空间损耗FSPL：$FSPL=(\frac{4{\pi}df}{c})^2$，其中f为频率，$\frac{f}{c}=\frac{1}{\lambda}$，即波长的倒数
信噪比SNR：信号和噪声强度的比值
误码率BER：大致为接收到错误比特的概率
BER随着SNR的增强而降低，随着带宽的提高而上升
与LAN的最大区别
- 递减的信号强度（由FSPL，其随着距离增加而减弱）
- 来自其他源的干扰（同一频段的电波源互相干扰）
- 多径传播（由于电磁波会反射，在发送方到接收方走了不同长度的路径）
IEEE 802.11体系结构
媒介访问控制——CSMA/CA
带碰撞避免的CSMA，是分布式协调（DFS）
DIFS（分布式帧间隙）、PIFS、SIFS（短帧间隙）：站点选择的等待时间，三者帧间距逐渐变小（DIFS等待时间最长），优先级逐渐增加（SIFS优先级最高，即从某时刻开始，对于想要等待SIFS时间的节点来说，其将抢占到节点）
原理：802.11协议精读2：DCF与CSMA/CA，有详细的包括RTS+CTS四帧方法的介绍，该方法是为了解决隐藏终端问题，即两个STA可能无法监听到对方，但是却要发送给同一个AP，从而造成不停的碰撞
“先backoff再发”
*为什么不用CSMA/CD：①WLAN是半双工；②存在诸多问题，如衰减、干扰、隐藏终端问题，导致无法检测到碰撞
802.11帧
有四个地址，第四个用于AP在自组织模式中互相转发。
地址1：要接受该帧的MAC地址，即dst
地址2：传输该帧的MAC地址，即src
地址3：一个BSS是某个子网的一部分，经由一个路由器接口与其他子网相连，地址3即为该接口的MAC地址
原因：对于路由器，其并不知道AP的存在（不知道它所连接的是WLAN），当它需要从R1接口将数据发送给某一STA（H1）时，其使用以太网帧封装（src：R1的MAC,dst：H1的MAC），当AP接收到这个帧时，将其转换为802.11帧，补充自己的MAC地址（地址1：H1的MAC，地址2：AP自己的MAC，地址3：R1的MAC）；当STA发送数据给路由器时，其使用802.11帧（地址1：AP的MAC，地址2：H1自己的MAC，地址3：R1的MAC），经由AP转换为以太网帧（src：H1的MAC,dst：R1的MAC）
网络层
控制平面
网络层的核心服务
路由，转发，建立连接（虚电路）
自治系统内部的路由选择算法
能到 $\equiv$ 无loop，无dead end，故考虑最小成本
分类方式：集中式/分布式、静态/动态、负载敏感/负载迟钝
链路状态路由选择算法（LS）
是一种集中式算法，举例：Dijkstra算法、OSPF
c(x, y)：x到y的cost（不是邻居则为∞），
D(v)：当前得到的从根到v的最短路长度，
p(v)：在这个D(v)下到v的前驱节点，
N’：当前集合
方法：选择不在N’的、D(w)最小的w加入N’，更新D(v)，若v是w的邻居且不在N’中，更新方式：D(v)=max{D(v), D(w)+c(w,v)}
距离向量路由选择算法（DV）
是一种分布式算法，举例：Bellman-Ford算法、RIP
d~x~(y)：x到y的最短路径的开销，d~x~(y)=min{c(x, v), + d~v~(y)} for all v = x’s neighbor
对于每个节点x，其需要维护：所有邻居v的c(x, v)、节点x的距离向量D~x~={D~x~(y), y ∈ n}、所有邻居的距离向量，距离向量由路由选择表维护，包含自己和自己邻居的距离向量
方法：每个节点不时向邻居发送自己的距离向量副本，若发现邻居发来新的距离向量则保存该邻居新的距离向量、更新自己的距离向量，更新规则为D~x~(y) = min{c(x, v) + D~v~(y)}，v为x的所有邻居。
更新完后若发生了变化，则向邻居发送自己新的距离向量
一个实际的算法运行见书P251
无穷计数问题及其解决：当链路xz发生变化时，x可能会选择通过邻居y到达z，然而邻居y提供给x的路径可能是依赖于原先的链路xz，这是由于更新是异步的，然后x更新了自己到z的距离又会导致y的更新，从而无限循环
毒性逆转：若y通过x到达z，则它对x的通告里的距离向量中，D~y~(z)将为∞。这样，x就不会试图经过y到达z。
毒性逆转不能解决涉及三个及以上节点的问题，例如：
在上图中，若AB间突然增加到100，虽然D告诉B自己到A是无穷，但是C告诉B自己到A是3（C-D-B-A），依然借用了B节点
LS和DV的比较
信息复杂性上，DV更简单；速度上，LS更快（DV需要多轮）；鲁棒性上，都有缺点
相同点：都是基于最短路径的路由选择，都用于域内路由
开放式最短路径优先 OSPF
是一种LS算法，用于自治系统(AS)内部
每个路由器负责发现、维护与邻居的关系，并将已知的邻居列表和链路费用LSU(Link State Update)报文描述，通过可靠的泛洪与AS内的其他路由器周期性交互，学习到整个自治系统的网络拓扑结构;并通过自治系统边界的路由器注入其他AS的路由信息，从而得到整个Internet的路由信息。每隔一个特定时间或当链路状态发生变化时，重新生成LSA，路由器通过泛洪机制将新LSA通告出去，以便实现路由的实时更新
AS 自治系统
意思是一组内部管理下的网络，它们之间共享同一个路由选择方法。
一般来说，AS内部的大多数路由器只知道本AS的拓扑结构，不知道其它AS的内部拓扑，也就不能直接知道去其它AS的路由，因为IGP类协议只在AS内部运行。但AS内会有一些骨干路由器和其它AS的骨干路由器之间运行EGP类协议，这些骨干路由器知道去其它AS的路由后会把这些信息通过IGP类协议重新发布，让本AS内的路由器也知道去其它AS的路由。
ISP之间的路由选择算法 BGP
isp：网络服务提供商
各个GP（网关协议）的对比
BGP:边界网关协议，自治系统间的路由协议
iBGP:内部边界网关协议，用于同一个AS内通告BGP信息 eBGP:外部边界网关协议，用于不同的AS间
IGP:内部网关协议，如OSPF、RIP等
EGP:外部网关协议，BGP是一种EGP
BGP过程
在上图所示的网络拓扑中，假设x与3c相连，现在向AS1和AS2中的所有路由器通告x的可达性信息，那么，AS3的边界路由器3a将通过eBGP通告给1c“AS3 x”，通过iBGP到达1b后，1b向2a通告“AS1 AS3 x”，最终使得所有路由器都知道如何到达x。
在上述过程中，传达的路由信息包含以下重要的BGP属性：
AS-PATH：通告已经通过的AS列表，如上述例子中的“AS3”、“AS1 AS3”，这个属性也可以用于检测是否环路（如果一个路由器在AS-PATH中看到了自己所处的AS，它将拒绝该通告
NEXT-HOP：AS-PATH起始的路由器接口的IP地址，上述例子中的“AS3 x”的NEXT-HOP为3a右侧侧接口的IP地址，“AS1 AS3 x”的NEXT-HOP为1b右侧接口的IP地址。这样，AS1内部所有路由器都知道到达AS3的BGP路由为3a、AS2都知道为1b。
LOCAL-PREF：用于iBGP内部，建议路由器优先选择哪条线路
MED：越低越好
IGP cost：AS内部所消耗的代价
热土豆算法
通过AS间协议学到可以通过多个网关到达x→通过IGP确定内部到达每个网关的开销→选择最低的那个
即尽量快地送出自己所在的AS
实际算法
优先级从高到低：
- LOCAL-PREF推荐的
- 若所有都具有相同的LOCAL-PREF值，最短AS-PATH的
- 若所有都具有相同的LOCAL-PREF值和AS-PATH，通过热土豆算法确定的
- 若仍然剩下多条，通过BGP标识符（MED）确定的
数据平面
IP协议（仅介绍IPv4）
首部长度：若不含Options则为20Bytes
服务类型 ToS：便于提供特定等级的服务
数据报长度：一般不超过1500（最大传送单元MTU），1500是以太网帧的承载上限
分片：16bit标识，3bit标志flag，13bit偏移量
标识表明是否为同一个包的分片，flag最高位DF Don’t Fragment，为1则禁止分片，最低位MF more fragment，为1则表明不是最后一个，offset值要*8，这也规定了最小分片的单位是8Bytes
例子：2500Bytes，分成一个1480+20和一个1000+20，id为123，则第一个包该行为123 0/0/1 0，第二个为123 0/0/0 185，185*8=1480
TTL：每一跳-1，为0时丢弃，从而避免死循环
协议：交给哪个特定的运输层协议，如6代表TCP
首部校验和：每两字节当作一个数作求和（溢出的回卷，即最低位再+1），结果的反码即为校验和
*为什么是反码：这样验证结果只需要将计算得到的和校验码相加，全1则正确，节省时间
地址：每8bits（2bytes）分开记，如12.34.56.78，即00010010 00110100 01010110 01111000
地址是层次化的，分为Network/Prefix和host/Suffix部分。一个路由器接口和多个主机接口形成的网络岛称为子网，子网掩码是子网的地址，例如123.45.6.0/24，意为该子网的前缀为前24位123.45.6，所有具有该前缀的属于同一子网，目的地址全1(255.255.255.0)为广播
获取地址的DHCP动态主机配置协议，由DHCP服务器为用户分配IP地址，过程为：用户广播发现DHCP服务器（DHCP发现），每个DHCP广播一个可以提供的IP（此时用户没有IP地址故仍需广播）包含IP地址租用期（DHCP提供），用户选择自己想要的并广播（DHCP请求），被选中的发送DHCP ACK，完成。
网络地址转换NAT，解决IP地址不够用，利用端口号进行转换，内部一般使用私有地址，例如：
主机A（地址：1.2.3.4）的端口123发送数据，被路由器（地址：11.2.3.4）转换为addr:11.2.3.4 port:456这个转换是双向的，记录在NAT表里，这样1.2.3.4只是A自认为它的IP地址
ICMP
用于发送出错信息，实现traceroute和ping
ICMP是IP的有效载荷，其协议号为1。
ICMP报文含有类型字段+编码字段（对类型的补充，如不可达类型分为目的网络、目的主机、目的协议、目的端口不可达等）+产生ICMP报文的IP数据报的首部和前8个字节（以便发送方确定产生ICMP的是哪个报文）
ping：发送方发送类型8编码0，ICMP Echo Request，接收方回答类型0编码0，ICMP Echo Reply
traceroute：发送TTL为1，2，3…的IP数据报，相应路由器检测到到期并发送TTL过期警告的ICMP
IP组播
当某一个人向一组人发送数据时，它不必将数据向每一个人都发送数据，只需将数据发送到一个特定的预约的组地址，所有加入该组的人均可以收到这份数据。
原因：在一些诸如视频点播的应用时，单播对主机的压力太大、而广播又对网络链路的压力太大
组播地址：特殊的IP地址，仅用于组播，例如224.0.0.1是向本网段所有设备发送组播报文，224.0.0.2是向本网段所有路由器发送组播报文
IGMP互联网组管理协议
用于实现用户加入、退出组
组播过程
组播源的注册：组播源通过单播隧道的方式把组播地址发给中介机构（RP）
用户想要加入某个组，但不知道其组播地址，故使用IGMP广播
路由器静态配置或动态发现RP的地址，层层上传（基于RP的RPTree），RP将组播源的地址返回给用户
用户退出RP，加入该组播，形成SPT（基于源的树，Source Path Tree）
路由器
组成：输入端口、输出端口、交换结构（将输入端口连接到输出端口）、路由选择处理器
性能评估：$capacity=N*R$，其中N为端口数，R为端口速度
分类：核心路由器&边缘路由器（均属于网络核心）
输入端口处理：接收包→检查包并更新包头（checksum先检查之后还要再重新计算、更新TTL、可能分片）→寻找出口→附加信息（仅存在于路由器内部的一些额外设置，增加其产品竞争力）→交给交换结构
*寻找出口：最长前缀匹配规则：路由器查询自己的转发表，选择最长的匹配项
交换结构：与交换机类似的crossbar
输出端口处理：排队→封装（下一跳如果进入数据链路层，则需要封装）→发送
*排队规则：
先到先走/先来先服务 FIFO/FCFS
优先权排队 Priority Queue：分成多个不同优先级的队列，队列内FIFO，队列间按优先级
循环排队规则 RR：依然是多个队列，但是队列间不具有优先级，按轮询方式
加权公平排队 WFQ：轮询每个队列，但是每个队列具有不同的权重（在一次轮询中可以走多个包）
RR和WFQ均为保持工作排队，即若当前队列为空则跳到下一个
路由器和交换机的对比
“路由器还是交换机，决定因素是软件，而不是硬件”，例如三层交换机
工作层次不同： 交换机主要工作在数据链路层（第二层） 路由器工作在网络层（第三层） 转发决策不同： 交换机转发依据MAC地址，查看帧的头部，不需要修改数据帧 路由器转发依据IP地址，查看数据报的头部，需要修改TTL，可能还需要修改Checksum，重新分片封装 主要功能不同： 交换机主要用于组建局域网，而路由主要功能是将局域网相互连接起来或者接入Internet。 交换机不能分割广播域，路由可以。 路由还可以提供防火墙的功能。
复杂程度不同：
路由配置、工作都比交换机复杂。这也导致交换机更廉价、快速，可以直接使用硬件处理。
*广播域：如果站点发出一个广播信号后能接收到这个信号的范围。通常来说一个局域网就是一个广播域
*冲突域：一个站点向另一个站点发信号。除目的站点外所有能收到这个信号的站点就构成一个冲突域
*交换机能分割冲突域（通过MAC找到目的主机，然后就不会发给和该主机冲突的其他主机了
*交换机不能分割广播域，但路由器能（当收到广播后，交换机会发送给局域网内所有节点，路由器分割了这些广播域）
传输层
基本服务
编址：IP地址+端口号形成socket，对于UDP，<local IP, local port>，对于TCP，<local IP, local port, remote IP, remote port>，端口号16bits
复用：多路分解（根据首部信息将数据交付到正确的套接字）&多路复用（将数据生成报文段并交付网络层）
流控制、可靠传输、面向连接服务
*TCP和UDP在复用和分解时的不同：若两个UDP报文段具有相同的dst ip & port，那么将通过相同的目的套接字被定位到相同的进程，而TCP是面向连接的（连接的双方一一对应）
可靠传输
可靠传输需可能遇到的问题及其解决方式
按序交付和副本检测（重复报文）
引入序列号，要求序列号空间足够大
数据包确认
ACK及NAK信号
数据包错误
损坏：校验和
丢失：超时重传机制
传输效率
流水线协议，滑动窗口+缓冲区
累计确认：接收方的ACK是自己期待收到的下一个，即若丢包一直重复发送同一个ACK号
*例如，接收方发送了ACK1和ACK2，即使ACK1丢失了，由于累计确认，发送方在收到ACK2时也知道接收方已经收到了ACK1
*快速重传：在收到对相同数据的3个冗余ACK之后，发送方就认为这个报文段丢失，立即重传而不是等待超时
选择性确认：接收方的ACK指明自己收到了哪些数据包
回退N步：若超时，窗口回退N步，即重发所有已发送、未确认的包，适合出错率低时使用
选择性重传：接收方缓存所有收到的分组，当某个错误时，只要求重传该分组，收到一定分组后一起交付给上层，适合出错率高时使用
UDP协议
无连接、非可靠的
举例：DNS、DHCP
首部格式：源端口号（在需要对方回信时选用）+目的端口号+长度+校验和，每个2字节
TCP协议
首部格式
port用于复用和分解，sequence num是Byte的偏移量（TCP是流协议）（而不是包的ID），ACK标明确认号字段，HdrLen是首部长度（若无Options则为20），Flags中RST、SYN、FIN比特用于连接建立和拆除；PSH比特指示接收方应立即将数据交给上层；CWR和ECE用于明确颜色通告；URG指示报文里存在“紧急”数据，其位置由Urgent pointer确定。
MSS 最大分段大小：Data的最大长度，在MTU为1500的情况下，MSS为1460
连接维护
TCP是一种全双工服务
建立：三次握手
ISN：初始序列号，随机生成的
设A为发送方，B为接收方，建立过程使用到了flags中的SYN和ACK
- A→B：seno = A’s ISN，Ack=N/A（期待对方的序列号），SYN
- B→A：seno = B’s ISN，Ack=A’s ISN+1，SYN+ACK
- A→B：Ack=B’s ISN+1，ACK
即，SYN→SYNACK→ACK (for SYNACK)
终止：四次挥手
- A：FIN
- B：ACK
- B：（在完成接收工作后）FIN
- A：ACK
B在接收到A的ACK后关闭，A在发送ACK后等待一段时间确保B收到自己的ACK（若没收到B会重发FIN）然后关闭
中断：A发送RST，则立即中断连接
流量控制
目的
消除发送方使得接收方缓存溢出的可能
Sliding Window
| sender | receiver | |
|---|---|---|
| left edge | LastByteAcked | LastByteRead |
| right edge | LastByteSent | LastByteRcvd |
设RcvBuffer为接收方的缓冲区大小，对于接收方，为了保证不溢出，需要满足(LastByteRcvd - LastByteRead) ≤ RcvBuffer
则接收方在其Advertised Window字段填上接收窗口剩余大小rwnd = RcvBuffer - (LastByteRcvd - LastByteRead)
而对于发送方来说，其需要根据接收方发来的rwnd信息，始终保证LastByteSent - LastByteAcked ≤ rwnd，即对于双方来说这都是一个动态的窗口。
当rwnd=0时，若发送方不再发送数据，则无法获取rwnd的更新，故为了避免这个问题，在这种情况下发送方将持续发送只有一个字节数据的报文段。
拥塞控制
拥塞原因
链路容量有限，分组到达速率接近链路容量时会出现巨大的排队时延；
路由器的缓存有限；
资源的浪费，在路由器缓存容量有限的多跳网络中，如果一个分组沿着一条路径被丢弃，那么该路径上参与转发该分组的路由器的缓存资源都浪费了
时延RTT估算算法
指数加权移动平均 EWMA：$EstimatedRTT = (1-\alpha)EstimatedRTT+\alpha{SampleRTT}$
后者为最近的一个样本，在该公式中，一个给定的SampleRTT的权值随着更新呈指数式衰减，例如第一个RTT，权值由1开始，每一轮变为原先的(1-α)倍，α的推荐值是0.125
| 估算SampleRTT与EstimatedRTT的偏理程度（类似方差），同样是一种EWMA：$DevRTT=(1-\beta)DevRTT+{\beta} | SampleRTT-EstimatedRTT | $ ，β的推荐值为0.25 |
综上，我们有以下估算：
$TimeoutInterval=EstimatedRTT+4*DevRTT$
这样，这个值将比EstimatedRTT大（避免不必要的重传）但又不至于大太多（确保效率）。
推荐的初值为1秒。
RTO计时器管理
RTO（超时重传机制）
当出现超时后，TimeoutInterval将变为原值的两倍，直到收到新的SampleRTT再根据原值计算。
TCP Reno
动态调整CWND，cwnd的单位为MSS
对于发送方，其发送速率将受限于RWND和CWND（通常RWND远大于CWND）
慢启动
在TCP连接刚刚建立时，CWND++ per ACK，即每个RTT，CWND*=2
当CWND大小超过ssthresh（设定的阈值）后，结束慢启动，转入拥塞避免
*ssthresh的初值一般为65536
拥塞避免
AIMD原则（加性增乘性减）
CWND += 1/CWND per ACK，即每个RTT，CWND++
当发生丢包时（三个dupACK），ssthresh变为CWND的1/2，CWND变为ssthresh
当超时，ssthresh变为CWND的1/2，CWND变为1，重新进入慢启动阶段
快恢复
在收到三个dupACK会触发快速重传机制，快恢复认为，既然能收到三个dupACK说明网络情况不是那么糟糕，这个重新发送的包应该会正常到达，故如果仍然变为ssthresh后加性增，可能浪费了许多带宽
当发生丢包时，ssthresh变为CWND的1/2，CWND变为ssthresh+3（考虑了之前的三个冗余ACK）
之后，每收到一个dupACK，CWND+=1
当收到新的ACK时，退出快恢复，重设CWND = ssthresh，退出快恢复，转入拥塞避免
*快恢复时若超时，同样会将ssthresh变为CWND的1/2，CWND变为1，进入慢启动
流量控制与拥塞控制的区别
流量控制针对的是发送方和接收方速度不匹配的问题，是端到端，由接收方控制，发送方被迫同步
拥塞控制制全局网络的速率，由发送方主动根据当前网络情况调整发送数据
数据网络中的拥塞控制
网络吞吐率的特征
如上图，在这样一段过程中，总共发了A个报文（纵轴cwnd的大小，横轴时间，面积即为数量），然后遇到了一个丢包，故丢包率为1/A，在这段时间中CWND增长了W~max~/2，在拥塞控制过程中每个RTT，CWND+=1，故总用时为RTT*W~max~/2，吞吐量就能算出来了。$\sqrt{\frac{3}{2}}$ 约为1.22
上述式子可以转换为：$B=\frac{0.75W_{max}}{RTT}$
路由器协助的拥塞控制
抑制分组
当发生拥塞时，路由器用ICMP报文告诉发送方，使其降速
反压
当发生拥塞时，路由器告诉上一跳路由器，使其降速
警告位 warning bit
路由器在检测到拥塞时，在收到的数据包上加上警告位，让其自行处理
随机早期丢弃 RED
为了避免同时丢包造成大家的窗口同时折半，浪费带宽
在路由器缓冲区满之前，随机丢包让某些链接速率先降下来
引入MinThresh和MaxThresh
路由器缓存小于MinThresh时不丢包，两者之间以概率p随机丢包，大于MaxThresh全部丢包
公平性
公平队列
当存在多个并行的TCP连接时，使用fair queue确保分得近似相等的带宽
方法：假设数据按bit一个一个到来（而不是packet），在这种情况下按照其离开时间为其排序，再根据这个顺序安排包的服务顺序
网络服务质量QoS
不同类型的应用对QoS的要求不一样
弹性流量：email等
非弹性流量：语音聊天、视频等，必须及时到达，但允许一定的丢包
尽力而为服务：在网络接口发生拥塞时直接丢包
综合服务体系 ISA
将服务分等级，优先队列+普通队列，实现在路由器上，实行RSVP协议，进行资源预留
缺点：①需要所有路由器都支持；②代价高；③复杂
区分服务体系 DS
用户和运营商签署SLA服务级别协议，只能使用在一个运营商（ISP）内
流量整形
控制速度不超过某阈值
漏桶
控制初速度恒定
令牌桶
令牌桶大小恒定，以一定速率生产令牌，桶中可以保存的最大令牌数永远不会超过桶的大小。传送到令牌桶的数据包消耗令牌，消耗数量可以根据大小确定
假设桶大小为b，用户配置的令牌生产速率（即平均发送速率）为r，则在t时间内，最多消耗rt+b个令牌
网络安全
攻击
基本类型：①拦截；②窃听；③篡改；④伪造
被动攻击 ②
难以检测，可以预防
主动攻击 ①③④
可以检测，难以预防
针对攻击 提出需求
①：可用性；②机密性；③完整性；④可认证性
密码学基本术语
明文—加密算法→密文—解密算法→明文
A提供密钥K~A~，和明文m作为加密算法的输入，生成的密文K~A~(m)作为输出
类似的，B提供密钥K~B~，计算K~B~(K~A~(m))=m进行解密
对称加密
发送方、接收方共享同一个密钥
经典算法
凯撒密码、弗吉尼亚密码、篱笆密码（拆成2行交叉）、行列密码（拆成数行，按一定顺序的列重组）
现代算法
块加密 分块进行n轮加密
非对称加密：RSA算法
双方（事实上是所有人）均掌握公钥，某一方掌握私钥
应用场景
设 $K_{A}^{+}$ 为A的公钥，$K_{A}^{-}$ 为A的私钥
- B用 $K_{A}^{+}$ 加密，发送给A，A用 $K_{A}^{-}$ 解密，其他人无法获得内容
- A用$K_{A}^{-}$ 加密，发送给B，B用 $K_{A}^{+}$ 解密，从而证明的确由A发送
密钥生成
- 选两个足够大的素数p，q（一般p在500bit左右，q在1024bit左右），计算N=p*q
- $\Phi=(p-1)*(q-1)$，即为N的欧拉函数（小于或等于n的正整数中与n互质的数的数目）
- 选取e，使得 $GCD(e, \Phi)=1$，即和 $\Phi$ 互质，再选取d，满足 $(d*e)\ mod\ \Phi=1$。（一般选择的e小，d大）
- 公钥为(e, N)，私钥为(d, N)
理论基础
欧拉定理的延申：$\frac{a^i}{N}$ 的余数以 $\Phi(N)$ 为周期，即 $a^i\ mod\ N = a^{i\ mod\ \Phi(N)}\ mod\ N$
${\Rightarrow}\forall{m},m^{ed}\ mod\ N=m^{ed\ mod\ \Phi}\ mod\ N=m\ mod\ N=m$ ①
同时，有
$m^{ed}\ mod\ N=(m^e\ mod\ N)^d\ mod\ N=(m^d\ mod\ N)^e\ mod\ N$ ②
结合上述①②，我们可以知道，对于任意信息m，将其作e次幂运算再mod N，得到信息c，将信息c作d次幂运算再mod N，将还原出m；同理，先做d次得到s，再作e次也能还原出m
使用方法
A：掌握公钥，即知道e、NA
B：掌握私钥，即知道e、d、NB
现在假设发送的信息为m
| 用途 | 保密信息 | 验证身份 |
|---|---|---|
| 加密者 | A | B |
| 加密方式 | c = m^e^ mod N | s = m^d^ mod N |
| 解密方式 | m = c^d^ mod N | m = s^e^ mod N |
由于RSA较费时，一般只在密钥分发时用于让双方共享密钥，之后的对话使用对称加密
报文鉴别与散列函数
保证数据的完整性和可鉴别性
密码散列函数
要求：找到两个不同的x和y，使得H(x) = H(y)，在计算上是不可能的
但是，可以存在x和y，H(x) = H(y)
常见的散列函数算法有MD5、SHA-1等
报文鉴别码 MAC
A和B共享密钥s，A发送m给B，则级联m和生成m+s，h = H(m+s)，发送扩展报文(m, h)
Bob收到报文(m, h)后，自己计算H(m+s)，并与h比较，若相同则报文完整
为什么要有密钥s？
若仅计算H(m)，由于H()是统一的，C可以将报文由(m, H(m))篡改为(m’, H(m’))
端点鉴别
回放攻击
攻击者向B发送一个已经发送给B的包（这个包是窃听得到的），从而达到欺骗目的
解决方法：引入不重数nonce，是一个在一个协议的生存期中只使用一次的数
中间人攻击
中间人位于A和B之间，然后进行拦截数据——修改数据——发送数据的“会话劫持”过程，从而让双方误以为在和对方通信
解决方法：CA、防止劫持
公钥系统
数字签名
发送者使用自己的私钥加密报文，接收者用公钥解密从而认证
由于报文很长，一般加密其散列函数，即 $K_{A}^{+}(H(m))$
安全的密钥分发：Diffie-Hellman密钥交换协议
双方共享一个足够大的素数p，且其一个原根为g
*原根：若a模n的阶为φ(m)，则称a为n的一个原根
*a模n的阶：使得 $a^x≡1(mod\ n)$ 成立的最小正整数x，即 $a^x\ mod\ n=1$
*原根的性质：假设一个数g是P的原根，那么g^i^ mod P的结果两两不同（i从1到p-1）
过程：
- A、B分别选取了数x、y
- A计算 $X=g^x mod\ P$，B计算 $Y=g^y mod\ P$
- A将X告诉B，B将Y告诉X
- A、B共享密钥$S=g^{xy}mod\ P=Y^xmod\ P=X^ymod\ P$，等式的后两部分为A、B计算得到S的方法
- 在这个交换过程中，P、g、X、Y都是外界可知的，然而S却仅能被A、B计算出
DH算法会受到中间人攻击
认证中心 CA
认证中心作为权威机构，用其私钥加密A的公钥，作为A的数字证书，任何人都可以从CA那里获取其（绝对正确的）公钥，解密得到A的公钥
安全电子邮件系统
加密过程：
解密过程：
B在得到扩展报文(x, y)后，对y通过 $K_B^-$ 获得对称密钥 $K_S$，对x使用 $K_S$ 得到扩展报文 $(m,K_A^-(H(m)))$，通过 $K_A^+$ 得到H(m)（同时也鉴别了发送方），与m计算得到的H(m)进行比对，从而确认报文完整性
*上述公钥均由CA验证
各层的安全协议
传输层 SSL
SSL：安全套接字层，用于建立运输层安全性(TLS)连接
SSL握手：
- Client hello：A发送它支持的密码算法列表和一个不重数
- Server hello：B选择一个对称算法和一个非对称算法和一个MAC算法，将选择和自己的证书连同一个不重数发送给A
- Cipher-spec：A验证该证书，提取公钥；生成前主密钥PMS；将PMS用B的公钥加密发送给B
- B提取出PMS；A和B独立地用两个不重数和PMS，组合生成主密钥MS，该主密钥被生成2个密码E~A~、E~B~和2个MAC密钥M~A~、M~B~
- A发送所有握手报文的一个MAC
- B发送所有握手报文的一个MAC
5和6用于使握手过程免遭篡改，E~A~、E~B~用于数据的加密，M~A~、M~B~用于和数据一起生成MAC
共是四轮握手，发生在TCP建立连接（三轮握手）之后
关闭：发送关闭送SSL记录
网络层 IPSec
AH协议：提供源鉴别、数据完整性
ESP协议：提供源鉴别、数据完整性和机密性服务
VPN：虚拟专用网，提供加密通信
两种分组模式：
设S(m)对m进行加密
运输模式：端——端，数据报：Header+Data→Header+IPSec Header+S(DAta)，即：仅保护Data
隧道模式：端—路由器—路由器—端，
在路由器中，Header+Data→New Header+IPSec Header+S(Header+Data)，即：保护Header和Data
WLan
有线等效保密
40位对称密钥+24位初始向量IV组合生成密钥k~i~，IV在每一个帧中都不同，因此有k~1~、k~2~、k~3~……
缺点：IV可能相同，如果攻击者监测到某次相同的k且其知道这个k第一次出现时的明文内容d1（可以通过不断要求服务器发送已知文件），由于c1=d1⊕k，c2=d2⊕k，则c1⊕c2=d1⊕k⊕d2⊕k=d1⊕d2，由于c1、c2、d1均已知，攻击者就得到了d2的内容
运行安全性——防火墙
分组过滤：针对包，按照数据包的特征进行过滤，例如：丢弃所有端口号为80（HTTP）的出分组，从而禁止外部Web访问，丢弃所有ICMP TTL过期，从而防止被Trace route
状态过滤：针对流，例如：禁止从222.22/16发送来的TCP协议数据
最后修改于 2020-8-4