I have a practical programming problem that I am struggling to find an optimal algorithm for, in part because I don't know what to call it. The problem concerns vectored I/O (scatter/gather).

Consider a server s and a set of connected clients C. The server maintains a contiguous array B of variable-length blocks of data in its memory. For each block in B, there is some subset of C that are "subscribed" to the block. At fixed intervals, the server sends each client all of its subscribed blocks.

I would like to use vectored I/O to optimize the sending by constructing a static I/O vector (array of pointer/length pairs) describing the location of each client's subscribed blocks at the server. This can be done trivially as so:

for (block in B) {
    for (client in block.subscribers) {
        client.io_vec.append(block.addr, block.len);

However, the network hardware I am using has a limit on the number of I/O vectors which can make up one message, which I will call k. So, I need to figure out how to lay out B such that I can construct vectors of length <= k, where k is much smaller than |B|. B can be rearranged freely, and blocks can be sent to the client in a different order than their order in server memory.

I am already confident that it is impossible to do this with no copying of blocks at the server for arbitrary B and k. Rather, my plan is to start from a conservative solution of entirely separate regions for each client, where each region contains a copy of all subscribed blocks (and can be described by an I/O vector of length 1), and then merge those regions as much as possible, with the constraint that all client I/O vectors must have a length <= k.

However, I'd like to check whether I'm reinventing the wheel before I spend a lot of time on this. Does what I'm describing match a known problem/algorithm? It feels like it might, but I just don't know the magic words to search for.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.