The packet counter in an entry is initialized to when the first packet of the flow gets sampled, and it is incremented for all subsequent packets belonging to the flow. Let be the number of packets in the flow at the input of the flow slicing algorithm. gives the formula for our estimator for the number of packets in the flow.
Proof: By induction on the number of packets .
Base case: If , the only packet of the flow is sampled with probability and in that case it is counted as packets. With probability it is not sampled (and it counts as 0). Thus .
Inductive step: By induction hypothesis, we know that for a flow
with ,
. Also since the flow slice
length and the inactivity timeout
are larger than the
bin size, we know that once the flow gets an entry, all its packets
within the bin will get counted by . There are two possible
cases: the first packet of the flow gets sampled, and we get ,
or it doesn't and then the value of and
will be
the same as those for a flow with packets for which the
sampling decisions are the same as for the rest of the packets of our
flow.
If we sample packets randomly with probability before applying the flow slicing algorithm, we will want to estimate the number of packets at the input of the packet sampling stage. Since , it is easy to show that is an unbiased estimator for .