期中复习

概述

未完成——仅根据往年题做了总结，未做其他细节/作业题

体系结构

会话层：主机间通信
表示层：数据表示
应用层：网络应用进程

层次从下往上编号，物理层是第一层

物理层

速度：双绞线<细缆<粗缆<光纤

字节与编码

比特填充法：HDLC协议

0111 1110为首尾标志比特流
内容中出现连续5个1时，则在第五个1后插入一个0——无论不插入是否会构成0111 1110：比如0111 1100 ，倒数第二个0依然是填充进去的，需要被去除，虽然不填它也不会出现6个1

字节填充法：PPP协议无连接

flag为0x**（某个数），转义为0x** (另外一个数)，这构造时在这两个前面都加一个转义，解码时反之
首尾都有flag字节
0x7d：转义。0x7e：帧首尾。 0x7e变为0x7d5e。 0x7d变为0x7d5d。ascii控制字符（ $\leq$ 0x20）前，加0x7d
协议和校验和字段的长度可变

CRC校验码

生成式：多项式，从n次幂到0次幂，系数非0的项为1。如 $X^{3} + 1$ ，则生成式为1001
计算方法：用待发送的比特流，左移生成式位数-1（最高阶），补0，除以生成式（竖式，除的每一步为异或操作），余数即为校验位
检验：收到的比特流除以生成式，不为0即有错。

海明码

纠正单个错误的码字位数下界：m个消息位，r个校验位： $m + r + 1 \leq 2^{r}$
构造：
- 计算r
- 写n=m+r个空，从1~n标下标，1、2、4、……为校验位，空着；其他位左到右依次填入待发送码字
- 将填入的比特中，为1的位的下标异或起来。如：_ _ 1_ 010 则计算3^6=101，那么101填入上面的空格，变为1011 010就是结果。
检验并纠错：
- 如上述正确是1011 010，错一位变成1010 010（错校验还是消息没区别），那么把所有为1的位的下标异或起来，如：1^3^6=100即第四位出错，翻转回来得到正确的。

其他

调制解调器使用字节传输，所以不适用比特填充法
调制解调器上行比下行慢：模拟变数字，信噪比影响，香农公式，受限
ADSL比普通电话线：扩展带宽，3400以上
单模光纤比多模快

ADSL（DMT）

Modem（2.4kHZ）的升级，大大拓宽频率，分成多个信道，从kbps变到mbps
总共1.1MHZ，分到256信道，每个4312.5HZ。4000波特率，15bits/波特
保卫带400hz（不确定）
0信道（低频）是原有的电话线
1-5不使用，隔开数据和语音
2个信道上/下控制，248个信道数据传输

T1链路（PCM）

采样时间为什么设置为 125μs？——话音信道的带宽为4KHz，按照奈奎斯特定理，采样频率应该为带宽的 2 倍，即每秒采样 8000 次，即每 125μs 采样一次。
时分复用TDM
每帧125us，所以8k帧率（波特率/采样率），每帧193bit
0bit为帧编码，然后分24个频道，每频道8bit，其中前7个是数据，8是信号——总之是每波特7bit数据，若指定带宽不是4k，那就是2H*7
速率：8k波特率，每波特24个频道，其中每频道7bit数据+1控制——因此，每频道的速率：8k*7=56k数据，及8k的控制信号。总速率：56k*24=1.536MHZ，加上0bit处的8k速率=1.544Mbps。 （T2为6Mbps，T3为45）

其他计算

p2p信道，数据帧成功概率p，ack不会错，求成功发送的次数： $\sum_{k = 1}^{\infty} k (1 - p)^{k - 1} = \frac{1}{1 - p}$
因为相同设备的接口针脚功能相同,比如1号端口发送2号接受，需要1号对应2号，2号对应一号

存储-转发的分组交换网络

计算包的个数n、计算发送一个包的耗时t，看路径有几跳k(k跳意味着有k段路径，不算首尾k-1个节点，算上首尾有k+1个节点)；
传输(Transmission )耗时： $k * t + n * t$ ：就像cpu的流水线，第一个包发出、第一个包第二跳发出的同时第二个包的第一跳发出……因此可以看成nt+最后一个包再跑了k跳
传播（propagation）耗时：计算d=一段路径的长度L/传播速度V ，然后耗时为 $(k + 1) d$

滑动窗口协议及其计算

效率： $P = \frac{W}{1 + 2 a}$ ，其中 $a = \frac{传播时延 Tp}{传输时延 Tt}$ ，若采用piggy-back捎带确认，则为 $P = \frac{W}{2 + 2 a}$ （因为加了发送一个返回数据包的时间）

停等协议

效率：W=1

有错情况的效率：p为一帧的出错率，则W=1-p

1比特的序号位和没有序号是不同的，后者会有重复帧问题，不能取消

GBN

1、效率：W=窗口长度，当P>1时取1

2、发送0-7，首尾1、2、6的ACK，计时器超时后需要重传几帧？

7号帧一个，因为会发出ACK6，一定意味着0-6全部无误收到

3、窗口长度与序号的关系？

窗口长度<最大序号，即 $[1, 2^{n} - 1]$ 。如序号是0~3，则窗口最大只能是0~2。 若窗口0~3，则发0~3然后ack全丢之后重传0，接收方会认为这是一个新的分组；若为0~2，则接收方期待3却收到0，就知道这个是重传的

4、即RWS接收窗口=1的情况

SR

1、效率：W=窗口长度，同上

2、发送0-3，收到ACK1，0、2超时：谁超时就重传谁，所以02两个

3、窗口长度与序号的关系？

窗口长度 $\leq$ 最大序号范围的一半，即 $[1, 2^{n - 1}]$ 。如序号是0~7，则窗口最大只能是0~3,长度是8/2=4；若序号0~4，则窗口最大是0~1,长度是5/2=2。 如第一种情况，窗口0到4的话，发出01234，ack全部丢失，则接收方认为应该接受56701，此时重传01234，其中的01无法分辨是新的还是重传的（若后者情况，窗口012的话则序号0是重叠的）

4、即RWS=SWS接受窗口=发送窗口的情况

MAC子层

随机接入

ALOHA

纯ALOHA：脆弱期2T（T为传输时间，为包大小d/带宽B），效率 $\frac{1}{2 e} = 18%$ ，完全分散
时隙ALOHA：脆弱期T，效率 $\frac{1}{e} = 37%$ ，需要统一时钟来定位时隙

CSMA/CD

脆弱期2 $τ$ （ $τ$ 为传播到该网段最远处的耗时，常为线缆长度L/传播速度V）
半双工。随机接入的主流

无线网

802.3：曼彻斯特编码，速率=赫兹=码率/2，一次调制10bit，

Ricardo's Wiki