Analysis of d-ary tree algorithms with successive interference cancellation

Quirin Vogel; Yash Deshpande; Cedomir Stefanović; Wolfgang Kellerer

doi:10.1017/jpr.2023.107

Analysis of d-ary tree algorithms with successive interference cancellation

Quirin Vogel
, Yash Deshpande
, Cedomir Stefanović
, Wolfgang Kellerer

Chair of Communication Networks

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.

Original language	English
Pages (from-to)	1075-1105
Number of pages	31
Journal	Journal of Applied Probability
Volume	61
Issue number	3
DOIs	https://doi.org/10.1017/jpr.2023.107
State	Published - 1 Sep 2024

Keywords

Random access
asymptotic analysis
functional equation
splitting algorithms

Access to Document

10.1017/jpr.2023.107

Cite this

@article{2e6ccb27ce884934a71788bb85c26977,

title = "Analysis of d-ary tree algorithms with successive interference cancellation",

abstract = "We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.",

keywords = "Random access, asymptotic analysis, functional equation, splitting algorithms",

author = "Quirin Vogel and Yash Deshpande and Cedomir Stefanovi{\'c} and Wolfgang Kellerer",

note = "Publisher Copyright: {\textcopyright} The Author(s), 2024.",

year = "2024",

month = sep,

day = "1",

doi = "10.1017/jpr.2023.107",

language = "English",

volume = "61",

pages = "1075--1105",

journal = "Journal of Applied Probability",

issn = "0021-9002",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - Analysis of d-ary tree algorithms with successive interference cancellation

AU - Vogel, Quirin

AU - Deshpande, Yash

AU - Stefanović, Cedomir

AU - Kellerer, Wolfgang

N1 - Publisher Copyright: © The Author(s), 2024.

PY - 2024/9/1

Y1 - 2024/9/1

N2 - We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.

AB - We calculate the mean throughput, number of collisions, successes, and idle slots for random tree algorithms with successive interference cancellation. Except for the case of the throughput for the binary tree, all the results are new. We furthermore disprove the claim that only the binary tree maximizes throughput. Our method works with many observables and can be used as a blueprint for further analysis.

KW - Random access

KW - asymptotic analysis

KW - functional equation

KW - splitting algorithms

UR - https://www.scopus.com/pages/publications/85186102334

U2 - 10.1017/jpr.2023.107

DO - 10.1017/jpr.2023.107

M3 - Article

AN - SCOPUS:85186102334

SN - 0021-9002

VL - 61

SP - 1075

EP - 1105

JO - Journal of Applied Probability

JF - Journal of Applied Probability

IS - 3

ER -

Analysis of d-ary tree algorithms with successive interference cancellation

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this