Accurate routing network status estimation is a key component in Software
Defined Networking. However, existing deep-learning-based methods for modeling
network routing are not able to extrapolate towards unseen feature
distributions. Nor are they able to handle scaled and drifted network
attributes in test sets that include open-world inputs. To deal with these
challenges, we propose a novel approach for modeling network routing, using
Graph Neural Networks. Our method can also be used for network-latency
estimation. Supported by a domain-knowledge-assisted graph formulation, our
model shares a stable performance across different network sizes and
configurations of routing networks, while at the same time being able to
extrapolate towards unseen sizes, configurations, and user behavior. We show
that our model outperforms most conventional deep-learning-based models, in
terms of prediction accuracy, computational resources, inference speed, as well
as ability to generalize towards open-world input.

本文提出了一种基于图神经网络的方法，较之传统深度学习方法，更能准确地建模网络路由，进行路由网络配置预测和时延估计。同时，该方法还具有较强的泛化能力，并能跨越不同网络规模和配置，更好地适应开放性预测需求。

路由网络延迟估计的开放世界学习图卷积方法

Open World Learning Graph Convolution for Latency Estimation in Routing Networks

We propose combinatorial cascading bandits, a class of partial monitoring
problems where at each step a learning agent chooses a tuple of ground items
subject to constraints and receives a reward if and only if the weights of all
chosen items are one. The weights of the items are binary, stochastic, and
drawn independently of each other. The agent observes the index of the first
chosen item whose weight is zero. This observation model arises in network
routing, for instance, where the learning agent may only observe the first link
in the routing path which is down, and blocks the path. We propose a UCB-like
algorithm for solving our problems, CombCascade; and prove gap-dependent and
gap-free upper bounds on its $n$-step regret. Our proofs build on recent work
in stochastic combinatorial semi-bandits but also address two novel challenges
of our setting, a non-linear reward function and partial observability. We
evaluate CombCascade on two real-world problems and show that it performs well
even when our modeling assumptions are violated. We also demonstrate that our
setting requires a new learning algorithm.

提出了组合级联赌博算法，对分布随机的约束问题解决一类非线性奖励函数部分可观测性问题，提供了一种基于 UCB 算法的求解方法，并论证了与时间复杂度无关的期望损失界限和时间关联的损失上限。在两个真实世界的网络路径问题测试中，算法表现良好，说明该算法对于模型假设违反的情况同样稳健有效，这个设置还需要提出新的学习算法。