Data flow dissemination in a network

We consider the following network model motivated, in particular, by blockchains and peer-to-peer live streaming. Data packet flows arrive at the network nodes and need to be disseminated to all other nodes. Packets are relayed through the network via links of finite capacity. A packet leaves the network when it is disseminated to all nodes. Our focus is on two communication disciplines, which determine the order in which packets are transmitted over each link, namely Random-Useful (RU) and Oldest-Useful (OU). We show that RU has the maximum stability region in a general network. For the OU we demonstrate that, somewhat surprisingly, it does not in general have the maximum stability region. We prove that OU does achieve maximum stability in the important special case of a symmetric network, given by the full graph with equal capacities on all links and equal arrival rates at all nodes. We also give other stability results, and compare different disciplines’ performances in a symmetric system via simulation. Finally, we study the cumulative delays experienced by a packet as it propagates through the symmetric system, specifically the delay asymptotic behavior as \(N \rightarrow \infty \). We put forward some conjectures about this behavior, supported by heuristic arguments and simulation experiments.

Authors and Affiliations

1. University of Illinois at Urbana-Champaign, Urbana, USA

   Aditya Gopalan & Alexander L. Stolyar

Corresponding author

Correspondence to Alexander L. Stolyar.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A: Proof of Theorem 3.2

The proof is a relatively minor adjustment of the proof of theorem 3 in [11]. For this reason we do not give a self-contained proof here, but rather specify the required changes in that proof. This means that an interested reader will have to read the proof of theorem 3 in [11], and then “apply” the adjustments that we now specify.

The proof of theorem 3 in [11] uses the fluid limit technique, which is also discussed and used in our Sect. 4. The following key estimate is derived in that proof:

Here the left-hand side is the derivative of the “amount of fluid" that originated in the subset of nodes \(S^*\), containing the single source node s, but has not “left the subset \(S^*\) yet,” i.e. not present in any node outside \(S^*\). The right-hand side is equal to the rate at which such fluid arrives (equal to \(\lambda _s\), since s is the single source) minus the lower bound (the term in brackets) on the rate at which such fluid leaves subset \(S^*\). In the lower bound (the term in brackets): \(\sum _{\begin{array}{c} u \in S^* \\ v \not \in S^* \end{array}}c_{uv}\) is the capacity of the graph cut from \(S^*\) to \(V {\setminus } S^*\); \((\max _{e \in E}c_e|E|2^K)\) is a constant depending only on the model parameters, and \(\alpha >0\) can be chosen arbitrarily small. It can be checked that the same lower bound holds as is for a multi-source network as well. Consequently, in our multi-source case, the above derivative estimate still holds if we replace the fluid arrival rate \(\lambda _s\) in the right-hand side by \(\sum _{u\in S^*} \lambda _u\):

Given this, the rest of the proof of theorem 3 in [11] applies, if we use (2.1) (with \(S = S^*\)) instead of \(\lambda _s < \sum _{\begin{array}{c} u \in S^* \\ v \not \in S^* \end{array}}c_{uv}\).

Appendix B: Dynamics of the stage profile in the large reshuffling system

1.1 Appendix B.1: Hydrodynamic model definition and convergence. Main conjecture.

Suppose that N is very large and a stage-profile \(\phi ^N_{RS}(\cdot )\) is close to a fixed linear stage-profile \(\xi x, ~0\leqslant x \leqslant 1\), where \(\xi >0\) is a constant density. Let us see what is the corresponding average number H of useful packets, competing for a link at its communication epoch. Based on the discussion following Conjecture 8.5, we should expect that \(H=\xi \). Let us see if this is the case. Consider a pre-limit system with large N. Recall that the point \(\gamma ^N_{i-1}\) in the transformed system corresponds to stage \(i=1,2,\ldots , N-1\) in the original system, and the length of \([\gamma ^N_{i-1},\gamma ^N_{i})\) interval is given in (7.4). Then the expected number of stage i packets in the original system is approximately

Each stage i packet competes for given link with probability \([i(N-i)]/[N(N-1)]\). Therefore, the expected number of stage i packets competing for the link is

We see that the contribution of each stage i (in the original system) into H is equal to \(\xi /(N-1)\), and therefore \(H=\xi \), as we expected. Note that, given the density \(\xi \geqslant 0\), the corresponding average speed of any particle is given by the function

which is just (8.1) with \(\psi \) replaced by \(\xi \). We adopt the convention that, in (8.1), \(v(0)=1\).

Now, fix a small \(\epsilon >0\) and denote by \(H(\epsilon )\) the contribution into H of those stages i for which \(\gamma ^N_{i-1} \in (1/2-\epsilon ,1/2 + \epsilon )\), i.e. with corresponding locations \(\gamma ^N_{i-1}\) in the transformed system lying in the small interval \((1/2-\epsilon ,1/2 + \epsilon )\). Since the contributions of all stages are equal, namely \(\xi /(N-1)\), by using Proposition 7.4 we conclude that, as \(N\rightarrow \infty \), \(H(\epsilon )/H \rightarrow 1\). Then, when N is large, the value H is determined by by the stages located in the transformed system in a small neighborhood of the middle point 1/2. In other words, “only the density at the middle point 1/2 determines H.”

From here it is easy to conclude that, when N is large, if we have a stage-profile \(\phi ^N_{RS}(\cdot )\) close to a deterministic stage-profile \(\phi (\cdot )\) with any (not necessarily constant) bounded density \(\xi (x) = \phi '(x), ~0\leqslant x \leqslant 1,\) then, when N is large, the average number H of useful packets, competing for a link at its communication epoch is equal to \(\xi (1/2)\). This, in turn, implies that the instantaneous speed of particles in the transformed system is

We are now in position to describe the dynamics of the deterministic stage-profile \(\phi (\cdot ,t)\), approximating the dynamics of \(\phi ^N_{RS}(\cdot ,t)\) in the reshuffling system when N is large. Let \(\xi (x,t) = (\partial /\partial x) \phi (x,t)\) denote the density of \(\phi (\cdot ,t)\). The dynamics is such that the particle mass, at any point \(x\in [0,1)\), is shifted to the right at the instantaneous speed \(v(\xi (1/2,t))\). Given that the new particle mass arrives at point 0 at the constant rate \(\lambda \), the density \(\xi (0,t)\) that “appears” at the left boundary point 0 must be \(\lambda /v(\xi (1/2,t))\). Consider the mapping

which takes \(\xi (1/2,t)\) into \(\xi (0,t)\). Recall that we consider \(\lambda <1\). It is easily checked that: mapping \(M(\cdot )\) is continuous increasing; it has unique fixed point \(\psi =-\log (1-\lambda )\); a sequence of iterations \(u_{n+1} = M(u_n)\), \(n=0,1,\ldots \), is monotone strictly increasing [resp., strictly decreasing], converging to \(\psi \) when \(u_0 < \psi \) [resp., \(u_n>\psi \)].

Observe that the following relation holds for any t and any \(x\leqslant 1/2\):

Given this special structure of \(\xi (x,t)\), we see that, for any bounded (measurable) non-negative initial condition \(\xi (x,0), ~ 0 \leqslant x \leqslant 1,\) the unique solution is as follows. Let us (uniquely) extend \(\xi (x,0)\) to all \(x \in (-\infty , 1]\) via (B.3). By the properties of the mapping M, this extension is well-defined, the function \(sup_{x \leqslant 1/2} \xi (x,0) \leqslant \sup _{0\leqslant x\leqslant 1/2} \xi (x,0)\) and, moreover,

Define function

This is the time it takes for the total displacement (to the right) to reach value y; in other words, this is the time it takes for the mass initially located at point \(1/2 -y\) to reach point 1/2. By the boundedness of \(\xi (\cdot ,0)\), \(v(\xi (x,0))\) is bounded away from 0 (and it is always bounded above by 1). Therefore, \(\tau (\cdot )\) is Lipschitz and, moreover, has the derivative bounded away from 0; then so is its inverse function which we denote by \(y(\tau ), ~\tau \geqslant 0\). Finally, we formally define

To summarize, for any initial deterministic stage-profile \(\phi (x,0), ~0\leqslant x \leqslant 1,\) with bounded density \(\xi (x,0)\), we formally (and rigorously) defined the unique stage-profile \(\phi (x,t), ~0\leqslant x \leqslant 1,\) for any \(t\geqslant 0\), where \(\phi (x,t) = \int _0^x \xi (z,t) dz\). The object \(\phi (\cdot ,\cdot )\) we will call the hydrodynamic model (of the reshuffling system) with initial state \(\phi (\cdot ,0)\). In the process of formally defining a hydrodynamic model, we have rigorously proved the following

Theorem B.1

Let \(\lambda <1\) be fixed. Consider any hydrodynamic model \(\phi (\cdot ,\cdot )\) with the initial state \(\phi (x,0), ~0\leqslant x \leqslant 1,\) having bounded density \(\xi (x,0)\). Then, as \(t\rightarrow \infty \), its density \(\xi (\cdot ,t)\) uniformly converges to the constant density \(\psi \).

Remark B.2

It is not difficult to rigorously define a hydrodynamic model for an arbitrary initial state \(\phi (\cdot ,0)\) with finite total mass, \(\phi (1,0)<\infty .\) So, \(\phi (x,0)\) does not have to be absolutely continuous or even continuous. We do not do this to this, because it adds technical details, without giving new intuition.

Our conjecture about the dynamics of the stage-profile in the reshuffling system is as follows.

Conjecture B.3

Let \(\lambda <1\) be fixed. If the initial stage-profile \(\phi _{RS}^N(\cdot ,0)\) in the reshuffling system converges to a deterministic stage-profile \(\phi (\cdot ,0)\) (with bounded density), then the process \(\phi _{RS}^N(\cdot ,\cdot )\) converges (in appropriate sense) to the hydrodynamic model \(\phi (\cdot ,\cdot )\) with initial state \(\phi (\cdot ,0)\).

This conjecture complements the steady-state Conjectures 8.2(iv) and 8.5. In particular, Conjecture B.3 in conjunction with Theorem B.1 implies that as time \(t\rightarrow \infty \) goes to infinity, the normalized sojourn time of a packet entering the system at time t converges to \(-\log (1-\lambda )/\lambda \).

1.2 Appendix B.2: Example of the dynamics of the reshuffling system. Comparison to that under RU

In this subsection we run a simulation experiment to test Conjecture B.3 about the dynamics of the reshuffling system. Specifically, we consider an extreme scenario when the entire particle mass (“impulse”) is initially located at point 0 and there are no new arrivals, i.e. \(\lambda =0\).

Mean time in transformed system to reach point x. Impulse sizes 5 and 10

Full size image

Consider a hydrodynamic model with initial state \(\phi (\cdot ,0)\), with density

where \(a \in (0, 1)\). Then, \(\phi (\cdot ,0)\) is such that: the a-long interval, where the density is u, will move right at the constant speed 1 until time \(1/2-a\), when it “hits” the middle point 1/2; then for the time \(a/[(1-e^{-u})/u]=au/(1-e^{-u})\), while it overlaps with the middle point 1/2, it will move at the constant speed \((1-e^{-u})/u\); and finally, for the time 1/2, it again will move at speed 1 until the entire particle mass leaves the system. Now, if we keep the total initial mass \(c=au\) constant, and let \(u\rightarrow \infty \), in the limit we obtain the following hydrodynamic model: it has the particle mass (“impulse”) c initially concentrated at 0; this mass first moves at speed 1 until it reaches the middle point 1/2; then the mass stays at 1/2 for the time c; then it resumes the movement at speed 1 until reaching end point 1. In particular, sojourn time of the particle mass in the transformed system is \(c+1\), which is the approximation of the normalized delay of the packets when N is large.

Figure 5 show simulation results for a system with finite \(N=10000\), initialized with \(c A_N\) stage 1 packets, and with no new exogenous packet arrivals. Therefore, c is the “impulse size” of the corresponding hydrodynamic model. We consider \(c=5\) and \(c=10\). The figure shows the average time for a packet to reach point x in the transformed system. We see that each plot does resemble that for the corresponding hydrodynamic model, albeit the curve is smooth since we simulate a finite system; a packet first moves fast (at speed close to 1), then slows down in the middle of the transformed interval, then accelerates again (to speed close to 1). The slowdown is close to the limiting slowdown of \(c+1\).

Figure 5 also shows plots for the corresponding systems under RU discipline. In this case the system is initialized so that \(c A_N\) stage 1 packets are placed independently at nodes chosen uniformly at random. We compare RS and RU disciplines, because, in a sense, RS is a “simplified version” of RU, both choosing a random useful packet to transmit on a link. We observe the the delay profile under RU is quite similar to that of RS. In fact, the plots practically coincide up to some point \(x^*\) which is greater than 1/2. Recall, that majority of stages i in the original system are located close to point 1/2 in the transformed system. We conclude that, for the RU and RS systems with impulse initial state, the delays to reach the majority of stages i, except a small fraction of stages “at the end,” are practically same. For the small fraction of stages at the end, however, the delays under RU are larger. Informally speaking, this is due the fact that the conjectures that we made about the behavior of an RS system (which are very well confirmed by simulations), do not appear to hold under RU.

Appendix C: Additional Simulation Data for Sects. 6, 7 and 8

See Fig. 6

See Tables 2 and 3

The simulated distribution of the number of useful packets on a fixed link of reshuffling system, with \(\lambda = 0.5\). The distribution appears to converge to Poisson

Full size image

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions