The origin of pathflow

pathflow began with a paper. AeroMTP brought together fountain coding, multiple network paths and an allocation model intended to reduce the time needed to deliver a block of data. Fountain coding lets a receiver recover a block once it has enough encoded packets, so packets arriving over different paths can contribute to the same recovery target. ¹²

Working through the design also meant revisiting the initial implementation choices. The first implementation used an integer linear solver, but closer examination of the paper’s loss model revealed nonlinear terms. Another goal was to separate packet allocation from congestion control, so other systems could use the idea with their own transport mechanisms. ²

The idea worth keeping

Multiple connections give a sender more options, but deciding how to use them takes more than comparing their bandwidth. A fast path may already have a queue. A low-latency path may lose more packets. A slower connection may still contribute enough useful capacity to finish a transfer sooner.

The useful question is how much work each path should take. For a batch of packets, the allocation needs to account for transmission time, latency, queued traffic and the extra transmissions needed to allow for loss. Giving every path an equal share ignores those differences. Sending everything over the path with the highest throughput ignores them too.

pathflow was designed to make that decision available independently of any particular transport protocol.

Following the loss model through

The paper suggests heuristic solutions for a small number of paths, but leaves the choice of algorithm open. Turning the model into reusable software required working through how its nonlinear loss allowance affected allocation. ¹

In AeroMTP, as in pathflow, the allowance for packet loss includes a square-root term that depends on how many packets are assigned to a path. That makes the cost nonlinear in the allocation variables. ¹³

A standard optimization technique can replace the maximum of several completion times with a shared upper bound. Each path used by the allocation must finish within that bound, which the solver tries to minimize. But this transformation leaves the nonlinear loss term in place. The resulting model cannot be passed directly to an integer linear solver without further reformulation or approximation.

That distinction became concrete in the code. The first implementation calculated loss compensation separately from the linear constraints used for allocation. A later revision included the extra transmissions in the completion-time objective itself. That allowed the allocator to compare choices using their modeled cost, including loss. ²

Keeping congestion control separate

AeroMTP’s rate-based controller used additive increase and multiplicative decrease, familiar mechanisms from TCP congestion control. It paired those mechanisms with a congestion signal based on the relative losses of high- and low-priority packets, assuming routers discard lower-priority packets first. That design raised a separate question: how much transport machinery did a packet allocator need to own? ¹

Congestion control determines how much traffic a sender can responsibly put onto the network. Allocation decides how to distribute work across the paths available to it. The two decisions need to cooperate, but they can have separate interfaces.

pathflow stays focused on allocation. The surrounding transport supplies usable path estimates and enforces its congestion limits and pacing. That lets an application use the allocator alongside its own transport control, with a clear place to update either part as conditions or requirements change.

A reusable packet allocator

pathflow takes a batch size and a description of each path: throughput in packets per second, latency, loss rate and queue depth. It uses a requested per-path success target to estimate an allowance for loss, then returns per-path allocations, planned transmission counts and estimated completion times. The loss model assumes independent packet losses; its estimates depend on how well that assumption and the supplied measurements represent the network. ¹³

Its objective is to minimize the latest estimated completion time among the paths it uses. The greedy solver, used by default in the command-line tool, builds the allocation one packet at a time, comparing the estimated completion time of giving the next packet to each path. A path can remain unused when assigning work to it would delay completion. ³

This produces a small, useful interface. An application gathers path measurements, asks for an allocation and carries out the resulting plan. As measurements change, it can calculate a new allocation. The application chooses its coding scheme, produces any repair packets and handles transmission and feedback.

The project developed from an allocation experiment into a C library with a command-line tool. The tool lets developers inspect allocations for a given set of path conditions before connecting the allocator to a larger system. ³

Building on research

The value of reading AeroMTP was in following a useful idea far enough to identify which parts could become a reusable component. Examining the loss model sharpened the allocation problem. Separating congestion control gave that problem a practical boundary. Publishing the result made the work available for others to examine and adapt.

The project illustrates an approach to building at URSOID: learning from existing work, questioning the assumptions that matter to implementation, and turning useful ideas into focused components. pathflow gives developers and integrators a packet allocator they can build into systems with their own constraints.

The source and build instructions are available on GitHub.

References