Towards asymptotic optimality in probabilistic packet marking

Abstrakt

We consider probabilistic algorithms (packed marking schemes) for sending information from nodes (routers) along a path traveled by a stream of packets to an end-host. We investigate tradeoffs between the number of possible states of marking bits in a packet, the number of bits of information sent, and the number of packets needed to reconstruct the information reliably.

We establish a connection of near-optimal schemes to a geometric problem, the existence of d-dimensional k-reptiles simplices.