자료유형  

 학위논문

Control Number  

0017160647

International Standard Book Number  

9798382261027

Dewey Decimal Classification Number  

004

Main Entry-Personal Name  

Tsanikidis, Christos.

Publication, Distribution, etc. (Imprint  

[S.l.] : Columbia University., 2024

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2024

Physical Description  

168 p.

General Note  

Source: Dissertations Abstracts International, Volume: 85-10, Section: A.

General Note  

Advisor: Ghaderi, Javad.

Dissertation Note  

Thesis (Ph.D.)--Columbia University, 2024.

Summary, Etc.  

요약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.

Subject Added Entry-Topical Term  

Computer science.

Subject Added Entry-Topical Term  

Communication.

Subject Added Entry-Topical Term  

Information science.

Index Term-Uncontrolled  

Wireless networks

Index Term-Uncontrolled  

Single-hop

Index Term-Uncontrolled  

Multi-hop

Index Term-Uncontrolled  

Scheduling algorithms

Added Entry-Corporate Name  

Columbia University Electrical Engineering

Host Item Entry  

Dissertations Abstracts International. 85-10A.

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:658576