2 数据链路层
功能
向网络层提供well-defined服务接口，表现为 无差错 的链路
成帧(Framing)
字节计数法(byte count)： 不可靠，因为计数值也可能出现错误
Flag bytes: 使用特殊字符FLAG标志帧的开始和节数。 但是需要转义字符ESC. 如果数据里面有FLAG,就变成ESC FLAG。如果数据里面有ESC,就变成ESC ESC。(类比字符串的\)
Flag bits: 每个帧的开始和结束用序列 01111110 (0x7E) 标识，同时发送方每发现连续的 5 个 1，发送时就在其后面添加一个 0 (这样就不会出现连续6个1）；接收方在发现 111110 时将最后一个 0 舍弃。这种技术称为 比特填充 bit stuffing。
Physical layer coding violations: 对于 曼彻斯特编码 和 4B/5B，有相当一部分信号组合是不可能出现的。我们可以使用这样的信号组合作为帧的开始和结束
Example
A bit string, 0111101111101111110, needs to be transmitted at the data link layer. What is the string actually transmitted after bit stuffing?
答: 011110111110011111010 (不用写头尾的标识符)
错误控制
- 码字（codeword）：n(码字) = m(数据位) + r(冗余位)
- 码率（code rate）：m / n
海明距离Hamming distance: 一个码字要出现 d 个 1bit 的错误才会变成另一个码字。
d个bit检错码: 海明距离为d+1 d个bit纠错码: 海明距离为2d+1
n个bit的数据 用海明码检验 k位冗余信息 则\(n+k\leq 2^k-1\)
纠错
容易出错的(无线通信)/单工信道
检错
错误率较低的时候，只需要检测出错然后重传。如光纤
CRC
循环（Cyclic Redundancy Code,CRC)
模二运算不考虑进位和借位。模二加法=模二减法=异或 模二除法部分余数相减时按模二减
- 发送方和接收方在通信前，约定好一个r+1位二进制数G作为除数。 要求: 开头和结尾都是1 (具体还有很多细节,略)
- 发送方确定一个r位的CRC码 使得Frame拼接上CRC之后模二除以G余数为0。那么就在Frame后面补r个0, 模二除以G, 余数就是CRC。把Frame拼接CRC (m+r bits )发送
- 接收方收到m+r bits, 模二除以G, 如果余数为0,就是正确的。否则错误
Example
发送方 
奇偶校验就是一位的CRC
Example
What is the remainder obtained by dividing x^7 + x^5 + 1 by the generator polynomial x^3 + 1? (give your answer as bit string)
答:111 (记得先补3个0)
Generator=\(x^8+x^3+1\), How many bits of checksum? 答: 8 (最高次数为\(x^r\),余数就是r位,除数r+1位)
流量控制
停止-等待
两种差错
- 发送的数据损坏，被接收方丢弃
- 数据成功发送，但是收不到确认帧
发送方增加一个计时器(timer)，如果经过一段时间没有收到接收端确认，发送方将超时，于是再次发送该帧。发送方每次发送1个帧，收到确认帧后重传。序列号只有0/1两种。ACK0/ACK1表示收到了0/1帧。如果出现2个相同序列号，就说明是重传
\(W_T=W_R=1\)
Example
A channel has a bit rate of 4 kbps and a propagation delay of 20 msec. For what range of frame sizes does stop-and-wait give an efficiency of at least 50 percent? 答: 160
滑动窗口
\(T_D\)是数据发送时间。RTT是 往返 延迟, \(T_A\)是接收端收到数据到返回ACK的时延(可忽略) 信道利用率: 当 \(nT_D<T_D+RTT+T_A\)
当\(nT_D \geq T_D+RTT+T_A ,U=1\)
Warning
- 往返时间\(RTT=2*t_{prop}\)
- \(T_D\)是数据发送时间=\(\frac{M}{W}\) M是每个frame的bit数，W是信道带宽(单位bps)
- 平均传输速率=信道利用率×信道带宽 \(\boxed{=\frac{nM}{T_D+2t_{prop}+T_A}}\)
- 注意帧长单位一般是字节 但传输速率是bit/s
- \(T_A\)的计算。如果忽略确认帧的传输时延 那么就是0 如果确认帧和数据帧长相同,就跟\(T_D\)一样计算
Example
Consider an error-free 64-kbps satellite channel used to send 512-byte data frames in one direction, with very short acknowledgements coming back the other way. What is the maximum throughput for window sizes of 1, 7, 15? The earth-satellite propagation time is 270 msec. (give your answer as an integer)
注意512-byte是4096b
\(n=1\), \(TP=\frac{1\times 4096}{4096/64000+2*0.27}=6781\) bps
\(n=7\) \(TP=47470\) (上面结果乘*7)
\(n=15\) 信道利用率为100%, 所以\(TP=64000\) bps
回退N帧(GBN)
- 当接收端收到一个出错帧或乱序帧时，丢弃所有的后继帧，并且不为这些帧发送确认
- 发送端超时后，重传所有未被确认的帧
累积确认：不是每收到一个帧就回复。ACKn表示收到第n帧及之前所有的帧
\(1<W_T\leq 2^N-1,W_R=1\)
Example
Assume the sequence number has 5 bits. What is the maximum number of outstanding sending frames for a go back N protocol? 答案：\(2^{5}-1=31\)
Example
After the sender first sends frames from 0 to 6 and at the end of timeout receives the acknowledgements for frame 1, 3, and 5, the next frame it will re-transmit is frame __. (assume the protocol is go-back-n)
答案：6
Example
王道P74原题改了数据,注意这里ackn表示收到的最后一个包是n-1. 发送端同理
- R3,3 表示确认收到0,1,2 3个帧
- 4bit 帧序列号范围0-15 3,4还没确认收到,所以从5到15,以及0,1,2都可以用, 共13个
- R2,2 确认0,1
- 2,3,4都没有收到确认,需要重发。注意发送端的y=3 因为同样表示需要确认序列号为y-1的包
- 1000bit 0.1ms \(n=15,RTT=0.96,T_D=T_A=0.1\) (因为是two-way data transmission,接送方也在发送数据帧,且大小也是1000bit, 同时捎带确认信息) \(\eta=\min(1,\frac{nT_D}{T_D+RTT+T_A})=100\%\)
选择重传(SR)
接收端只把出错的的帧丢弃，其后面的数据帧保存在缓存中，并向发送端回复NAK；发送端接收到NAK时，只重传出错的帧
\(W_T+W_R\leq 2^{n},W_R\leq W_{T}\) 所以取\(2^{n-1}\)
Example
Assume the sequence number has 4 bits. What is the maximum number of outstanding sending frames for a selective repeat protocol? 答案: 8
Which is not the rule of MACA?
- If station X received RTS of station A, X must remain silent for a short time
- If station X received RTS, but did not receive CTS, then X may not transmit its data.
- If station X has not received RTS, but received CTS, then X may not transmit its data
- If station X has received both RTS and CTS, then X may not transmit its data