2013 | OriginalPaper | Buchkapitel
A Simpler Proof for Packet Routing
verfasst von : Thomas Rothvoß
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the
store-and-forward routing
problem, packets have to be routed along given paths such that the arrival time of the latest packet is minimized. A groundbreaking result of Leighton, Maggs and Rao says that this can always be done in time
$O(\textrm{congestion} + \textrm{dilation})$
, where the
congestion
is the maximum number of paths using an edge and the
dilation
is the maximum length of a path. However, the analysis is quite arcane and complicated and works by iteratively improving an infeasible schedule. Here, we provide a more accessible analysis which is based on conditional expectations. Like [LMR94], our easier analysis also guarantees that constant size edge buffers suffice.
Moreover, it was an open problem stated e.g. by Wiese [Wie11], whether there is any instance where all schedules need at least
$(1+\varepsilon)\cdot(\textrm{congestion}+\textrm{dilation})$
steps, for a constant
ε
> 0. We answer this question affirmatively by making use of a probabilistic construction.