Selecting multiple network paths to reduce longest delay
Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting
Machine Learning
Summary
This work looks at how to send data using several routes through a network at the same time while keeping the longest travel time among these routes as short as possible. The authors consider that each route's travel time is uncertain and that pathways have limits on how many data transmissions they can handle. They model this as a semi-bandit problem and suggest a method to pick the best set of paths to minimize delays. The aim is to improve efficiency when sending data in parallel through complex networks.
What this means in practice
- •For network schedulers: Optimize choosing multiple routes simultaneously to reduce maximum delay for data transmissions over networks with capacity limits.
- •For cloud infrastructure teams: Improve reliability and speed of parallel data transfers between data centers by selecting paths that minimize worst-case transfer times.
Authors
Shunsuke Aoki, Atsuyoshi Nakamura
Abstract
When performing parallel data transmission through a network using multiple paths, it is practically important to minimize the maximum transmission time among the selected paths. This study addresses an online problem in which $k$ paths from an origin vertex to a destination vertex must be selected at each time step within a network represented as a directed graph. Here, the number of paths going through each edge in each parallel data transmission is limited to its capacity, and the time required for transmission is determined stochastically. We formulate the semi-bandit problem of selecting a set of paths to minimize the maximum traversal time among the selected paths and propose an algorithm to solve it.