Scheduling periodic messages on a shared link without buffering

Maël Guiraud () and Yann Strozecki ()
Additional contact information
Maël Guiraud: CESI Nanterre
Yann Strozecki: Université de Versailles-Saint-Quentin

Journal of Scheduling, 2024, vol. 27, issue 5, No 4, 484 pages

Abstract: Abstract Cloud RAN, a novel architecture for modern mobile networks, relocates processing units from antenna to distant data centers. This shift introduces the challenge of ensuring low latency for the periodic messages exchanged between antennas and their respective processing units. In this study, we tackle the problem of devising an efficient periodic message assignment scheme under the constraints of fixed message size and period without contention nor buffering. We address this problem by modeling it on a common network topology, wherein contention arises from a single shared link servicing multiple antennas. While reminiscent of coupled task scheduling, the introduction of periodicity adds a unique dimension to the problem. We study how the problem behaves with regard to the load of the shared link, and we focus on proving that, for load as high as possible, a solution always exists and it can be found in polynomial time. The main contributions of this article are two polynomial time algorithms, which find a solution for messages of any size and load at most 2/5 or for messages of size one and load at most $$\phi - 1$$ ϕ - 1 , the golden ratio conjugate. We also prove that a randomized greedy algorithm finds a solution on almost all instances with high probability, shedding light on the effectiveness of greedy algorithms in practical applications.

Keywords: Periodic scheduling; Greedy algorithm; Randomized algorithm; Experimental algorithms; C-RAN (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-024-00813-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:27:y:2024:i:5:d:10.1007_s10951-024-00813-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-024-00813-0

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().