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. In particular, we investigate algorithms that employ 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Indirect Coflow Scheduling

  • Alexander Lindermayr,
  • Kirk Pruhs,
  • Andréa W. Richa,
  • Tegan Wilson

摘要

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. In particular, we investigate algorithms that employ 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.