这篇笔记主要记录：

  1. 提供可靠传输的两种技术

    1. Acknowledgements
    2. Timeout

  2. Stop-and-Wait Protocol

    这种协议能提供可靠传输，但是效能堪忧：

    1. 有且仅有一个封包在外传输
    2. 可能会收到重复封包

  3. Sliding Window Protocol

    这种协议能提供可靠传输，且效能很好

    1. 每一个封包上都会添加一个sequence number，滑动窗口的工作方式建立在这个序号的基础上
    2. 同时可有多个封包在外传输(keeping pipefull)
    3. sender(window的滑动时机)
      1. Sending Window Size(SWS) = delay * bandwidth
      2. Last Acknowledgement Received(LAR)
      3. Last Frame Sent(LFS)
    4. Receiver(window的滑动时机)
      1. Receiving Window Size(RWS) = 1 or SWS
      2. Largest Acceptable Frame(LAF)
      3. Last Frame Received(LFR)

  4. SWS和RWS可以不相等

  5. 如果RWS = SWS，最好让SWS < (MaxSeqNum + 1) / 2，否则，receiver可能会收到重复封包

  6. Acknowledgement机制的实现方式视具体实现而定，常用的有：

    1. NAK
    2. Cumulative acknowledgement

  7. Sliding Window protocol 提供了三个特性

    1. 提供可靠传输
    2. Perserve order，虽然在传输过程是无序的，但是往上一层协议送的时候是有序的
    3. 流量控制，receiver determines the RWS

可靠传输

借助2个实现机制：

  • Acknowledgements: An acknowledgement(ACK) is a small control frame(无data) that a protocol sends back to its peer saying that it has received the earlier frame
  • Timeouts: The action of waiting a reasonable amount of time is called a timeout(超时后就要重送)

这两个又被称为 Automatic Repear reQuest(ARQ)

Stop And Wait Protocol

工作原理：

  1. After transmitting one frame, the sender waits for an acknowledgement before transmitting the next frame
  2. If the acknowledgement does not arrive after a certain period of time, the sender times out and retransmits the original frame

该协议可能出现四种情况：

  1. The ACK is reveived before the timer expires
  2. The original Frame is lost
  3. The ACK is lost(这种情况会导致Receiver重复收到相同的封包(duplicated frame))
  4. The timeout fires too soon or the ACK is delayed(这种情况也会导致Recaiver重复收到相同的封包)

stopAndWaitProtocol

Stop And Wait Protocol的问题

  1. 因为ACK丢失或延迟导致Receiver重复收到封包(duplicate copies of frames)

    解决办法：使用1bit来给封包编号(0或1)，重送的封包编号如果和前一个相同则会被丢弃

  2. The sender has only one outstanding frame on the link at a time(这会导致链接的效率低下)

    也就是说在1个RTT的时间里，只可能存在1个封包，这个问题没有办法解决，该协议的工作模式就是这样

Sliding Window Protocol

  1. sender要给每一个封包添加一个SeqNum

    SeqNum的大小盲猜是和具体实现有关

  2. sender要维护三个变量

    1. Sending Window Size(SWS)：表示同时可以送多少个封包出去而不用等ACK回来
    2. Last Acknowledgement Received(LAR)：最新收到的连续的ACK的SeqNum
    3. Last Frame Sent(LFS)：最后送的一个封包的SeqNum

  3. sender还要维护下面这个不等式：

    LFS - LAR <= SWS

    下图反应了sender上的sliding window：

    slidingWindowOnSender

  4. 当1个ACK返回

    The sender moves LAR to right, thereby allowing the sender to transmit another frame

  5. sender也会给发出的每一个封包关联一个timer

    It retransmits the frame if the timer expires(lost or delay) before the ACK is received

  6. sender还需要buffer SWS个frame 以防重送

  7. 什么时候允许窗口滑动

    当编号LAR+1的ACK收到时，就允许窗口滑动

    timeToSlidingWindowOnSender

    上图中，2~6封包无序收到ACK，只有但2号收到ACK，形成一片连续ACK时，窗口才回移动，如果此时sender有封包要送，就可以使用9~13进行封包的发送

    最好的涉及就是window一直在滑动

  8. Receiver端也会维护3个变量

    1. Receiving Window Size(RWS): Upper bound on the number of out-of-order frames that the receiver is willing to accept
    2. Largest Acceptable Frame(LAF): Sequence number of the largest acceptable frame(可接收的最大值)
    3. Last Frame Received(LFR): Sequence number of the last frame received(连续收到的最近的一个)

  9. Receiver端也会维护下面的不等式

    LAF - LFR <= RWS

    下图反应了receiver上的sliding window：

    slidingWindowOnReceiver

  10. 当一个带有SeqNum 序列号的封包到达Receiver时，Receiver是如何处理的

    1. if SeqNum <= LFR or SeqNum > LAF, discard it(the frame is outside the receiver window)
    2. if LFR < SeqNum <= LAF, accept it

  11. Receiver端的窗口滑动时机

    当编号LFR+1的ACK收到时，就允许窗口滑动

    timeToSlidingWindowOnReceiver

  12. Cumulative Acknowledgement

    1. SeqNumToAck：还没有回复的Sequence number的最大值
    2. The receiver acknowledges the receipt of SeqNumToAck if high-numbered packets have been received

    回复的这个ACK表示说Sequence number小于SeqNumToAck的封包通通都收到了

Sliding Window Protocol的问题

  1. 发生超时时，sender发送的数据量就会下降

    ack没有回来，window就不能滑动

  2. When the packet lost occurs, this scheme is no longer keeping the pipe full

    The longer it takes to notice that a packet loass has occurred, the more severe the problem becomes

    因为window会暂停，只要暂停就不会有新的sequence number用于发送新的封包，时间越长，throughout就越差

    有三种方式用来改善上述情况：

    1. Negative Acknowledgement(NAK)：封包错误返回ACK
    2. Additional Acknowledgement
    3. Selective Acknowledgement: receiver收到什么编号的封包就返回什么编号的ACK

  3. 如何选择window size

    1. SWS： delay * bandwidth
    2. RWS通常有两种选择方法
      1. RWS = 1：No buffer at hte receiver for frames that arrive out of order
      2. RWS = SWS：The receiver can buffer frames that the sender transmits
      3. RWS > SWS没有意义：因为sender 发送封包的最大量就是SWS个，RWS比SWS多出来的位置用不到

  4. Sequence number是有限的，当封包数量很大时，可能遇到需要重复使用的情况
    解决办法：

    1. 可以用的sequence number的数量一定要大于在外面跑的封包的数量
    2. MaxSeqNum：当前可以使用的sequence number的上限值，sws + 1 <= MaxSeqNum
    3. 如果RWS = 1, 上面的方法能解决

    4. 如果RWS = SWS，上面的方法不足以解决

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      sequence number: 0, 1, 2, 3, 4, 5, 6, 7
      RWS = SWS = 7 = 8 - 1

      1. Sender sends 0, 1, ..., 6
      2. Receiver receives 0, 1, ..., 6
      3. Receiver acknowledges 0, 1, ..., 6，但是ACK(0~6)丢失
      4. Sender timeouts and retransmits 0~6
      5. Receiver is expecting 7, 0, ..., 5
      6. frames 0~5 will be accepted(duplicated)
      7. frames 6 will be discarded(correct)

      为了解决上述的问题，当RWS = SWS时，需要设定SWS < (MaxSeqNum + 1) / 2， 也就是不能大于一半的数量

Sliding Window Protocol的特性

  1. 提供可靠传输
  2. Preserve order
    1. Each frame has a sequence numebr
    2. Out of order frames will be buffered
  3. Flow Control
    1. Receiver is able to throttle the sender by setting the values of RWS(sender可以送多快是由receiver决定的)
    2. Keeps the sender from overunning the receiver(不在Receiver窗口范围内的封包不收，会导致Sender方封包的timeout，重送把流量降下来)