“滑动窗口” - 是否有可能增加协议的可靠性并避免流量控制实施？
作为个人项目的一部分，我正在制作一个可靠的应用程序级协议（封装在 UDP 中）。
为了实现可靠性，我必须跟踪我发送的数据包以及另一接收端收到的数据包。 这是在滑动窗口的帮助下完成的，并且它还保持了流量控制。
- 除了标准滑动窗口/流量控制技术之外，还有其他方法可以实现可靠性吗？
- 如果否，是否有人会分享他的经验/设计原理/代码并通过这篇文章进行讨论。
- 如果是，您是否实现了它，或者您是否知道该概念的任何实现。
As a part of a personal project, I am making an application level protocol (encapsulated in UDP) which is reliable.
For the implementation of reliability, I have to keep track of which packets i send, and which packets are received at the other receiver end. This is done with the help of a sliding window, and it also maintains the flow-control.
- Is there a way to implement reliability apart from standard sliding window/flow control technique.
- If No, will someone share his experience/design rationale/code and discuss it over this post.
- If Yes, have you implemented it, or if you know any implementation of the concept.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
遗憾的是 TCP/IP 堆栈不包含可靠的数据报协议，但事实就是如此。 你可以搜索很多尝试和建议。
如果这是一个个人项目，您的时间可能是最稀缺的资源，除非您的目标是重新发明这个特定的轮子，否则只需在 TCP 之上构建您的协议即可继续。
It's sad that the TCP/IP stack doesn't include a reliable datagram protocol, but it just doesn't. You can search for lots of attempts and proposals.
If this is a personal project, your time is probably the most scarce resource, and unless your goal is to reinvent this particular wheel, just build your protocol on top of TCP and move on.
在阅读了所有这些答案、从其他实现中学习并阅读了一些论文之后，我正在编写/分享最相关的内容。 先讲流量控制，后面讲可靠性。
有两种流量控制——
基于速率的流量控制很难实现，因为它们基于 RTT（往返时间 - 它不像 ping 的 RTT 那么简单）计算。 如果您决定提供专有的拥塞控制系统，并且从当前版本开始提供它，那么您可以采用基于速率的流量控制。 显式拥塞控制也存在，它依赖于路由器，所以它不存在。
基于窗口的流量控制，窗口用于跟踪所有发送的数据包，直到发送方确定接收方已收到它们。 静态窗口实现起来很简单，但是吞吐量会很惨。 动态窗口（也称为滑动窗口）是一种更好的实现，但实现起来有点复杂，并且依赖于各种确认机制。
现在可靠性...
可靠性是确保接收者已收到您的数据包/信息。 这意味着接收者必须告诉发送者，是的，我明白了。 这种通知机制称为确认。
现在当然也需要传输数据的吞吐量。 因此，只要两端和整个路径都有可用带宽，您应该能够发送尽可能多的数据包，而不是 MAX[发送方的发送限制，接收方的接收限制]。
如果你结合所有的知识，虽然可靠性和流量控制是不同的概念，但在实现方面，当你使用滑动窗口时，底层机制是最好的实现。
所以最后简而言之，如果我和其他人设计一个新的应用程序协议并需要它可靠，滑动窗口将是实现它的方式。 例如，如果您计划实施拥塞控制，那么您不妨使用混合（基于窗口+速率）方法（uDT）。
After reading all these answers, learning from other implementations and reading some papers, I am writing/sharing what is most pertinent. First let me talk about Flow control, and later i will talk about reliability.
There are two kinds of flow control--
Rate Based flow controls are difficult to implement, as they are based on RTT(round trip time -- its not as simple as ping's RTT) calculation. If you decide on providing a proprietary congestion control system, and you are providing it from present release, then you can go for rate-based flow control. Explicit congestion control is also there which is router dependent,so its out of picture.
Window based flow control, a window is used to keep track of all the sent packet, until the sender is sure that receiver has received them. Static window is simple to implement but throughput will be miserable. Dynamic window (also know as sliding window) is a better implementation, but a little complex to implement, and depends on various kind of Acknowledgement mechanisms.
Now Reliability...
Reliability is making sure the receiver has received your packet/information. Which means that receiver has to tell the sender, yes I got it. This notification mechanism is called Acknowledgement.
Now one ofcourse needs throughput for the data transfered also. So you should be able to send as many packets as you can, rather MAX[sender's sending limit, receiver's receiving limit], provided you have available bandwidth at both the ends, and throughout the path.
If you combine all the knowledge, although reliability and flow control are different concepts, but implementation wise the underlying mechanism is best implemented, when you use a sliding windows.
so finally in short, I and anyone else if designing a new app protocol and needs it to reliable, sliding window shall be the way to achieve it. If you are planning to implement congestion control then u might as well use a hybrid(window+rate based) approach (uDT) for example.
我有点同意 Nik 在这一点上的观点，听起来你正在使用 UDP 来完成 TCP 的工作，可靠的传输和流量控制。 然而，有时他们也是你自己这样做的理由。
为了回答您的问题，有一些基于 UDP 的协议可以进行可靠的传输，并且不太关心顺序，这意味着只有丢弃的数据包在到达目的地时才会产生性能损失（通过要求重新传输）。
我们日常使用的最好的例子是名为 RADIUS 的协议，我们使用它在 EVDO 网络上进行身份验证和计费。 源和目标之间的每个数据包都有一个标识符字段（半径仅使用 1 个字节，您可能需要更多），并且每个标识符都需要被确认。 现在Radius并没有真正使用滑动窗口的概念，因为它实际上只是一个控制平面流量，但使用TCP的概念是完全可行的。 因此，因为每个数据包都需要被确认，所以您缓冲传出数据包的副本，直到它们被远程端点确认，这样每个人都很高兴。 流量控制可以使用来自此确认机制的反馈来了解它可以放大/缩小数据包的速率，这可以最容易地通过传输但等待确认的数据包列表的大小来控制。
请记住，对于滑动窗口的使用以及围绕数据包丢失和滑动窗口对 TCP/IP 堆栈进行的调整，实际上已经进行了数十年的研究，因此您可能拥有一些可行的东西，但可能很难复制相同的东西你会在现代操作系统上进入高度调整的堆栈。
这种方法的真正好处是您需要可靠的传输，但您实际上不需要订购，因为您发送的是不相交的信息。 这就是 TCP/IP 崩溃的地方，因为丢弃的数据包会阻止所有数据包进入堆栈，直到数据包重新传输为止。
I sort of agree with Nik on this one, it sounds like you're using UDP to do TCP's job, reliable transmission and flow control. However, sometime's their are reasons to do this yourself.
To answer you're questions, there are UDP based protocols that do reliable transmission and don't care much about ordering, meaning only dropped packets have a performance penalty for making it to the destination (by requiring retransmission).
The best example of this we use daily is a protocol called RADIUS, which we use for Authentication and Accounting on our EVDO network. Each packet between the source and destination get's an identifier field (radius only used 1 byte, you may want more), and each identifier needs to be acked. Now Radius doesn't really use the concept of a sliding window since it's really just a control plane traffic, but it's entirely viable to use the concept from TCP. So, because each packet needs to be acked, you buffer copies of outgoing packets until they are acked by the remote end point, and everyone is happy. Flow control can use feedback from this acknowledgement mechanism to know it can scale up/down the rate of packets, which may be most easily controlled by the size of the list you have for packets transmitted but awaiting acknowledgement.
Just keep in mind, there are literally decades of research into the use of sliding window and adjustments to TCP/IP stacks around packet loss and the sliding window, so you may have something that works, but it may be difficult to replicate the same thing you get in a highly tweaked stack on a modern OS.
The real benefit to this method is you need reliable transport, but you really don't need ordering, because you're sending disjoint pieces of information. This is where TCP/IP breaks down, because a dropped packet stop all packets from making it up the stack until the packet is retransmitted.
您可以有一个简单的发送->确认协议。 对于每个数据包，在继续处理下一个数据包之前，您都需要一个 Ack（实际上，这是窗口大小 = 1 个数据包 - 我不会将其称为滑动窗口:-)
You could have a simple Send->Ack protocol. For every packet you require an Ack before proceding with the next (Effectivly this is windows size = 1 packet - which I wouldn't call a sliding window :-)
您可能有如下内容：
第 1 部分：初始化
1) 发送方发送一个数据包，其中包含要发送的数据包数量。 该数据包可能需要设置某种控制位或具有不同的大小，以便接收器可以将其与常规数据包区分开。
2) 接收方向发送方发送ACK。
3) 重复步骤1-2，直到发送方收到ACK。
第 2 部分：发送大量数据
4) 然后，发送方发送所有数据包，并将序列号附加到数据部分的前面。
5) 接收方接收所有数据包并按照序列号指定的方式排列它们。 接收器保留一个数据结构来跟踪已接收到的序列号。
第 3 部分：发送丢失的数据
6) 在一段超时时间过后，没有收到更多数据包，接收方将向发送方发送一条消息，请求丢失的数据包。
7) 发送方将丢失的数据包发送给接收方。
8) 重复步骤6-7，直到接收方收到所有需要的数据包。
9) 接收方向发送方发送一个特殊的“Done”数据包。
10) 发送方向接收方发送ACK。
11) 重复步骤10-11，直到接收方收到ACK。
数据结构
接收方可以通过多种方式跟踪丢失的序列号。 最直接的方法是为每个序列号保留一个布尔值，但这将是非常低效的。 您可能想要保留丢失数据包范围的列表。 例如，如果总共有 100 个数据包，您将从包含一个元素 [(1-100)] 的列表开始。 每次收到数据包时，只需增加该范围前面的数字即可。 假设您成功接收数据包 1-12，错过数据包 13-14，收到数据包 15-44，错过数据包 45-46，那么最终会得到类似：[(13-14), (45-46)] 的结果。 将此数据结构放入数据包并将其发送给发送方将非常容易。 你也许可以通过使用一棵树来让它变得更好，但不确定。
You could have something like the following:
Part 1: Initialization
1) Sender sends a packet with the # of packets to be sent. This packet may require some kind of control bit to be set or be a different size so that the receiver can distinguish it from regular packets.
2) Receiver sends ACK to Sender.
3) Repeat steps 1-2 until ACK received by Sender.
Part 2: Send bulk of data
4) Sender then sends all packets with a sequence number attached to the front of the data portion.
5) Receiver receives all the packets and arranges them as specified by the sequence numbers. The receiver keeps a data structure to keep track of which sequence numbers have been received.
Part 3: Send missing data
6) After some timeout period has elapsed with no more packets received, the Receiver sends a message to the Sender requesting the missing packets.
7) Sender sends the missing packets to the Receiver.
8) Repeat steps 6-7 until Receiver has received all required packets.
9) Receiver sends a special "Done" packet to the Sender.
10) Sender sends ACK to Receiver.
11) Repeat steps 10-11 until ACK is received by Receiver.
Data Structure
There are a few ways the Receiver can keep track of the missing sequence numbers. The most straight-forward way would be to keep a boolean for each sequence number, however this will be extremely inefficient. You may want to keep a list of missing packet ranges. For example, if there are 100 total packets, you would start with a list with one element [(1-100)]. Each time a packet is received, simply increment the number on the front of that range. Let's say you receive packets 1-12 successfully, miss packets 13-14, received 15-44, miss 45-46, then you end up with something like: [(13-14), (45-46)]. It would be quite easy to put this data structure into a packet and send it off to the Sender. You could maybe make it even better by using a tree instead, not sure.
您可能需要查看 SCTP - 它可靠且面向消息。
You might want to look at SCTP - it's reliable and message-oriented.
维护 UDP 应用程序中的本地状态以检查是否已传输必要的数据以确认可靠性可能是更好的方法，而不是尝试执行完整的数据包级可靠性和流量控制。
尝试在 UDP 路径中复制 TCP 的可靠性和流量控制机制根本不是一个好的答案。
It might be a better approach to maintain local state in the UDP applications to check that necessary data has been transferred for confirming reliability -- rather than, trying to do complete packet level reliability and flow-control.
Trying to replicate reliability and flow-control mechanisms of TCP in a UDP path is not a good answer at all.