一周总结(二)

发表于 | 更新于

前言

迟到了好久的总结。。。本部分为计算机网络。

计算机网络

  1. 信道利用率
    $$ Efficiency = \frac{Transmission\ time\ of\ packet}
    {Transmission\ time\ of\ packet + 2 * Propagation\ delay} $$
    1. A channel has a bit rate of 4 kbps and one-way propagation delay of 20 ms. The channel uses stop and wait protocol. The transmission time of the acknowledgement frame is negligible. To get a channel efficiency of at least 50%, the minimum frame size should be:
      • 这道题中可以设传输时间为x，由上述公式，得：
        $$ 0.5 = \frac{x}{x+2*20*10^{-3}} $$
        得x=\( 40*10^{-3}\)，再结合bit rate为4 kbps得到结果为160bits
    2. 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, and 127? The earth-satellite propagation time is 270 msec
      • 一个传输周期T = 第一个帧的传输时延+第一个帧的传播时延+确认帧的传输时延+确认帧的传播时延
        这里不考虑确认帧的传输时延，但考虑传播时延。计算得周期T为 \( 270*2+512Byte/64kbps=604ms \)。
        发送一帧为64ms，因此需要604/64=9帧保持通道不空。每604ms发送(窗口值*512Byte*8)bit,
        注意这里的窗口值若超过9(如15、128)，吞吐量也只是最大值64kbps。
  2. T1速率125us传送193位的帧
  3. CRC的checksum是多项式的最高次幂
  4. sequence number(n) 与maximum number of outstanding sending frames(M)的关系
    • go back N: $$ M = 2^n - 1 $$
    • selective repeat $$ M = 2^{n-1} -1 $$
  5. Wait and Stop、 Go back N 和 Selective repeat总结
    这三种实际上是发送窗口与接收窗口大小的区别。发送方将窗口里的帧挨个发送，如果收到nck或者当计时器超时时未收到ack，就重新发送该号帧。发送方接收到AckRn，则表示AckRn之前的帧已经被接收方收到。接收方将帧按号放入接收窗口，并发送ack，当接收到的帧与接收窗口当前的号不同时，就返回nak，表明有帧未收到需重传。窗口大小与sequence number的bit位数有关。发送方维护一个Slast(\( S_n \))，表明将要发送的帧，每发送完一帧后更新值+1，接收方维护Rnext(\( R_n \)),每接收到一帧后更新值+1。
    1. Wait-and-Stop
      • 发送方与接收方窗口大小均为1。
      • 发送方按照Sn发送帧，启动计时器，并更新Sn。发送方比较ack与Sn确认帧被接收，可以发送下一帧，并停止计时器。当计时器超时，发送方重新发送Sn帧，并重新启动计时器。
      • 接收方没有计时器。每当接收到帧，就比较帧号与Rn是否相等，若是则将该帧上传，并更新Rn，同时发送ackRn。
      • 这种方法效率较低。假设传播延时为τ sec，帧大小为L bits，带宽为r bit/sec，忽略control frame和传输延时则它发送Lbits然后等待至少2τ+L/r sec。
    2. Go-Back-N
      • 发送方的窗口为小于2m(不能等于)，接收方的窗口大小为1。m为sequence number 的bit位数。
      • 发送方需要维护Sf，表示最后发送的帧号。Sf与Sn的差要小于窗口大小。发送方发送帧后，更新Sn，如果此时计时器未启动，则启动计时器。发送方接收到ack后要判断ack在发送窗口中，然后更新Sf为ack+1，并停止计时器。如果计时器超时，则重新启动计时器，并重新发送Sf与Sn之间的帧。
      • 接收方与Wait-and-Stop相同。
    3. Selective Repeat
      • 发送方与接收方的窗口最大为2m-1
      • 发送方每个帧都有一个计时器。每发送一个帧，更新Sn，并启动对应的计时器Timern。如果接收到nak在窗口范围(f到n)内，则重新发送nak号帧，并启动timernak。如果接收到的ack在窗口范围内，则停止Sf到ack的计时器，并更新Sf为ack。当某个计时器超时，则重新启动该号计时器，并发送该号帧。
      • 接收方需要维护NakSent(bool，初始为false，表示未发送Nak)。需要维护一个slot数组(大小为窗口大小，初始为false)。维护一个AckNeeded(bool，初始为false，表示不需要发送ack)接收到的帧号不为Rn,并且NakSent为false，则发送NakRn，并置NakSent为true。如果接收到的帧号seqNo在窗口中，并且slot[seqNo]为false(未标记)，则保存该帧，并且标记slot[seqNo]为true。接着若slot[Rn]为true，则上传Rn号帧给上一层，置AckNeeded为true。并使Rn+1，接着判断。接下来，判断AckNeeded，若为true，则发送AckRn，并置AckNeeded和NakSent为false。