通信协议详解：平衡滑动窗口协议分析

### 通信协议详解：平衡滑动窗口协议分析 #### 1. 通信协议概述 在数据通信中，两个计算站之间可靠地交换数据并非易事。理想情况下，数据只需通过发送和接收消息就能完成交换，但实际通信中，错误是不可忽视的。消息通过物理介质传输时，可能会出现丢失、重复、乱序或损坏的情况。为了检测和纠正这些错误，需要在计算站中实现一些补充机制，即协议。 这些协议的主要功能是数据传输，包括在一个站点接收信息并在另一个站点交付。可靠的数据传输涵盖了对丢失消息的重发、对损坏消息的拒绝或纠正，以及对重复消息的丢弃。为了实现这些功能，协议需要维护状态信息，记录哪些数据已发送、哪些数据已被确认接收等。这就引出了连接管理的问题，即状态信息的初始化和丢弃，分别对应连接的打开和关闭。连接管理的难点在于，当连接关闭时，消息可能仍留在通信通道中，这些消息的接收不能干扰当前连接的正常运行。 本文讨论的两个协议是为协议层次结构中的不同层设计的，例如类似 OSI 参考模型中的层。第一个协议完全异步，第二个协议依赖于定时器的正确使用。在这两种情况下，协议的验证都集中在所需的安全属性上，即接收方只交付正确的数据。 第一个协议适用于具有直接物理连接（如电话线）的两个站点之间的数据交换，属于 OSI 模型的数据链路层。第二个协议适用于必须通过中间网络（可能包含其他站点，并通过不同路径连接端点站）进行通信的两个站点，属于 OSI 模型的传输层。这种差异在以下两个方面影响了协议的功能： - **考虑的错误类型**：两个协议考虑的传输错误类型不同。在物理连接中，消息不能相互绕过，也不会重复，第一个协议只考虑消息丢失的情况（消息损坏实际上也会导致消息丢失，因此不单独处理）。而在网络中，消息可以通过不同路径传输，可能会相互绕过，并且由于中间站点的故障，消息可能会重复或丢失，第二个协议会考虑消息的丢失、重复和乱序。 - **连接管理**：第一个协议不考虑连接管理，因为物理连接通常会持续很长时间，而不是反复打开和关闭。但对于与远程站点的连接，可能只是临时需要交换数据，长期维护与每个远程站点的连接成本过高，所以第二个协议需要具备打开和关闭连接的能力。 #### 2. 平衡滑动窗口协议 ##### 2.1 协议概述 平衡滑动窗口协议是一种对称协议，允许信息在两个方向上可靠地发送。该协议用于通过线路直接连接的站点之间的信息交换，可假设通道具有先进先出（FIFO）属性，但该假设直到后面才会用到。 两个通信进程分别用 p 和 q 表示，协议关于 p 和 q 完全对称。进程 p 的输入是要发送给 q 的信息，用无限数组 inp 表示；输出是从 q 接收的信息，用无限数组 outp 表示。同样，进程 q 的输入和输出分别用数组 inq 和 outq 表示。这些数组都由自然数索引，从 0 开始。协议要求随机访问 inp 和 outp，但后续会证明可以将随机访问限制在一个有限长度的“窗口”内，这也是该协议被称为“滑动窗口”协议的原因。 进程 p 包含一个变量 sp，表示 p 仍期望从 q 接收的编号最低的字。因此，在任何时候，p 已经写入了 outp[0] 到 outp[sp - 1]，且 sp 的值不会减小。类似地，进程 q 包含变量 Sq。协议的所需属性包括安全属性和活性属性： - **安全交付**：在协议的每个可达配置中，outp[0 .. sp - 1] = inq[0 .. sp - 1] 且 outq[0 .. Sq - 1] = inp[0 .. sq - 1]。 - **最终交付**：对于每个非负整数 k，最终会达到 sp ≥ k 且 Sq ≥ k 的配置。 ##### 2.2 协议呈现 传统的传输协议通常依赖确认消息，发送方若未收到确认消息，会假设数据消息或确认消息丢失并重新发送。但本协议不使用显式的确认消息，两个站点的消息同时充当对方消息的确认。 进程交换的消息称为数据包，格式为 (pack, w, i)，其中 w 是数据字，i 是数据包的序列号。当 p 发送该数据包给 q 时，它传输了字 w = inp[i] 给 q，同时也确认了从 q 收到的一些数据包。具体来说，p 发送的数据包 (pack, w, i) 确认了从 q 接收的编号为 0 到 i - fp 的字。常数 fp 和 lq 是非负的，且两个进程都知道。数据数据包作为确认的隐含含义对协议的转换有两个影响： - 进程 p 只有在存储了 outp[0] 到 outp[i - fp] 中的所有字后，才能发送 inp[i]（作为数据包 (pack, inp[i], i)），即 i < sp + fp。 - 当 p 收到 (pack, w, i) 时，不再需要重发 inp[0] 到 inp[i - lq] 中的字。 以下是协议的伪代码（以进程 p 为例）： ```plaintext var sP, Up : integer inp : array of word outp : array of word Sp: { Up <= i < sp + lp } init 0, 0 ; (* Data to be sent *) ; init udef, udef, ... ; begin send ( pack, inp[i], i ) to q end Rp: { ( pack, w, i ) E Qp } begin receive ( pack, w, i ) ; if outp[i] = udef then begin outp[i] := w ; Up := max (Up, i - lq + 1) ; sp := min { j | outp[j] = udef } end (* else ignore, packet was retransmission *) end Lp: { ( pack, w, i ) E Qp } begin Qp := Qp \ {( pack, w, i )} end ``` 在上述代码中，变量 Op 用于指示进程 p 尚未收到确认的编号最低的字。动作 Sp 表示 p 发送第 i 个字，动作 Rp 表示 p 接收一个字，动作 Lp 表示目的地为 p 的数据包丢失。 通信子系统由两个队列表示，Qp 用于目的地为 p 的数据包，Qq 用于目的地为 q 的数据包。为了证明该算法满足前面提到的要求，需要证明断言 P 是一个不变量： ```plaintext P == ∀i < sp : outp[i] != udef (Op) ∧ ∀i < Sq : outq[i] != udef (Oq) ∧ ( pack, w, i ) E Qp => w = inq[i] ∧ (i < Sq + lq) (1p) ∧ ( pack, w, i ) E Qq => w = inp[i] ∧ (i < sp + lp) (1q ```