Ch3必考题

1. 拥控

cwnd与threshold变化

a) Identify the intervals of time when TCP slow start is operating. b) Identify the intervals of time when TCP congestion avoidance is operating. c) After the 5th transmission round, is segment loss detected by a triple duplicate ACK or by a timeout d) After the 11th transmission round, is segment loss detected by a triple duplicate ACK or by a timeout e) What is the value of threshold at the 14th transmission round f) What is the value of threshold at the 18th transmission round g) During what transmission round is the 70th segment sent? Assuming a pkt loss is detected after the 27th round by the receipt of a triple duplicate ACK, what will be the values of the congestion window size and of threshold?

分析:可以画出每一时刻的情况

threshhold=1/2cwnd | 19 | 4 | 4 | cwnd==threshold<br />
慢启动->避免 |

| 7 | 19 | 16 | | 20 | 5 | 2 | | | 8 | 20 | 16 | | 21 | 6 | 2 | | | 9 | 21 | 16 | | 22 | 7 | 2 | | | 10 | 22 | 16 | | 23 | 8 | 2 | timeout
threshhold=1/2cwnd | | 11 | 23 | 16 | | 24 | 1 | 4 | | | 12 | 24 | 16 | timeout
threshhold=1/2cwnd | 25 | 2 | 4 | | | 13 | 1 | 12 | | 26 | 4 | 4 | cwnd==threshold
慢启动->避免 |

答案

1. [1,6],[13,16],[17,19],[24,26] 1. [7,12],[19,23] 1. 3dup 1. timeout 1. 12 1. 4 1. 1+2+4+8+16+32+19=82,在第7个round中

2. 流控—GBN

分析如下

丢失) | 0 | 1 | 2 | start | | 20 | 3 | | 240 | | 9 | 10 | 1 | 3 | | | 30 | | | 250 | | 10 | 20 | 1 | 4 | | | 40 | 4 | 1 | 260 | | | 40 | 2 | 收4 | start | | 50 | 5 | 2 | 270 | | | | | 5 | | | 60 | 6 | 3 | 280 | | | 50 | 3 | 收5 | start | | 70 | | | 290 | | | | | 6 | | | 80 | 7 | 4 | 300 | | | 60 | 4 | 收6 | start | | 90 | | | 310 | | | | | 7 | | | 100 | | 4 | 320 | | | 80 | 5 | 收7 | time out | | 110 | | | 330 | | | | | 8 | | | 120 | | 4 | 340 | | | 140 | 5 | 8 | time out | | 130 | | | 350 | | | 150 | 5 | 8 | | | 140 | 5 | | 360 | | | 160 | 5 | 8 | | | 150 | 6 | | 370 | | | 190 | 7 | 收8 | start | | 160 | 7 | | 380 | | | | | 9 | | | 170 | | | 390 | | | 200 | 8 | 收9 | start | | 180 | | | 400 | | | | | 10 | | | 190 | 8 | 6 | 410 | | | 210 | 8 | 11 | start | | 200 | 9 | 7 | 420 | | | 240 | 10 | 11 | | | 210 | 10 | | 430 | | | 250 | 11 | 11 | stop** |

GBN要点⭐
笔记参考: (GBN)回退N步—滑动窗口协议

• sender变化要点
  1. 流控无3dup处理,全靠timer
  2. base,标识已发送但未ack的pkt; nextseq,标识已进入窗口,待发送的pkt
  3. 初始化base=nextseq=1
  4. 每次接收正确ack,base++
  5. 每次新发送pkt,nextseq++
  6. 只有base+N>nextseq才说明窗口有空间,能发送
  7. 接收到任何错误/乱序/冗余ack—>do nothing,等待timer
  8. 当接受到ack n+1没收到ack n,说明ack n遗漏,但receiver已经接收—>累计确认,base = n+2
  9. timer启动/结束:
     1. 初始时base==nextseq—>timer启动接收正确ack后base++,若base==nextseq,说明完毕—>timer结束否则重启timer
     2. 收到其余任何ack,重启timer
  10. timeout发生后,重传不改变base和nextseq
• receiver变化要点
  1. 收到正确pkt n,返回ack n:
  2. 其余任何情况,返回当前正确接收的最大n

3. 流控—SR

题目同2
分析如下

SR要点⭐
笔记参考: SR—Selective Repeat

• sender变化要点
  1. base,标识已发送但未ack的pkt
  2. nextseq,标识已进入窗口,待发送的pkt
  3. 初始化base=nextseq=1
  4. 只有接收到窗口最小pkt的ack,base++(区别)
  5. 每次新发送pkt,nextseq++
  6. 只有base+N>nextseq才说明窗口有空间,能发送
  7. 接收到乱序ack,do nothing,等待timer
  8. timer启动/结束:
     1. 每次发出一个pkt n—>启动timer n
     2. 接收正确ack n时—>timer n结束
  9. timeout n发生后,重传pkt n需重设timer n
• receiver变化要点
  1. 序号[rcv_base, rcv_base+N-1]收到正确pkt n,返回ack n:
     1. 当pkt未被缓存:缓存,且如果pkt序号==rcv_base,则已经连续的已缓存pkt可提交上层:rcv_base==2时,已经缓存3,5,6,此时2,3可被提交
     2. 当pkt已经缓存,返回ack n即可
  2. 序号[rcv-N, rcv_base-1]收到正确pkt n,此时是上一个窗口,必须也返回ack n告知sender
  3. 其余任何情况,忽略 | 解题思路 | | :—-: | |
     1. 读题,确定GBN/SR
     1. 确定所给条件:发送间隔,RTT,timeout,延后,丢包,buffer容量
     1. 分析时不用列出base,nextseq等,时刻关注此时有几个pkt未确定即可判断是否可以继续发送:
     - 题3GBN下,始终出现ack4,此时已经发出的pkt5,6,7无法确定,因此不能再发
     - 题4SR下,出现了ack4,6,7,但此时ack5缺失,sender端窗口依旧5,6,7(base在收到窗口最小pkt的ack时才能base++),因此无法再发
     4. 时刻关注Timer
     - GBN下,初始时启动一次,此后接收任何ACK时,(re)start—>全程一个timer
     - SR下,每发出一个pkt n,start一个timer n—>收到ack n,stop—>全程n个timer
     |

4. RDT综合(1)

可靠性+流控+拥塞控制

分析:由题意可得到 - TCP与GBN的关系: - TCP具有单timer和累计确认的特性 - TCP接收非最小未确认ACK时只重启timer,不发出pkt - cwnd等说明拥控,有3dup - recv有buffer - ACKs for 8th实际指对sender发出的seg7的确认,同时是receiver发出ack8时

①采用慢启动
②起始threshhold=4KB,cwnd=MSS=1KB,rwnd=recB=4KB
③第2个seg的ACK返回时出现延后
④第4个seg丢失
⑤第8个seg后recB缩减为2KB
⑥sender的每个seg发送间隔10ms 首先可以确定的是receiver没有个sender发送data,因此ack一列始终为100 |

初始cwnd=1MSS=1KB,因此只能发送一个seg,大小1K,设置time**r(****每次接收****ack,timer****重置****,****后续省略****)** |   |

| 30 | | seg0抵达,返回:
ack=1k
(实际抵达0-1023,请求1k) | | 60 | 接收ack=1k,cwnd=2MSS,
发出seq=1k | | | 70 | 发出seq=2k | | | 90 | | seg1抵达,返回ack=2K | | 100 | | seg2抵达,返回ack=3K | | 130 | 先接收ack=3k,cwnd=3MSS, 发出seq=3k(**丢失**) | | | 140 | ack=2k抵达,cwnd=4MSS 发出seq=4k | | | 150 | 发出seq=5k | | | 160 | 发出seq=6k | | | 170
/180
/190 | | seg3丢失,seg4,5,6抵达
返回ack=3k,3k,3k
seg4,5,6—>Buffer | | 200
/210
/220 | 接收3k,3k,3k,根据GBN中dup处理,220+100=320,**但220时dup3触发快速重传
重发seq=3k
快速恢复:cwnd=1/2cwnd+3=5MSS
thresh=2 | | | 250 | | seg3抵达,从buffer读出4,5,6,积累ack,返回ack=7k | | 280 | 拥塞避免:接收ack=7k,cwnd=6MSS 发出seq=7k | | | 290 | 发出seq=8k | | | 300 | 发出seq=9k | | | 310 | 发出seq=10k
| seg7抵达,返回ack=8k,此时rwnd=2k | | 320 | min{cwnd,rwnd}=2k,受到流控限制,**暂停 | seg8抵达,
返回ack=9k | | 330 | | seg9抵达,
返回ack=10k | | 340 | 接收ack=8k | seg10抵达,
返回ack=11k | | 350 | 接收ack=9k | | | 360 | 接收ack=10k,解除限制,发送seq=11k | | | 370 | 接收ack=11k | | | 390 | | seg11抵达,接收完成 |

5. RDT综合(2)

对比4,5中接收了乱序ACK

分析:由题意可得到 - ACKs for 7th实际指对sender发出的seg6的确认,同时是receiver发出ack7时

①采用慢启动
②起始threshhold=4KB,cwnd=MSS=1KB,rwnd=recB=4KB
③第2个seg的发送时延后
④第4个seg丢失
⑤receiver接收第7个seg后recB缩减为2KB
⑥sender的每个seg发送间隔10ms 首先可以确定的是receiver没有个sender发送data,因此ack一列始终为100 |

初始cwnd=1MSS=1KB,因此只能发送一个seg,大小1K,设置time**r(每次接收ack,timer重置,后续省略)** |   |

| 30 | | seg0抵达,返回:
ack=1k
(实际抵达0-1023,请求1k) | | 60 | 接收ack=1k,cwnd=2MSS,
发出seq=1k | | | 70 | 发出seq=2k | | | 100 | | seg2抵达,返回ack=1K | | 110 | | seg1抵达,返回ack=3K(累计确认) | | 130 | 先接收ack=1k,重启timer,不发送 | | | 140 | ack=3k抵达,cwnd=4MSS 发出seq=3k | | | 150 | 发出seq=4k | | | 160 | 发出seq=5k | | | 170 | 发出seq=6k | | | 180
/190
/200 | | seg3丢失,seg4,5,6抵达
返回ack=3k,3k,3k
seg4,5,6—>Buffer | | 210
/220
/230 | 接收3k,3k,3k,根据GBN中dup处理,230+100=330,但230时dup3触发快速重传
重发seq=3k
快速恢复:cwnd=1/2cwnd+3=5MSS
thresh=2 | | | 260 | | seg3抵达,从buffer读出4,5,6,积累ack,返回ack=7k同时rwnd变为2K | | 290 | 累计确认,拥塞避免
接收ack=7k,cwnd=6MSS 发出seq=7k | | | 300 | 发出seq=8k ,此时min{cwnd,rwnd}=2k,流控限制 | | | 320 | | seg7抵达,
返回ack=8k | | 330 | | seg8抵达,
返回ack=9k | | 350 | 接收ack=8k,可发送seq=9k | | | 360 | 接收ack=9k | | | 380 | | seg9抵达,接收完成 |

• 一些常用结论 | cwnd和threshold |
  - Timeout:
  - threshold=1/2cwnd
  - cwnd=1
  进入慢启动
  - 3dup:
  - threshold=1/2cwnd
  - cwnd=1/2cwnd+3
  进入拥塞避免 | | —- | —- | | 关于timer |
  - pkt发出,设置timer直到对应ack返回
  - dupACK下,sender do nothing,等待timer
  | | 流控和拥控 |
  - 流控针对末端receiver的buffer
  - 拥控针对路径link
  - 是否能够继续发送seg,需要同时考虑
  1. 非dupACK
  1. min{cwnd,rwnd}
  1. threshold本身无特别影响,只是在慢启动中当cwnd==threshold,告知连接进入拥塞避免
  |