This dissertation considers the problem of scheduling deadline-constrained packets in networks, an increasingly relevant problem, which due to the rise of time-sensitive applications such as teleconferencing and video streaming, has recently received renewed attention. To accommodate a diverse range of environments and scenarios, our work investigates single-hop and multi-hop networks, across various traffic models and network conditions, including wired and wireless settings.
We propose algorithms in each setting, with their performance evaluated by considering commonly used benchmarks in the related literature, such as the attained fraction of the real-time capacity region achieved in single-hop networks and the maximization of the cumulative weight of packets reaching their destinations within their deadlines in multi-hop networks. We explore traffic which is either worst-case, or stochastic, and provide different performance guarantees in each case.
The first part of our study focuses on scheduling real-time traffic in single-hop wireless networks with conflict-graph interference models. We propose randomized policies that achieve higher real-time efficiency ratios, compared to state-of-the-art existing algorithms, such as the Largest-Deficit-First algorithm. The research then extends to single-hop wireless networks with unreliable links due to channel fading, designing randomized algorithms that achieve efficiency ratios strictly higher than traditional scheduling algorithms, such as Maximum-Weight Scheduling.
The dissertation proceeds to examine online admission, routing, and scheduling algorithms for multi-hop wireless networks under a general interference graph model. It presents online algorithms that are competitive with the optimal offline algorithms and provides upper bounds on performance which demonstrate the asymptotic optimality of these results. Simulation results illustrate significant improvements over prior approaches.
Furthermore, the research addresses the problem of scheduling packets with end-to-end deadline constraints in both wired and wireless multi-hop networks, in the case of stochastic traffic. It illustrates the first near-optimal approximation algorithms under nontrivial assumptions on traffic and link capacity, showcasing significant improvements over worst-case algorithms in practical settings.
In conclusion, this dissertation contributes scheduling algorithms for deadline-constrained packet delivery in single and multi-hop networks, under various traffic and interference models, and in both wired and wireless settings. The proposed algorithms materially improve the state-of-the-art performance guarantees in each case.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/qbk2-s959 |
| Date | January 2024 |
| Creators | Tsanikidis, Christos |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0046 seconds