Summary

  • Learn 6 elementary DLL protocol
  • Learn & master sliding-window
  • Learn & master ARQ（自动重复请求）/PAR
  • Learn & master piggybacking(捎带确认)
  • Learn pipeline
  • Go back n & selective repeat

基本DLL协议

假设

  • 物理层、数据链路层和网络层是独立的进程 -- independent processes
  • 机器 A 想要使用可靠的、面向连接的服务向机器 B 发送长数据流 -- reliable, connection-oriented
  • A的数据链路层请求数据，网络层总是能够立即遵守 -- always able
  • 这些协议处理通信错误，但不处理由计算机崩溃和重新启动引起的问题 -- errors, but not the problems caused by computers
  • 就数据链路层而言，从网络层通过接口传递给它的数据包是纯数据 -- pure data

3 simplex(单工) protocol--三个单工的协议

  • An unrestricted simplex protocol
    • 无限制的单工协议
  • A simplex stop-and-wait protocol
    • 单工的停—等协议
  • A simplex protocol for a noisy channel
    • 有噪声信道的单工协议

Protocol Declaration -- 协议定义

  • 所有常见的数据类型、函数都定义为（protocol.h）
  • NL、PL之间的数据传输

  • Wait_for_event(&event)：等待某事发生
    • fram_arrive,
    • cksum_err,
    • timeout
  • Timer
    • start_timer, stop_timer
    • start_ack_timer，stop_ack_timer
  • 帧的结构

unrestricted simplex protocol 无限制的单工协议

  • 协议一（乌托邦，乌托邦）

  • 数据只在一个方向传输 -- in one direction only

  • 发送网络层和接收网络层都时刻准备着（随时待命）-- are always ready

  • 处理时间可以忽略（瞬间完成）-- Processing time can be ignored

  • 提供无限缓冲空间（无限空间）-- spaces is available

  • 数据链路层之间的通信通道永不损坏或丢帧（完美通道） -- never damages or loses of frames

  • 发送端和接收端处于一个无限的while循环中

Simplex Stop-and-Wait Protocol 单工停--等协议

  • Protocol2 ：放弃不切实际的限制
    • 接收器的处理能力是有限的：接收器只有有限的缓冲容量和有限的处理速度。
    • a finite buffer capacity and a finite processing speed
  • 如何防止发送方用数据淹没接收方？
    • 只需在协议 1 中插入延迟 -- delay
    • 接收者向发送者提供反馈 -- feedback
  • 发送方发送一帧然后在继续之前等待确认的协议称为停止等待 stop and wait
注意
  • 数据流量是单工的，但帧是双向传输的。
  • 两个数据链路层之间的通信通道需要能够进行双向信息传输。
    • 一个半双工（半双工）物理通道就足够了 -- half-duplex
  • 数据流
    • 首先发送方发送一个帧，然后接收方发送一个帧，然后发送方发送另一个帧，然后接收方发送另一个帧，依此类推。

Simplex Protocol for a Noisy Channel 有噪声信道的单工协议

  • 让我们考虑正常情况：通信通道可能会出错。

  • 使用定时器和确认的方案： (timer and ackonwledgement)

    • 发送方在发送一个帧后启动一个定时器 -- starts a timer after sending

    • 只有在正确接收到传入帧时，接收器才会发回确认 -- sends back an ackonwledgement

    • 如果定时器超时，发送方将重传该帧 -- retransmit the frame

  • 主动确认重传 -- Positive Ackonwledgement with Retrasmission

  • 自动重复请求 -- Automatic Repeat Request

PAR(主动确认重传)
  • 上述方案的致命缺陷是什么？
    • 丢失确认 -- Loss of an ackonwledgement
    • 复制帧 -- duplicated frame
  • 如何区分第一次看到的帧和重传？
    • 在每个帧的标题中使用序列号 -- sequence number

改进

  • Improve efficiency of transmission
    • full-duplex （全双工）
    • piggybacking （捎带确认）
    • sliding window （滑动窗口）（flow control）
  • Sliding window protocol
    • Protocol 4：n=1——basic idea of sliding window
    • Protocol 5： Go Back n （回退n帧）
    • Protocol 6： Select Repeat （选择性重传）

full-duplex （全双工）

  • 如何实现全双工数据传输？
    • 两个独立的单工数据通道
    • 双向数据的一个电路
  • 捎带（捎带确认）Piggybacking
    • 暂时延迟传出确认，以便他们可以免费乘坐下一个传出数据帧
  • 接收者应该等待捎带多长时间？
    • 一个特别的方案：等待固定的毫秒数。 （ACK-TIMER）

序列号

  • 序列号与每个传输的帧相关联。 序列号的范围从 0 到某个最大值 (\(2^n - 1\)) 循环。
  • 一个窗口是一个序列号列表 -- window
  • 发送方维护一个发送窗口(sending window)，其序列号对应于已发送但尚未确认或可以发送的帧 (been sent but are as yet not acknowledged, or can be sent)
    • 每当一个新的数据包从网络层到达时，它就会被赋予下一个最高的序列号，并且上边界提前一个。
    • 当确认(ackonwledge)进来时，下边界前进一个。
  • 接收器维护一个接收窗口(receiving window)，其序列号与允许接收的帧相对应。
    • 当接收到序列号等于窗口下边缘的帧时，将其传递到网络层，生成确认，并将窗口旋转一。

  • Receiver：接收帧后，检查序列号是否为frame_expected(期望帧号)，如果是，接收并且frame_expected+1，即滑动接收窗口（接收窗口）。
  • Sender：收到确认帧时，检查ack_number是否为next_frame_to_send，如果是，从network_layer取包，next_frame_to_send+1，即滑动singing_window

w=1 sliding window

Principle of protocol 4 -- 1位传输的滑动窗口

  • 1-bit sliding window protocol （w=1）
  • Window setting 窗口设置
    • Sliding window maximum：MAX_SEQ = 1
    • Initial value：seq =0, ack=1（期待接收seq=0）
  • Window sliding scheme 窗口滑动模式
    • A send frame firstly A发送帧
      • （seq=0, ack=1, A0）
    • B receive A0，send back piggyback-acknowledge B接收帧，发送捎带确认
      • （seq=0, ack=0, B0）
    • A receive acknowledge （to A0），sliding window，send next frame 接收捎带确认，滑动窗口，发送下一帧
      • （seq=1, ack=0, A1）
  • characteristic
    • 序列号seq和确认值ack“0”“1”交替
    • 滑动窗口长度W=1，收到确认才移动窗口
    • 保证按顺序将接收到的正确帧只一次上交网络层
正常情况

不正常情况

duplicated 重复的

error control 差错控制

Line utilization rate of protocol4（信道利用率）

  • 协议 4 中的一个假设：时间可以忽略不计。
    • 向前或向后传输时间
    • 接收器处理传入帧的处理时间
  • 事实上，在低速率信道中，往返时间可以非常大，发送方在此期间被阻塞。
  • 线路利用率：
    • 信道容量为 b bps
    • 帧大小 k 位
    • 往返传播时间 R 秒

  • 例子

代入公式：\(\frac{k}{k+ bR}=\frac{1000}{1000+50000\times0.5}=3.85\%\)

improve line utilization 提高利用率
  • 增加最大滑动窗口尺寸 W：
  • 线路利用率 = \(W\times T_f \ \div \ (T_f+R) = W \times k \ \div \ (k + bR)\)
  • 乌托邦案例：线路利用率达到100%，那么最大滑动窗口大小为：
    • W = $ (T_f+R)   T_f $ = 520 / 20 =26

Pipeline 管道化
  • 允许发送方在阻塞前最多传输 w 帧 -- w frames
  • 每当带宽和往返延迟的乘积很大时，发送端就需要一个大窗口。
    • bandwidth and round-trip-delay is large
  • 长流中间的帧损坏或丢失怎么办？
    • Go back n -- 回退n个
    • Selective repeat -- 选择性重复

Protocol 5：go back n

  • 接收方的窗口大小为1，即接收方只按顺序接受帧。
  • 接收器丢弃发生错误后的所有帧，不发送确认。
  • 超时后，发送方按顺序重传所有未确认的帧，从损坏或丢失的帧开始。

  • 数据帧

  • 工作原理分析

Protocol 6：selective repeat

  • 协议 6 接受无序的帧，但按顺序将数据包传递到网络层。
    • accepts frames out of order
    • 接收序列号在接收窗口内的所有帧
    • 在所有编号较低的帧都以正确的顺序传送到网络层之前，不会将帧传递到网络层。

  • 例子

接收方收到非期望的正确帧－缓存

发送方选择帧seq2重传

接收方收到重传帧seq2－排序上交

Function of NAK
  • Negative acknowledgement (否定确认)
  • 比协议 5 更有效
    • 向发送方发送错误帧的 NAK，强制发送方立即重新发送帧而不是超时