Mean-field limits for multi-hop random-access networks

Abstract

Recent years have seen wireless networks increasing in scale, interconnecting a vast number of devices over large areas. Due to their size these networks rely on distributed algorithms for control, allowing each node to regulate its own activity. A popular such algorithm is Carrier-Sense Multi- Access (CSMA), which is at the core of the well-known 802.11 protocol. Performance analysis of CSMA-based networks has received significant attention in the research literature in recent years, but focused almost exclusively on saturated networks where nodes always have packets available.

However, one of the key features of emerging large-scale networks is their ability to transmit packets across large distances via multiple intermediate nodes (multi-hop). This gives rise to vastly more complex dynamics, and to phenomena not captured by saturated models. Consequently, performance analysis of multi-hop random-access networks remains elusive. Based on the observation that emerging multi-hop networks are typically dense and contain a large number of nodes, we consider the mean-field limit of multihop CSMA networks. We show that the equilibrium point of the resulting initial value problem provides a remarkably accurate approximation for the pre-limit stochastic network in stationarity, even for sparse networks with few nodes. Using these equilibrium points we investigate the performance of linear networks under different back-off rates, which govern how fast each node transmits. We find the back-off rates which provide the best end-to-end throughput and network robustness, and use these insights to determine the optimal back-off rates for general networks. We confirm numerically the resulting performance gains compared to the current practice of assigning all nodes the same back-off rate.

References

1. A. Aziz, S. Shneer, P. Thiran (2013). Wireless multi-hop networks beyond capacity. In: Proc. LANMAN.
2. R.R. Boorstyn, A. Kershenbaum, B. Maglaris, V. Sahin (1987). Throughput analysis in multihop CSMA packet radio networks. IEEE Trans. Commun., 35, 267-274.
3. C. Bordenave, D. McDonald, A. Proutiere (2008). Performance of random medium access control, an asymptotic approach. ACM SIGMETRICS Perf. Eval. Rev., 36 (1), 1-12.
4. F. Cecchi, S.C. Borst, J.S.H. van Leeuwaarden (2014). Throughput of CSMA networks with buffer dynamics. Perf. Eval., 79, 216-234
5. F. Cecchi, S.C. Borst, J.S.H. van Leeuwaarden, P.A. Whiting (2016). CSMA networks in a many-sources regime: A mean-field approach. In: Proc. IEEE Infocom.
6. F. Cecchi, S.C. Borst, J.S.H. van Leeuwaarden, P.A. Whiting (2016). Mean-field limits for large-scale random-access networks. arXiv preprint arXiv:1611.09723.
7. J. Cho, J.Y. Le Boudec, Y. Jiang (2012). On the asymptotic validity of the decoupling assumption for analyzing 802.11 MAC protocol. IEEE Trans. Inf. Theo., 58 (11), 6879-6893.
8. M. Durvy, O. Dousse, P. Thiran (2009). Self-organization properties of CSMA/CA systems and their consequences on fairness. IEEE Trans. Inf. Theo., 55 (3), 931-943.
9. D. Evans (2011). The internet of things. How the next evolution of the internet is changing everything, Whitepaper, Cisco (IBSG).
10. J. Ghaderi, R. Srikant (2010). On the design of effcient CSMA algorithms for wireless networks. In: Proc. IEEE Dec. Contr., 954-959.
11. P.T. Harker, J.S. Pang (1990). Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math. Progr., 48 (1-3), 161-220.
12. B. van Houdt (2016). Explicit back-off rates for achieving target throughputs in CSMA/CA networks. IEEE/ACM Trans. Netw., 25 (2), 765-778.
13. B. van Houdt (2017). Free Energy Approximations for CSMA networks. arXiv preprint arXiv:1703.10500.
14. L. Jiang, J. Walrand (2010). A distributed CSMA algorithm for throughput and utility maximization in wireless networks. IEEE/ACM Trans. Netw., 18 (3), 960-972.
15. R. Laufer, L. Kleinrock (2016). The capacity of wireless CSMA/CA networks. IEEE/ACM Trans. Netw., 24 (3), 1518-1532.
16. S.C. Liew, C.H. Kai, J. Leung, B. Wong (2010). Back-of-the-envelope computation of throughput distributions in CSMA wireless networks. IEEE Trans. Mob. Comp. 9 (9), 1319-1331.
17. S. Rajagopalan, D. Shah, J. Shin (2009). Network adiabatic theorem: an efficient randomized protocol for content resolution. In: Proc. ACM SIGMETRICS Perf. Eval. Rev., 133-144.
18. S. Shneer, P.M. van de Ven (2015). Stability and instability of individual nodes in multi-hop wireless CSMA/CA networks. In: Proc. ACM SIGMETRICS Perf. Eval. Rev., 43 (2), 19-21.
19. P.S. Swamy, V.P.K. Bellam, R.K. Ganti, K. Jagannathan (2016). Efficient CSMA based on Kikuchi approximation. In: Proc. IEEE SPCOM.
20. P.M. van de Ven, S.C. Borst, J.S.H. van Leeuwaarden, A. Proutière (2010). Insensitivity and stability of random-access networks. Perf. Eval., 67 (11), 1230-1242.
21. P.M. van de Ven, A.J.E.M. Janssen, J.S.H. van Leeuwaarden, S.C. Borst (2011). Achieving target throughputs in random-access networks. Perf. Eval., 68 (11), 1103-1117.
22. V. Vorotnikov (2012). Partial stability and control. Springer Science & Business Media
23. X. Wang, K. Kar (2005). Throughput modeling and fairness issues in CSMA/CA based ad-hoc networks. In: Proc. IEEE Infocom.
24. S. Yun, J. Shin, Y. Yi (2015). CSMA using the Bethe approximation: scheduling and utility maximization. IEEE Trans. Inf. Theo., 61 (9), 4776-4787.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis