Comparative Synthesis: Learning Near-Optimal Network Designs by Query
Comparative Synthesis: Learning Near-Optimal Network Designs by Query
复制标题
DOI：
10.1145/3571197
复制
发表时间：
2023-01-01
影响因子：
1.8
通讯作者：
Rao，Sanjay
中科院分区：
文献类型：
--
作者：
Wang，Yanjun;Li，Zixuan;Rao，Sanjay
在管理广域网时，网络架构师必须决定如何平衡多个相互冲突的指标，并确保公平分配竞争流量，同时优先考虑关键流量。实践状况带来了挑战，因为架构师必须使用抽象概念（例如效用函数和临时手动调整旋钮）将其意图精确编码到正式的优化模型中。在本文中，我们提出了第一次努力，合成最优网络设计与不确定的目标，使用交互式程序合成为基础的方法。我们做了三个贡献。首先，我们提出了比较合成，一个交互式的合成框架，通过两种查询（搜索和比较）产生接近最优的方案（网络设计），没有明确的目标。其次，我们开发了第一个学习算法比较合成，其中一个投票引导学习者挑选最翔实的查询在每次迭代。我们目前的理论分析的算法的收敛速度。第三，我们实现了Net10Q，基于我们的方法的系统，并证明其有效性的四个现实世界的网络案例研究，使用黑盒预言机和模拟实验，以及试点用户研究，包括网络研究人员和从业人员。理论和实验结果表明，我们的方法的承诺。
When managing wide-area networks, network architects must decide how to balance multiple conflicting metrics, and ensure fair allocations to competing traffic while prioritizing critical traffic. The state of practice poses challenges since architects must precisely encode their intent into formal optimization models using abstract notions such as utility functions, and ad-hoc manually tuned knobs. In this paper, we present the first effort to synthesize optimal network designs with indeterminate objectives using an interactive program-synthesis-based approach. We make three contributions. First, we present comparative synthesis, an interactive synthesis framework which produces near-optimal programs (network designs) through two kinds of queries (Validate and Compare), without an objective explicitly given. Second, we develop the first learning algorithm for comparative synthesis in which a voting-guided learner picks the most informative query in each iteration. We present theoretical analysis of the convergence rate of the algorithm. Third, we implemented Net10Q, a system based on our approach, and demonstrate its effectiveness on four real-world network case studies using black-box oracles and simulation experiments, as well as a pilot user study comprising network researchers and practitioners. Both theoretical and experimental results show the promise of our approach.