将数据分片成数据包的算法

Question

假设我想将一些数据单元分成数据包(每个数据包的最大大小可以说是 1024 字节)。每个数据单元的大小都可以是可变的，例如:

a = 20 bytes
b = 1000 bytes
c = 10 bytes
d = 800 bytes

任何人都可以建议任何有效的算法来有效利用带宽来创建包含此类随机数据的数据包吗？我无法将单个数据单元拆分为字节...它们全部放在一个数据包中。

编辑:数据单元的顺序无关紧要!

Answer 1

有几种不同的方法，具体取决于您的要求以及您希望花费多少时间。正如@amit 在评论中提到的，一般问题是 NP-Hard。但是您可以通过一些简单的更改获得一些改进。

在我们去那里之前，你确定你真的需要这样做吗？大多数网络层都有一个数据包大小(或更大)的缓冲区。当您写入网络时，它会将您的数据放入该缓冲区。如果您没有完全填满缓冲区，代码将在发送前短暂延迟。如果您在该延迟期间添加更多数据，则新数据将添加到缓冲区。缓冲区在填满后或在延迟超时到期后发送。

因此，如果您有一个每次向网络写入一个字节的循环，您就不会创建大量的单字节数据包。

在接收端，最低级别的网络层接收整个数据包，但不能保证您接收数据的调用将获得整个数据包。也就是说，发送方可能会发送一个 800 字节的数据包，但在接收端，第一次调用 read 可能只返回 50 或 273 字节。

当然，这取决于您阅读数据的级别。如果您谈论的是 Java 或 .NET 之类的东西，其中您与网络堆栈的接口(interface)是通过套接字实现的，那么您几乎可以肯定不能保证对 socket.Read() 的调用会返回一个完整的数据包。

现在，如果您可以保证每次读取调用都返回一个完整的数据包，那么最简单的打包方法就是将所有内容序列化到一个大缓冲区中，然后以多个 1,024 发送出去字节数据包。您需要在第一个数据包的前面创建一个 header ，说明将发送的总字节数，以便接收方知道会发生什么。结果将是一堆 1,024 字节的数据包，后面可能是一个更小的最终数据包。

如果你想确保一个数据对象完全包含在一个数据包中，那么你必须这样做:

add a to buffer
if remaining buffer < size of b
    send buffer
    clear buffer
add b to buffer
if remaining buffer < size of c
    send buffer     
    clear buffer
add c to buffer
... etc ...