Indirect Coflow Scheduling
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915863700963328 |
|---|---|
| author | Lindermayr, Alexander Pruhs, Kirk Richa, Andréa W. Wilson, Tegan |
| author_facet | Lindermayr, Alexander Pruhs, Kirk Richa, Andréa W. Wilson, Tegan |
| contents | We consider routing in reconfigurable networks, which is also known as coflow scheduling in the literature. The algorithmic literature generally (perhaps implicitly) assumes that the amount of data to be transferred is large. Thus the standard way to model a collection of requested data transfers is by an integer demand matrix $D$, where the entry in row $i$ and column $j$ of $D$ is an integer representing the amount of information that the application wants to send from machine/node $i$ to machine/node $j$. A feasible coflow schedule is then a sequence of matchings, which represent the sequence of data transfers that covers $D$. In this work, we investigate coflow scheduling when the size of some of the requested data transfers may be small relative to the amount of data that can be transferred in one round. fractional matchings and/or that employ indirect routing, and compare the relative utility of these options. We design algorithms that perform much better for small demands than the algorithms in the literature that were designed for large data transfers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12854 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Indirect Coflow Scheduling Lindermayr, Alexander Pruhs, Kirk Richa, Andréa W. Wilson, Tegan Data Structures and Algorithms Networking and Internet Architecture We consider routing in reconfigurable networks, which is also known as coflow scheduling in the literature. The algorithmic literature generally (perhaps implicitly) assumes that the amount of data to be transferred is large. Thus the standard way to model a collection of requested data transfers is by an integer demand matrix $D$, where the entry in row $i$ and column $j$ of $D$ is an integer representing the amount of information that the application wants to send from machine/node $i$ to machine/node $j$. A feasible coflow schedule is then a sequence of matchings, which represent the sequence of data transfers that covers $D$. In this work, we investigate coflow scheduling when the size of some of the requested data transfers may be small relative to the amount of data that can be transferred in one round. fractional matchings and/or that employ indirect routing, and compare the relative utility of these options. We design algorithms that perform much better for small demands than the algorithms in the literature that were designed for large data transfers. |
| title | Indirect Coflow Scheduling |
| topic | Data Structures and Algorithms Networking and Internet Architecture |
| url | https://arxiv.org/abs/2511.12854 |