3
$\begingroup$

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.

$\endgroup$

0

Your Answer

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