To address the rising demand for strong packet delivery guarantees in
networking, we study a novel way to perform graph resource allocation. We first
introduce allocation graphs, in which nodes can independently set local
resource limits based on physical constraints or policy decisions. In this
scenario we formalize the distributed path-allocation (PAdist) problem, which
consists in allocating resources to paths considering only local on-path
information — importantly, not knowing which other paths could have an
allocation — while at the same time achieving the global property of never
exceeding available resources.
Our core contribution, the global myopic allocation (GMA) algorithm, is a
solution to this problem. We prove that GMA can compute unconditional
allocations for all paths on a graph, while never over-allocating resources.
Further, we prove that GMA is Pareto optimal with respect to the allocation
size, and it has linear complexity in the input size. Finally, we show with
simulations that this theoretical result could be indeed applied to practical
scenarios, as the resulting path allocations are large enough to fit the
requirements of practically relevant applications.