The embedding capacity of information flows under renewal traffic

Stefano Marano, Vincenzo Matta, Ting He, Lang Tong

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Given two independent point processes and a certain rule for matching points between them, what is the fraction of matched points over infinitely long streams? In many application contexts, e.g., secure networking, a meaningful matching rule is that of a maximum causal delay, and the problem is related to embedding a flow of packets in cover traffic such that no timing analysis can detect it. We study the best undetectable embedding policy and the corresponding maximum flow rate-that we call the embedding capacity-under the assumption that the cover traffic can be modeled as an arbitrary renewal process. We find that computing the embedding capacity requires the inversion of a very structured linear system that, for a broad range of renewal models encountered in practice, admits a fully analytical expression in terms of the renewal function of the processes. This result enables us to explore the properties of the embedding capacity, obtaining closed-form solutions for selected distribution families and a suite of sufficient conditions on the capacity ordering. We test our solution on real network traces, which shows a remarkable match for tight delay constraints. A gap between the predicted and the actual embedding capacities appears for looser constraints, and further investigation reveals that it is caused by inaccuracy of the renewal traffic model rather than of the solution itself.

Original languageEnglish (US)
Article number6353586
Pages (from-to)1724-1739
Number of pages16
JournalIEEE Transactions on Information Theory
Issue number3
StatePublished - 2013

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'The embedding capacity of information flows under renewal traffic'. Together they form a unique fingerprint.

Cite this