Timezone: »

 
Poster
Adaptive Probing Policies for Shortest Path Routing
Aditya Bhaskara · Sreenivas Gollapudi · Kostas Kollias · Kamesh Munagala

Thu Dec 10 09:00 AM -- 11:00 AM (PST) @ Poster Session 5 #1671
in Poster Session 6 »
Inspired by traffic routing applications, we consider the problem of finding the shortest path from a source $s$ to a destination $t$ in a graph, when the lengths of the edges are unknown. Instead, we are given {\em hints} or predictions of the edge lengths from a collection of ML models, trained possibly on historical data and other contexts in the network. Additionally, we assume that the true length of any candidate path can be obtained by {\em probing} an up-to-date snapshot of the network. However, each probe introduces a latency, and thus the goal is to minimize the number of probes while finding a near-optimal path with high probability. We formalize this problem and show assumptions under which it admits to efficient approximation algorithms. We verify these assumptions and validate the performance of our algorithms on real data.

Author Information

Aditya Bhaskara (University of Utah)
Sreenivas Gollapudi (Google Research)
Kostas Kollias (Google Research)
Kamesh Munagala (Duke University)

More from the Same Authors