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

F. Cecchi, P.M. van de Ven, S. Shneer

Research output: Contribution to journalConference articleAcademicpeer-review

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 di erent back-o rates, which govern how fast each node transmits. We find the back-o rates which provide the best end-to-end throughput and network robustness, and use these insights to determine the optimal back-o rates for general networks. We confirm numerically the resulting performance gains compared to the current practice of assigning all nodes the same back-o rate.

Fingerprint

Linear networks
Initial value problems
Parallel algorithms
Wireless networks
Throughput
Network protocols

Keywords

  • CSMA
  • Mean-field limits
  • Multi-hop networks
  • Random-access

Cite this

Cecchi, F. ; van de Ven, P.M. ; Shneer, S./ Mean-field limits for multi-hop random-access networks. In: ACM SIGMETRICS Performance Evaluation Review. 2018 ; Vol. 45, No. 3. pp. 109-122
@article{b672b1bef9ee44b4a18cba8d9ac3b31c,
title = "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 di erent back-o rates, which govern how fast each node transmits. We find the back-o rates which provide the best end-to-end throughput and network robustness, and use these insights to determine the optimal back-o rates for general networks. We confirm numerically the resulting performance gains compared to the current practice of assigning all nodes the same back-o rate.",
keywords = "CSMA, Mean-field limits, Multi-hop networks, Random-access",
author = "F. Cecchi and {van de Ven}, P.M. and S. Shneer",
year = "2018",
month = "3",
day = "20",
doi = "10.1145/3199524.3199544",
language = "English",
volume = "45",
pages = "109--122",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery, Inc",
number = "3",

}

Cecchi, F, van de Ven, PM & Shneer, S 2018, 'Mean-field limits for multi-hop random-access networks' ACM SIGMETRICS Performance Evaluation Review, vol. 45, no. 3, pp. 109-122. DOI: 10.1145/3199524.3199544

Mean-field limits for multi-hop random-access networks. / Cecchi, F.; van de Ven, P.M.; Shneer, S.

In: ACM SIGMETRICS Performance Evaluation Review, Vol. 45, No. 3, 20.03.2018, p. 109-122.

Research output: Contribution to journalConference articleAcademicpeer-review

TY - JOUR

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

AU - Cecchi,F.

AU - van de Ven,P.M.

AU - Shneer,S.

PY - 2018/3/20

Y1 - 2018/3/20

N2 - 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 di erent back-o rates, which govern how fast each node transmits. We find the back-o rates which provide the best end-to-end throughput and network robustness, and use these insights to determine the optimal back-o rates for general networks. We confirm numerically the resulting performance gains compared to the current practice of assigning all nodes the same back-o rate.

AB - 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 di erent back-o rates, which govern how fast each node transmits. We find the back-o rates which provide the best end-to-end throughput and network robustness, and use these insights to determine the optimal back-o rates for general networks. We confirm numerically the resulting performance gains compared to the current practice of assigning all nodes the same back-o rate.

KW - CSMA

KW - Mean-field limits

KW - Multi-hop networks

KW - Random-access

UR - http://www.scopus.com/inward/record.url?scp=85046644716&partnerID=8YFLogxK

U2 - 10.1145/3199524.3199544

DO - 10.1145/3199524.3199544

M3 - Conference article

VL - 45

SP - 109

EP - 122

JO - Performance Evaluation Review

T2 - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 3

ER -

Cecchi F, van de Ven PM, Shneer S. Mean-field limits for multi-hop random-access networks. ACM SIGMETRICS Performance Evaluation Review. 2018 Mar 20;45(3):109-122. Available from, DOI: 10.1145/3199524.3199544