Competitive Analysis of Online Path Selection: Impacts of Path Length, Topology, and System-Level Costs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914860725436416 |
|---|---|
| author | Cao, Ying Yu, Siyuan Tan, Xiaoqi Tsang, Danny H. K. |
| author_facet | Cao, Ying Yu, Siyuan Tan, Xiaoqi Tsang, Danny H. K. |
| contents | Consider a communication network to which a sequence of self-interested users come and send requests for data transmission between nodes. This work studies the question of how to guide the path selection choices made by those online-arriving users and maximize the social welfare. Competitive analysis is the main technical tool. Specifically, the impacts of path length bounds and topology on the competitive ratio of the designed algorithm are analyzed theoretically and explored experimentally. We observe intricate and interesting relationships between the empirical performance and the studied network parameters, which shed some light on how to design the network. We also investigate the influence of system-level costs on the optimal algorithm design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05239 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Competitive Analysis of Online Path Selection: Impacts of Path Length, Topology, and System-Level Costs Cao, Ying Yu, Siyuan Tan, Xiaoqi Tsang, Danny H. K. Data Structures and Algorithms Networking and Internet Architecture Consider a communication network to which a sequence of self-interested users come and send requests for data transmission between nodes. This work studies the question of how to guide the path selection choices made by those online-arriving users and maximize the social welfare. Competitive analysis is the main technical tool. Specifically, the impacts of path length bounds and topology on the competitive ratio of the designed algorithm are analyzed theoretically and explored experimentally. We observe intricate and interesting relationships between the empirical performance and the studied network parameters, which shed some light on how to design the network. We also investigate the influence of system-level costs on the optimal algorithm design. |
| title | Competitive Analysis of Online Path Selection: Impacts of Path Length, Topology, and System-Level Costs |
| topic | Data Structures and Algorithms Networking and Internet Architecture |
| url | https://arxiv.org/abs/2407.05239 |