So, I'm working through this practice exam in my data communication class. Then I never wanted to relive my calculus two days, but here we are. I think I'm dealing with an arithmetic/geometric sequence.
The original problem states:
Consider a query flooding in a P2p Gnutella network. Suppose that each peer is connected to at most $N$ neighbors in the overlay network. Also, suppose that the node count field is initially set to $k$. Suppose Alice makes a query Find an upper bound on the number of query messages that are sent into the overlay network.
My reasoning is that something like this is going on. Suppose $K=7$ and $x = 3$ meaning that each peer has 3 leaves, or child nodes.
The first query executes on the parent node so, 1 Next query $k = k - 1$ $1 + (3)1$ Then $1 + (3)1 + 9(1)$
Not sure how to produce a formula to figure this out.
Having $N$ neighbours and up to $k$ hops we get for the number of query messages \begin{align} q_0 &= 1 \\ q_1 &= 1 + N \\ q_2 &= 1 + N + N^2 \\ \vdots \\ q_k &= \sum_{j=0}^k N^j = \frac{N^{k+1} - 1}{N - 1} \end{align} which is a geometric series.