Crate quack

The quACK is a data structure for being able to refer to and efficiently acknowledge a set of opaque packets seen by a network intermediary. The recommended quACK implementation is the 32-bit power sum quACK with no features.

In the quACK problem, a data sender transmits a multiset (meaning the same element can be transmitted more than once) of elements S (these correspond to packets). At any given time, a receiver (such as a proxy server) has received a subset R \subseteq S of the sent elements. We would like the receiver to communicate a small amount of information to the sender, who then efficiently decodes the missing elements—the set difference S \ R—knowing S. This small amount of information is called the quACK and the problem is: what is in a quACK and how do we decode it?

Modules

• arithmetic
  Efficient modular arithmetic and polynomial evaluation.

Structs

• MontgomeryQuackmontgomery
  64-bit power sum quACK using the Montgomery multiplication optimization.
• PowerSumQuackU16power_table
  16-bit power sum quACK.
• PowerSumQuackU32
  32-bit power sum quACK.
• PowerSumQuackU64montgomery
  64-bit power sum quACK.
• PowerTableQuackpower_table
  16-bit power sum quACK using the precomputation optimization.
• StrawmanAQuackstrawmen
  Strawman quACK implementation that echoes every packet identifier.
• StrawmanBQuackstrawmen
  Strawman quACK implementation that echoes a sliding window of packet identifiers.

Traits

• PowerSumQuack
  A quACK represented by a threshold number of power sums.

Functions

• global_config_set_max_power_sum_threshold
  The multiplicative modular inverses of the integers up to this threshold are lazily precomputed, for more efficient divison. This function MUST be called before modifying any quACKs with a threshold greater than the default threshold of 20, and immediately precomputes the tables.