Packing unsplittable flows problem

Question

For a single stream of elements as input every elements should be routed into a fixed number of $k$ output streams trying to keep them balanced. In the following example $k=3$ :

Let's define as flow a sequence of element of the same type represented in the following diagrams using the same colour. Every flow must be routed into the same output stream keeping the elements ordered as found on the input stream:

Another correct solution that is more balanced than the previous one:

Considering also that:

• After a number of elements (called $timeout$) on the input stream without any element of the type of a specific flow, that flow should be considered ended and the element found should be the starting point of a new flow

I have some questions:

• Do you know any paper covering this kind of problems?

• What is a good algorithm that maximise the throughput, in other words keeping the output stream balanced?

Update

Thanks to @D.W. for the comments, here some clarifications:

• I am looking for an "online algorithm" where a "reasonable" latency is allowed therefore a lookahead-buffer/moving-window is definitely allowed

• I am not looking for theoretical guarantees, I am looking for an approximate algorithm to try against few hundreds test cases made of [millions..billion] elements with a mix of few elephant flows and many mice ones.

• The stream balance I am looking for should be considered over a period of time and not in an "absolute sense". In other words an algorithm that fills the first stream only then the second and then the third is as balanced as an algorithm that fill only the first stream

Answer 1

The obvious algorithm is the greedy algorithm. Each time you see a new element that's not part of an existing flow, you identify which output stream currently has lowest occupancy, and route that element to that output stream. When you see an element that is part of an existing flow, you obviously have no freedom about where to route it; it has to go to the same output stream as the rest of the flow.

In an online setting where you must decide immediately where to route each element and where you have no information about the distribution of flow sizes or other domain knowledge, this is the natural strategy. When you see the first element of a flow, you have no information about how large the flow will be, and you must decide immediately where to route it based only upon the current state of the output streams. It's not clear whether there is any theoretical sense in which one can provably do better, if we have zero knowledge.

Now in practice I suspect you will typically have some a priori knowledge about the distribution of flow sizes. In this case, you can do bit better.

For instance, suppose you knew that all flows were either mice (they have 1 element) or elephants (they have 1000 elements). Then it would be easy to do better. When you get a new element that's not part of an existing flow, look at the existing flows in the output streams. For each existing flow in an output stream that has more than 1 element, you know exactly how many more elements are yet to be received in that flow, so you get a lower bound on how full that output stream will become once all of the remaining packets in the existing flows arrive (it is a lower bound since for the flows where you've only seen one packet you don't know yet whether they are mice or elephants). Call this the degree to which that output stream is "committed". Now you can use these lower bounds to pick which output stream is least committed, and route the new element to that output stream.

If you additionally know what fraction of flows are mice and what fraction are mice, instead of computing a lower bound you can compute an expected value and choose which output stream to route to by going for the choice where the expected value of the imbalance is minimized.

In general, you can use a greedy algorithm that uses expected output stream commitment as the basis for choosing an output stream. Let the random variable $X$ be distributed according to the distribution on flow sizes, i.e., $X$ is a random variable that counts the number of elements in a randomly chosen flow. Suppose you have seen $k$ elements in a particular flow, so far. Then the conditional expectation $\mathbb{E}(X | X\ge k)$ is in some sense your "best guess" at what the total flow size will be; it is the expected flow size, given that the flow contains at least $k$ elements. Thus, you can compute this for each active flow, and compute the sum of these values for each output stream, and route the new flow to the least-committed output stream. If you know the distribution of $X$, you should be able to compute $\mathbb{E}(X | X\ge k)$ easily.

This algorithm is fairly simple and should be pretty efficient: it requires $O(1)$ state per active flow (a counter to keep track of the number of elements seen in that flow so far). Assuming you can compute the conditional expectation in $O(1)$ time, the algorithm requires $O(1)$ time per element.

Whether this algorithm is sufficiently better than the simple greedy (choose the lightest output stream, based only upon its current size, not its expected commitment) in practice can only be answered by experimenting on some realistic data sets.