CSE_lecture19:network-end2end
End-to-end Layer: Best-effort is not enough
end-to-end layer
- UDP: 最简化的协议
- TCP: 能保证数据顺序和不丢包，能保证不重复
- RTP: 建立在UDP，用于实时要求
assurance of at-least-once delivery
保证发出的包至少成功一次，在best-effort网络中会为每个包加一个nonce，用于标记是哪个包，发送者会保留包的复制，超时后就可以重传，一直重传直到达到limit times
会面临一个两难问题，即超时是因为包发过去丢失，还是对方的ACK丢失
问题在于怎么确实timeout：
- fixed timer: 无法确定等待时间长还是短，因此绝对不能将时间固定
- adaptive timer: 超时时间适应当时的网络环境，可以设置为RTT(往返时延)的150%，或者设置为上次失败时延的两倍
- NAK: 与ACK相反，即接收者主动说明自己没收到的包，这样timer放在接收者，重发由NAK决定
assurance of at-most-once delivery
接收者记住自己曾受到过的包，当再次收到这个包时就不必再处理这个包。但这样可能导致表无限增长，因此难点在于怎么设置tombstone；或者由应用设置幂等性的操作
问题在于怎么做duplicate suppression：
- 记录水位，但默认包按照nonce的顺序，这样只用记录一个数字，但old nonce会成为tombstone
- 使用一个新的端口接收新的请求，即不再使用已经用过的端口，但old port会成为tombstone
但当接收者崩溃重启后，这些duplicate suppression会丢失，而写入磁盘又会导致性能下降，因此tombstone会占用资源。因此最好由应用层支撑幂等性
实践上在5个RTT之后删除记录的包（即发送者和接收者达成了协议），避免接收者记录过多东西
assurance of data integrity
为了保证数据完整性，需要添加checksum
segments and reassembly of long messages
对于长消息需要拆分和合并，此时会有类似于”message 914, segment 3 of 7”的标识，这个标识也可以用于at-least-once和at-most-once的编号
但多个长消息的分块可能出现乱序：
- 接收者只ACK in-order的包，抛弃其他包
- ACK所有的包并缓存它们，直到全收到再释放缓存并合并，但当坏包出现时，需要非常大的缓存
- 结合前两个方法，维护一个有限的缓存，缓存存不下就丢包，难点在于缓存开多大
为了缓解坏包带来的问题，可以使用NAK，而不是等到坏包超时再重发。而TCP是基于ACK，而不是NAK
assurance of jitter control
每个包到达的时间不完全一样，网络不稳定时导致时延突然过大。解决策略为缓冲，等待一会儿
缓冲的大小为：$Number_ of_ segment_ buffers = \frac{D_{long} - D_{short}}{D_{headway}}$，即统计一段时间内的最长时延和最短时延，相减并除以平均值
assurance of authenticity and privacy
保证网络的安全性，因此需要身份验证。传统的方法为密钥加密，分为对称加密和非对称加密，非对称加密性能很差，用于建立连接时，后续使用对称加密
end-to-end performance
考虑性能的同时需要保证网络不崩溃
使用lock-step protocol很直观，但会导致发送者和接收者出现大面积的闲置时间，浪费带宽
pipelining technique会在发送一个包后继续发第二个包，但全力发包可能导致接收者无力承受，需要两边进行协商，此外也可能导致包的丢失
为了协商速度，引入fixed window，即在发包之前协定发送包的数量。但会出现idle
因此在收到ACK时就可以发新的包了，即sliding window
当有包丢失时，滑动窗口会卡住，直到超时重发并ACK，这是为了防止维护一个过大且未知大小的缓存
window size的大小公式为：$window_ size \geq round_ trip_ time \times bottleneck_ data_ rate$
TCP congestion control
network layer可以直观体验到拥塞，但发送速度是由end-to-end layer控制的
当load过大时，不仅会出现拥塞，甚至会出现倒塌(collapse)，成功率反而急速下降
为了控制拥塞，window size的另一个公式为：$window_ size \leq min(RTT \times bottleneck_ data_ rate, receiver_ buffer)$
拥塞控制的基本思想(AIMD)为：缓慢线性增加congestion window，即没有丢包就加一，一旦丢包指数减小，即除以二。当有多个发包和收包的人时需要保证公平性
AIMD的问题在于初始值不能太小，否则会导致浪费
retrofitting TCP的步骤为：
- slow start: 开始时指数上升，每次给window size乘二
- 接收者发现乱序时，发送一个duplicate of latest ACK，发送者收到时window size除以二，再每次加一，重复此过程直到平衡
- 超时，等待随机时间，重新开始slow start
为了提高利用率，在window size减小时可以减的少一点，因此在数据中心会单独适配TCP
AIMD通过反复调整可以自动保证多个发送者的公平性，即不需要各个节点协商专门调整。这也是为什么window size下降时需要减半
TCP的缺点在于：
- 路由器buffer太大会导致长的延时
- 丢包不一定由拥塞导致，如wifi在丢包后反而应当发得快一些
- 在数据中心时TCP做的不够好，即减半导致利用率低，需要自行适配TCP
- 对于长RTT的网络存在偏见，因为吞吐量会下降