Active network tomography and identifiability by design

A finite rooted directed tree $T=(V,E)$ has root $o$, with all edges directed away from $o$, and a nonempty receiver set $R$ consisting of every leaf other than $o$. Every nonroot internal vertex has at least two children. For a vertex $v$, its children are the vertices joined to $v$ by an outgoing edge; $P(o,v)$ is the unique edge set on the path from $o$ to $v$. The root may have any finite number of children.

A finite probe design is a nonempty finite family $\mathcal{C}=((C_d,N_d){)}_{d=1}^D$, where each receiver set $C_d$ is a nonempty subset of $R$ and each probe count $N_d$ is a positive integer. A singleton receiver set is a unicast scheme; a receiver set of size at least two is a multicast scheme. Its used edge set is $E_d={\bigcup }_{r\in C_d}P(o,r)$.

For a link-success parameter vector $p=(p_e{)}_{e\in E}\in (0,1{)}^E$, each design $d$ and probe $j\in \{1,\dots ,N_d\}$ has mutually independent link-success variables $X_{e,d,j}\in \{0,1\}$ for $e\in E_d$, with ${\mathrm{Pr}}_p(X_{e,d,j}=1)=p_e$. The same $p_e$ applies in every design and probe (temporal homogeneity). The observed receiver indicator is

For $y\in \{0,1{\}}^{C_d}$ let

The one-probe outcome law is

These probabilities sum to one because the sets ${\mathrm{\Omega }}_{d,y}$ partition the finite link-state space and ${\sum }_{x\in \{0,1{\}}^{E_d}}{w}_{p,d}(x)={\prod }_{e\in E_d}(p_e+(1-p_e))=1$. The complete experiment observes $N_d$ independent outcomes with law $P_{p,d}$ for each design, independently across designs. If the data are summarized by counts, $n_{d,y}\in {\mathbb{N}}_0$ is the number of probes in design $d$ with outcome $y$, and ${\sum }_y{n}_{d,y}=N_d$.

This is a finite statistical experiment: its parameter space is $(0,1{)}^E$ and its sampling law is the finite product of the stated receiver-outcome laws.

Statistical experiments

Cáceres, Duffield, Horowitz, and Towsley, §§2.1–2.3

Lawrence, Michailidis, and Nair, §§1–2

For a finite-tree probe design $\mathcal{C}=((C_d,N_d){)}_{d=1}^D$, a receiver $r\in R$ is covered if $r\in C_d$ for some $d$. For a nonroot internal vertex $v$, a design $C_d$ splits $v$ if there are distinct children $c,c^{\mathrm{\prime }}$ of $v$ and receivers $r,s\in C_d$ such that $r$ lies in the subtree rooted at $c$ and $s$ lies in the subtree rooted at $c^{\mathrm{\prime }}$. The design satisfies the split/coverage condition if every receiver is covered and every nonroot internal vertex is split by at least one design.

Finite-tree multicast loss experiments

Xi, Michailidis, and Nair, §3.2, Proposition 1

Lawrence, Michailidis, and Nair, §3.1

Inputs. Use a finite-tree multicast loss experiment with observed counts $n_{d,y}$, where $n_{d,y}\in {\mathbb{N}}_0$, ${\sum }_{y\in \{0,1{\}}^{C_d}}{n}_{d,y}=N_d$, and $p_e$ is the success probability for edge $e$. Supply an initial vector $p^{(0)}\in (0,1{)}^E$, a likelihood tolerance $\tau \ge 0$, and an iteration cap $M\in {\mathbb{N}}_{>0}$. The data are admissible only when every pattern with positive count has ${\mathrm{\Omega }}_{d,y}\mathrm{\ne }\mathrm{\varnothing }$ and every link is traversed by at least one probe, that is,

For algorithm calculations, extend the finite law to candidate vectors in the closed cube as follows. For $a\in [0,1]$ and $z\in \{0,1\}$, let $b(a,z)=a$ if $z=1$ and $b(a,z)=1-a$ if $z=0$. For $p\in [0,1{]}^E$, set

The sets ${\mathrm{\Omega }}_{d,y}$ partition the link-state space and ${\sum }_{x\in \{0,1{\}}^{E_d}}{w}_{p,d}^{\mathrm{c}\mathrm{l}}(x)={\prod }_{e\in E_d}((1-p_e)+p_e)=1$, so $P_{p,d}^{\mathrm{c}\mathrm{l}}$ is a probability law for every $p\in [0,1{]}^E$. For $p\in (0,1{)}^E$, $P_{p,d}^{\mathrm{c}\mathrm{l}}(y)=P_{p,d}(y)$ from the tree-experiment definition. This closed-cube extension is used only to evaluate candidate iterates; the experiment's parameter space remains $(0,1{)}^E$. When $Z_{d,y}(p)>0$ define

The algorithm's observed log likelihood on the closed cube is

with $\mathrm{\ell }(p)=-\mathrm{\infty }$ if any positive-count pattern has zero probability.

Output. Return the finite iterate list and one status: invalid-input, zero-likelihood-current, zero-likelihood-candidate, likelihood-tolerance-met, or iteration-cap-reached. For admissible input, the list begins with $p^{(0)}$ and every later iterate lies in $[0,1{]}^E$. If an input check fails, the list is the one-element list $(p^{(0)})$ containing the supplied initial vector.

Procedure.

1. Validate the count constraints, pattern feasibility, interior initial vector, nonnegative tolerance, positive iteration cap, and $N_e>0$ for each link. If any check fails, return the one-element iterate list $(p^{(0)})$ and status invalid-input.

2. Initialize the list with $p^{(0)}$. At each current iterate $p^{(t)}$, compute $Z_{d,y}(p^{(t)})$ for every positive-count pattern. If any is zero, return the current iterate list, ending in $p^{(t)}$, with status zero-likelihood-current.

3. For each link $e$, compute its expected number of latent successes

Set

This finite sum is the E-step conditional expectation of the complete-data success count; the displayed ratio is the M-step update instruction and lies in $[0,1]$ for each edge. Coordinates equal to $0$ or $1$ are allowed after an update.

4. Compute $\mathrm{\ell }(p^{(t+1)})$. If any positive-count pattern has zero probability, return the current iterate list, ending in the last valid iterate $p^{(t)}$, with status zero-likelihood-candidate. Otherwise append $p^{(t+1)}$. If $\mathrm{\mid }\mathrm{\ell }(p^{(t+1)})-\mathrm{\ell }(p^{(t)})\mathrm{\mid }\le \tau$, return the list with status likelihood-tolerance-met. If not, continue from $p^{(t+1)}$ until $M$ updates have been made, then return the list with status iteration-cap-reached.

All state sums are finite, and the finite link-state conditional probabilities are calculated directly; the generic measure-space/KL branch of the EM procedure is not invoked. The status records only the stopping rule that fired; it asserts neither parameter convergence nor a global optimum.

Finite-tree multicast loss experiments

Expectation-maximization

Xi, Michailidis, and Nair, §4.2

Lawrence, Michailidis, and Nair, §3.2

Let $T=(V,E)$ and $\mathcal{C}=((C_d,N_d){)}_{d=1}^D$ be a finite-tree multicast loss experiment with parameter space $(0,1{)}^E$, independent link successes, and the same link probabilities in every probe. Let $\mathsf{L}(p):={⨂}_{d=1}^D{P}_{p,d}^{\otimes N_d}$ be the full repeated-probe sampling law determined by the one-probe outcome laws $P_{p,d}$. Then $\mathsf{L}$ is injective if and only if $\mathcal{C}$ satisfies the split/coverage condition.

Finite-tree multicast loss experiments

Split and coverage condition

Identifiability of an estimand

Xi, Michailidis, and Nair, §3.2 Proposition 1 and Appendix A.1

Lawrence, Michailidis, and Nair, §3.1