CAN201 W5
This is the note of CAN201 Week5.
We will focus on Transport Layer.
Roadmap
- Pipelined communication
- TCP: connection-oriented transport
- Principles of congestion control
Lecture
rdt3.0: stop-and-wait operation
就是之前我们说的停等机制。3.0同时考虑到封包遗失与资料错误的情形，除了使用ACK机制，另外在传送端多了倒数计时器，封包送出去如果超过时间仍未收到ACK或是收到不正确编号的ACK，则再送出封包一次。
Piplined protocols
Pipelining: sender allows multiple, “in-flight”, yet-to-be acknowledged pkts.
- Range of sequence numbers must be increased 序号的范围必须增加
- Buffering at sender and/or receiver 发送端和/或接收端缓冲
Pipelining: increased utilization 管道增加利用率
滑动窗口协议(slide window)
- 发送缓存区
- 形式：内存中的一个区域，落入缓存区的分组可以发送
- 功能：用于存放已发送，但是没有得到确认的分组
- 必要性：需要重发时可用
- 发送缓存区大小：一次最多可用发送多少个未经确认的分组
- 停止等待协议=1
- 流水线协议>1，合理的值，不能很大，链路利用率不能够超100%
- 发送缓冲区中的分组
- 未发送的：落入发送缓冲区的分组，可以连续发送出去；
- 已经发送出去的、等待对方确认的分组：发送缓冲区分组只有得到确认才能删除
发送窗口最大值小于等于发送缓存区的大小
发送窗口每发送一个信息，就往前挪一个，一直挪到发送窗口的后沿，不能超过发送缓冲区。数据收到接受信号之后，就离开发送窗口，窗口移动到后面的数据上。
接受窗口每次只能接受一个信息，接受完之后才能向后滑动，继续接受。
接受窗口
接收窗口 (recieving window)=接受缓存区
- 接收窗口用于控制哪些分组可以被接收
- 只有收到的分组序号落入接受窗口才允许接收
- 若序号在接受窗口之外，则丢弃
- 接收窗口尺寸Wr=1，则只能顺序接收 (GBN协议)
- 接收窗口尺寸Wr>1，可以乱序接收 (Selected repeat协议)
- 但提交给上层的分组，要按序
- 例子：Wr=1，在0的位置：只有0号分组可以接受：向前滑动一个，罩在1的位置，如果来了第2号分组，则丢弃：
GBN和SR的相同和不同点
GBN严格按照顺序进行窗口的移动，接收方没有缓存区和滑动窗口，所以会产生后面重复的发送。SR是无序的传送，不会出现重复的发送，只会发送出现问题的信息，在接收方建立缓存区和滑动窗口，帮助乱序的信息留下来。
GBN: 接收方拓展的FSM
- 只发送ACK：对顺序接受的最高序号的分组
- 可能会产生重复的ACK
- 只需要记住
expectedseqnum: 接收窗口=1
- 对乱序的分组：
- 丢弃 （不缓存）接收方没有缓存
- 对顺序接受的最高序号的分组进行确认 - 累加确认 可能有丢失ack，但是只需要按照最后一个确认就可以了
SR: 选择重传
- 接收方对每个正确接受的分组，分别发送ACKn（非累计确认）
- 接受窗口>1 可以缓存乱序的分组
- 最终讲分组按照顺序交付给上层
- 发送方只对那些没有收到ACK的分组进行重发-选择性重发：发送方为每个未确认的分组设定一个定时器
- 发送窗口的最大值（发送缓冲区）限制发送未确认分组的个数
GBN发送窗口最大值是2^n-1，SR发送窗口最大值是2^(n-1)
SR会出现一些问题，当窗口的大小不合适的时候：
发送方无法确定发送的pkt和自己需要的是否匹配
TCP: connection-oriented transport
TCP: overview
- Point-to-point: 点对点
- one sender, one receiver
- Reliable, in-order byte steam: 可靠的按顺序的字节流
- no “message boundaries” 没有报文边界
- Pipelined: 有滑动窗口
- TCP congestion and flow control set window size TCP拥塞控制和流量控制设置窗口大小
- Full duplex data: 全双工数据 既有累加确认，两方也都有缓存区
- bi-directional data flow in same connection 同一连接中的双向数据流
- Connection-oriented: 会相关联 要握手
- handshaking (exchange of control msgs) inits sender, receiver state before data exchange 握手(交换控制msg)在数据交换前初始化发送方、接收方状态
- Flow controlled: 流控制
- sender will not overwhelm receiver 发送方不会压倒接收方
TCP segment structure
s段是用于三次握手
TCP seq. numbers, ACKs
Sequence numbers: 序列号
- Byte stream “number” of first byte in segment’s data
Acknowledgements: 确认号
- Seq # of next byte expected from other side
- Cumulative ACK
Q: How receiver handles out-of-order segments 接收器如何处理无序段
A: TCP spec doesn’t say, - up to implementor TCP规范没有说，由实现者决定
一个序列号和确认号的例子：
一共发送了三个报文段。第一个报文段是由客户发给服务器，在他们的数据字段里包含一字节的C的ASCII码。然后第一个报文段的序号字段是42。由于客户还没有接受来自服务器的任何数据，因此该第一个字段的确认号字段就是79。
第二个报文段是由服务器发往客户。首先为该服务器所受到的数据提供一个确认。通过在确认号字段中填入43，服务器告诉客户它已经成功接收到了字节42，正在等待43的出现。所以在第二个报文段的数据字段中填入的是C的ASCII码。第二个报文段的序号是79，它是该TCP连接上从服务器到客户的数据流的起始序号，这也正是服务器要发送的第一个字节数据。值得注意的是，对客户到服务器的数据的确认被装载在一个字节的数据。承载服务器到容户的数据的报文段中；这种确认被称为是被捎带（piggybacked）在服务器到客户的数据报文段中的。
第三个报文段是从客户发往服务器的。它的唯一目的是确认已从服务器收到的数据。（前面讲过，第二个报文段中包含的数据是字符C，是从服务器到客户的。）该报文段的数据字段为空（即确认信息没有被任何从客户到服务器的数据所捎带）。该报文段的确认号字段填入的是80，因为客户己经收到了字节流中序号为79及以前的字节，它现在正等待着字节80的出现。你可能认为这有点奇怪，即使该报文段里没有数据还仍有序号。这是因为TCP存在序号字段，报文段需要填入某个序号。
Host A和Host B是相互发送的。
TCP round trip time, timeout
往返时间的估计和超时
这里产生的问题就是：如何设置TCP的超时时间？
首先，必须要比RTT长，但是不同情况下的RTT差异很大；假如太短就会导致提前超时，造成不必要的重传；假如时间太长就会导致反应太慢而造成segment loss.
Q: How to estimate RTT? 如何估计RTT呢？
- SampleRTT: measured time from segment transmission until ACK receipt
- Ignore retransmissions
- SampleRTT will vary, want estimated RTT “smoother”
- Average several recent measurements, not just current SampleRTT
- 公式：
EstimatedRTT = (1- a)*EstimatedRTT + a*SampleRTT(a = 0.125)
如何设置timeout时间：估计RTT加上“安全边际”DevRTT = (1-b)*DevRTT + b*|SampleRTT-EstimatedRTT| (typically, b = 0.25)TimeoutInterval = EstimatedRTT + 4*DevRTT 4*DevRTT=“safety margin”
TCP reliable data transfer
- TCP creates rdt service on top of IP’s unreliable service
- pipelined segments
- cumulative acks 累积ack
- single retransmission timer 单重传定时器
- Retransmissions triggered by: 触发重传的事件
- timeout events 超时事件
- duplicate acks 复制ack
TCP sender events
Data rcvd from app:
- Create segment with seq# 创建段与seq#
- seq# is byte-stream number of first data byte in segment seq#是段中第一个数据字节的字节流号
- Start timer if not already running 开启计时器
Timeout:
- Retransmit segment that caused timeout 重发segment导致超时
- Restart timer 重新启动计时器
Ack rcvd:
- If ack acknowledges previously unacked segments 如果ack确认先前未打包的段
- Update what is known to be ACKed 更新已知被ack的内容
- Start timer if there are still unacked segments 如果仍然有未打包的段开始定时器
TCP sender
这段自己看ppt，最重要的内容是TCP的三次握手和四次挥手。
Principles of congestion control
看b站 笔记要抄的太多了 b站写的很详细。
中科大郑烇、杨坚全套《计算机网络（自顶向下方法 第7版，James F.Kurose，Keith W.Ross）》课程
References
- XJTLU slides CAN201
- 中科大郑烇、杨坚全套《计算机网络（自顶向下方法 第7版，James F.Kurose，Keith W.Ross）》课程
- 计算机网络 自顶向下方法.原书第6版