目录
四、可靠数据传输原理 1、Rdt 1.0 2、Rdt 2.0 3、Rdt 2.1和2.2 4、Rdt 3.0
五、流水线机制与滑动窗口协议 1、Go-Back-N（GBN）协议 2、Selective Repeat（SR）协议
传输层协议为运行在不同Host上的进程提供了一种逻辑通信机制（端到端，不需要关心媒介等）。发送方，将应用递交的消息分成一个或多个的Segment，并向下传给网络层。接收方，将接收到的segment组装成消息，并向上交给应用层。
网络层提供主机之间的逻辑通信机制。传输层提供应用进程之间的逻辑通信机制，位于网络层之上，依赖于网络层服务，对网络层服务进行（可能的）增强。家庭类比，12个孩子给12个孩子发信，应用进程=孩子，应用消息=信封里的信，主机=房子，传输层协议=李雷和韩梅梅（把信收集），网络层协议=邮政服务。
Internet传输层协议。TCP，可靠、按序的交付服务，拥塞控制，流量控制，连接建立。UDP，不可靠的交付服务，基于“尽力而为（Best-effort）”的网络层，没有做（可靠性方面的）扩展。两种服务均不保证延迟和带宽。
如果某层的一个协议对应直接上层的多个协议/实体，则需要复用/分用。接收端进行多路分用，传输层依据头部信息将收到的Segment交给正确的Socket，即不同的进程。发送端进行多路复用，从多个Socket接收数据，为每块数据封装上头部信息，生成Segment，交给网络层。
分用如何工作？主机接收到IP数据报（datagram），每个数据报携带源IP地址、目的IP地址和一个传输层的段（Segment），每个段携带源端口号和目的端口号。主机收到Segment之后，传输层协议提取IP地址和端口号信息，将Segment导向相应的Socket。TCP做更多处理。
利用端口号创建Socket。
DatagramSocket mySocket1=new DatagramSocket(99111);
DatagramSocket mySocket2=new DatagramSocket(99222);
UDP的Socket用二元组标识（目的IP地址，目的端口号）。
主机收到UDP段后，检查段中的目的端口号，将UDP段导向绑定在该端口号的Socket。
来自不同源IP地址和/或源端口号的IP数据报被导向同一个Socket。
TCP的Socket用四元组标识（源IP地址、源端口号、目的IP地址、目的端口号）。
接收端利用所有的四个值将Segment导向合适的Socket。
服务器可能同时支持多个TCP Socket，每个Socket用自己的四元组标识。
Web服务器为每个客户端开不同的Socket。
用户数据报协议（User Datagram Protocol，UDP，RFC 768），基于Internet IP协议，增加复用/分用、简单的错误校验（端到端原则），相当于把IP层服务暴露给应用层。
“Best effort”服务，UDP段可能丢失、非按序到达，IP也是这样。无连接，UDP发送方和接收方之间不需要握手，每个UDP段的处理独立于其它段。（在UDP上实现可靠数据传输？在应用层增加可靠性机制，应用特定的错误恢复机制。）
UDP为什么存在？无需建立连接（减少延迟）；实现简单，无需维护连接状态；头部开销少；没有拥塞控制，应用可更好地控制发送时间和速率。
常用于流媒体应用，容忍丢失，速率敏感。还用于DNS和SNMP
UDP协议报文段格式：源端口号、目的端口号、UDP段的长度（包括头部）、UDP校验和、应用数据（报文）。
UDP校验和（checksum）：检测UDP段在传输中是否发生错误（如位翻转）。发送方， 将段的内容视为16-bit整数；计算所有整数的和，进位加在和的后面（最高位进位必须被加进去），将得到的值按位求反，得到校验和；发送方将校验和放入校验和字段。接收方，计算所收到段的校验和；将其与校验和字段进行对比，不相等则检测出错误，相等则没有检测出错误（但可能有错误）。
可靠是不错、不丢、不乱。可靠数据传输对应用层、传输层、链路层都很重要，是网络Top-10问题，信道的不可靠特性决定了可靠数据传输协议（rdt）的复杂性。
渐进地设计可靠数据传输协议的发送方和接收方。只考虑单向数据传输，但控制信息双向流动。
利用状态机（Finite State Machine, FSM）刻画传输协议。有限状态自动机，圆圈代表当前所处的状态，线表示状态之间的迁移转换，横线上方是引起状态变迁的事件，横线下方是活动进行状态转换过程中采取的动作。每个状态间的变迁都必须被准确的定义，一个事件只能触发一个状态向另一个状态变迁。
Rdt 1.0: 可靠信道上的可靠数据传输。
底层信道完全可靠，不会发生错误（bit error），不会丢弃分组，发送方和接收方的FSM独立，不需要进行控制信息的交换。
发送方只有一个状态，等待上层调用。当有上层调用时，产生rdt_send(data)事件，make_pkt(data)生成分组，udt_send(packet)将分组发出，回到状态继续等待上层的调用。
接收方只有一个状态，等待下层调用。当rdt_rcv(packet)事件发生，extract(packet,data)从分组中将数据提取出来，deliver_data(data)把数据交付给上层，继续等待下层的调用。
Rdt 2.0: 产生位错误的信道。
底层信道可能翻转分组中的位（bit），利用校验和检测位错误。如何从错误中恢复？确认机制（Acknowledgements, ACK），接收方显式地告知发送方分组已正确接收；NAK，接收方显式地告知发送方分组有错误；发送方收到NAK后，重传分组。基于这种重传机制的rdt协议称为ARQ（Automatic Repeat reQuest）协议。
Rdt 2.0中引入的新机制：差错检测、接收方反馈控制消息ACK/NAK、重传。
发送方有两个状态，等待上层调用、等待控制消息ACK/NAK。生成分组时增加校验和。将分组保存到缓存中，进入等待ACK/NAK的状态，如果收到接收方返回的控制消息rdt_rcv(rcvpkt)且是NAK，重发该分组。重发后继续进入等待ACK/NAK的状态，直到收到接收方返回的控制消息rdt_rcv(rcvpkt)且是ACK，再进入等待上层调用状态。
接收方只有一个状态，等待下层调用。收到分组后判断是否有错，如果有错则返回NAK控制消息udt_send(NAK)，没错则提取数据向上层交付且返回ACK控制消息。
Rdt 2.0的缺陷，如果ACK/NAK消息发生错误/被破坏（corrupted）、发送方不能识别会怎么样？为ACK/NAK增加校验和，检错并纠错，难度较大；发送方收到被破坏ACK/NAK时不知道接收方发生了什么，添加额外的控制消息，额外的消息仍然可能会坏掉；如果ACK/NAK坏掉，发送方重传，不能简单的重传，会产生重复分组。
如何解决重复分组问题？发送方给每个分组增加序列号（Sequence number），接收方丢弃重复分组。stop and wait（停-等机制）Sender sends one packet, then waits for receiver response.
Rdt 2.1发送方，为每个分组增加了序列号，两个序列号（0和1）就够用，因为采用停-等协议；需校验ACK/NAK消息是否发生错误，状态数量翻倍，状态必须“记住”“当前”的分组序列号。接收方，需判断分组是否是重复，当前所处状态提供了期望收到分组的序列号。接收方无法知道ACK/NAK是否被发送方正确收到。
发送方引入0和1两个序列号，状态数增加。制作分组时加入序列号。发送消息后如果得到确认消息坏掉或NAK，重传；如果确认消息没有坏掉且收到ACK，修改序列号。
接收方有两个状态，希望收到序列号为0或1。如果收到一个分组且分组没有坏掉且序列号正确，理想情况，提取数据向上层交付且发送ACK；收到分组且分组坏掉，发送NAK；收到分组、分组没坏但序列号错误，发送ACK。
Rdt 2.2：无NAK消息协议。与Rdt 2.1功能相同，但只使用ACK。
接收方通过ACK告知最后一个被正确接收的分组，在ACK消息中显式地加入被确认分组的序列号。发送方收到重复ACK之后，采取与收到NAK消息相同的动作，重传当前分组。
如果信道既可能发生错误，也可能丢失分组，“校验和+序列号+ACK+重传”够用吗？如发送的段丢失或返回的ACK丢失，导致发送方一直等待。
发送方等待“合理”时间，需要定时器。如果没收到ACK，重传；如果分组或ACK只是延迟而不是丢了，重传会产生重复，序列号机制能够处理，接收方需在ACK中显式告知所确认的分组。
发送方发送一个packet后，启动定时器，进入等待ACK状态。如果产生超时事件，重传，再次启动定时器。如果发送成功，重置定时器，转到另外一个等待上层调用的状态。
Rdt 3.0能正确工作，但性能很差。示例：1Gbps链路，15ms端到端传播延迟，1KB分组。发送方利用率，即发送方发送时间百分比。
在1Gbps链路上每30毫秒才发送一个分组33KB/sec。网络协议限制了物理资源的利用。
流水线协议：允许发送方在收到ACK之前连续发送多个分组，更大的序列号范围，发送方和/或接收方需要更大的存储空间以缓存分组。
滑动窗口协议（Sliding-window protocol）：窗口，允许使用的序列号范围，窗口尺寸为N代表最多有N个等待确认的消息；滑动窗口，随着协议的运行，窗口在序列号空间内向前滑动。滑动窗口协议有GBN和SR。
分组头部包含k-bit序列号。窗口尺寸为N，最多允许N个分组未确认。
发送方为空中的分组设置计时器（timer）。超时Timeout(n)事件，重传序列号大于等于n，还未收到ACK的所有分组。
接收方采用累积确认机制，发送拥有最高序列号的、已被正确接收的分组的ACK，ACK(n)表示确认到序列号n（包含n）的分组均已被正确接收。可能收到重复ACK。接收方只需要记住唯一的expectedseqnum。
接收方没有缓存，乱序到达的分组直接丢弃。重新确认序列号最大的、按序到达的分组。
例题：数据链路层采用后退N帧（GBN）协议，发送方已经发送了编号为0～7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是什么？根据GBN协议工作原理，GBN协议的确认是累积确认，所以此时发送端需要重发的帧数是4个，依次分别是4、5、6、7号帧。
发送方窗口，N个连续的序列号，限制已发送且未确认的分组。只重传没收到ACK的分组。data from above: if next available seq # in window, send pkt. timeout(n): resend pkt n, restart timer. ACK(n) in [sendbase,sendbase+N]: mark pkt n as received. if n smallest unACKed pkt, advance window base to next unACKed seq #.
接收方对每个分组单独进行确认。设置缓存机制，缓存乱序到达的分组。为每个分组设置定时器。pkt n in [rcvbase, rcvbase+N-1]: send ACK(n), out-of-order: buffer, in-order: deliver (also deliver buffered, in-order pkts), advance window to next not-yet-received pkt. pkt n in [rcvbase-N,rcvbase-1]: ACK(n)（ACK丢失）. otherwise: ignore.
SR协议困境：序列号0, 1, 2, 3，窗口尺寸3，接收方能区分开下面两种不同的场景吗？(a)中，发送方重发分组0, 接收方收到后会如何处理？
序列号空间大小与窗口尺寸需满足什么关系？NS+NR<=2k，k是序列号位数。
