《Computer Communications》：Efficient deployment of programmable switches for scalable network monitoring
编辑推荐：
本文提出懒 greedy算法和参数成本敏感的懒 greedy算法，分别解决遗留网络中可编程交换机部分部署的NP难问题，以最大化流量覆盖并考虑成本因素，实验证明其在大规模网络中有效。
阿里·纳迪姆·阿尔哈吉（Ali Nadim Alhaj）| 威尔逊·奈克·布基亚（Wilson Naik Bhukya）| 拉金德拉·普拉萨德·拉尔（Rajendra Prasad Lal）
海得拉巴大学计算机与信息科学学院，特伦甘纳邦，500046，印度
摘要
可编程交换机在网络测量和安全性方面取得了显著进展。然而，对于大多数网络来说，完全替换传统基础设施仍然不切实际。部分部署可编程交换机提供了一种具有成本效益且平衡的解决方案。本文探讨了两个与在传统网络中选择性部署支持P4协议的交换机相关的问题，以通过最大化不同流量的覆盖范围来增强网络范围内的监控能力。第一个问题是假设部署成本均匀的情况下最大化流量覆盖范围，我们提出了一种懒惰贪心算法，该算法能够在减少计算开销的情况下接近最优解。第二个问题是考虑成本差异的变体，为此我们提出了一种参数化的懒惰贪心算法。这种算法在监控性能和部署成本之间提供了权衡，使其适用于软件定义网络（SDN）环境。实验结果表明，这些方法在大规模网络拓扑中具有高流量覆盖率和准确的重点流量检测能力，证明了其有效性和可扩展性。
引言
网络监控是各种网络管理任务的基础，包括流量工程[1]、负载均衡[2]、服务质量[3]、异常检测以及安全应用[4]。这些应用包括分布式拒绝服务（DDoS）[5]、[6]和超级传播者检测[7]。随着软件定义网络（SDN）的出现，监控能力得到了显著提升。SDN引入了一个逻辑上集中的控制平面，使得测量数据的汇总更加高效，并实现了控制逻辑与网络状态之间的紧密集成。因此，SDN解决了传统网络架构中的许多固有限制。以往的网络测量研究主要集中在提高单个设备上的流量记录的准确性和效率上，采用的技术包括采样、基于流量的计数和草图绘制[8]。其中，草图绘制方法由于其在内存效率和紧凑表示大量流量方面的优势而显示出最大的潜力。
尽管SDN增强了了对网络行为的控制，但其自身的有效性仍受到传统交换机功能的限制，这些限制阻碍了高级测量方法在数据平面的应用。像支持P4协议的交换机这样的可编程交换机的出现大大扩展了数据平面的能力，使得可以直接在交换机硬件上部署更复杂、更精确的监控解决方案[9]。这一发展引发了大量研究兴趣，出现了许多旨在改进SDN测量能力的提案。一种非常有前景的技术是利用内存高效的数据结构（如草图绘制[10]），这些结构可以在可编程交换机中进行编程，从而以较小的精度损失为代价来最小化开销[11]。由于经济、技术和组织方面的限制，用可编程设备完全替换旧基础设施仍然不可行。因此，在现有的传统网络中逐步部署可编程交换机，形成混合式可编程网络，是更实际的过渡路径。然而，部分部署会降低流量的可见性，并引入新的问题，特别是在混合网络环境中维护草图绘制等方法的效率和效果。
一些研究专注于通过部分部署来改进网络功能[12]。其他研究则旨在提高重点流量的检测能力，例如[13]中提出的标准贪心机制和[14]中的基于整数线性规划（ILP）的模型。然而，之前的研究都没有考虑到监控问题、更换交换机的成本或与大规模网络相关的时间开销。在多个网络和拓扑结构上的实验表明，最大化不同流量的覆盖范围可以改善监控任务。这种增强有助于覆盖和检测重要的流量，这些流量可能是重点流量、DDoS流量或超级传播者[15]。
为了解决部分可编程交换机部署的问题，本文提出了一种懒惰贪心算法。逐步选择一部分传统交换机进行替换，确保每个部署阶段都能在考虑成本和可扩展性的同时最大化不同流量的覆盖范围。该算法根据交换机对被监控的不同流量的边际价值对交换机进行排序，有效利用优先队列来避免冗余计算。通过利用收益函数的次模性，该算法能够以较低的计算成本获得接近最优的解决方案。此外，本文还提出了一种考虑成本的懒惰贪心参数化算法，明确考虑了特定于交换机的部署成本，这些成本包括硬件价格、地理限制和运营开销等因素。通过将这些异构成本纳入选择过程，算法优先考虑最具成本效益的可编程交换机部署，从而最大化单位成本下的流量可见性。最近的研究表明，使用P4可编程交换机可以在运行中的网络中实现细粒度的流量测量[16]、[17]。这些研究侧重于数据平面监控原语的设计以及控制器集成，以在可编程设备部署后提高可见性。相比之下，本文关注的是一个互补问题：它在明确的预算限制下优化了传统网络中可编程交换机的放置和逐步部署。这些部分部署解决方案使网络运营商能够在不替换整个网络的情况下逐步提高可观测性，非常适合现实世界的网络拓扑。
- 1. 提出一种基于次模流量覆盖函数的懒惰贪心部署算法，用于在传统网络中逐步部署可编程交换机，以实现接近最优的监控性能。
- 2. 提出一种考虑每台交换机升级成本的参数化成本感知贪心部署模型，以在考虑部署成本的同时最大化流量可见性。
- 3. 在三种现实拓扑上评估所提出的方法。实验将提出的算法与现有技术进行了比较，展示了在流量覆盖范围、成本效率和可扩展性方面的改进。
本文的其余部分组织如下：第2节回顾了最重要的相关研究。第3节讨论了主要的研究问题。第4节介绍了我们的研究方法和解决研究问题的算法。第5节将我们提出的算法与现有解决方案进行了比较。第6节是对本文的简要总结。
相关工作
相关工作
大多数研究集中在以低成本和简单性逐步部署可编程交换机以满足某些监控目标上。一些研究探讨了逐步部署P4交换机的方法。例如，[14]提出了一种实现长期最大重点流量覆盖范围的贪心方法。同样，[13]提出了一种强调交换机间协调的分布式部分P4部署框架。此外，[14]将该方法扩展到了基于草图绘制的遥测技术中。
SDN中的可编程性级别
图1展示了软件定义网络（SDN）中的可编程性级别，并指出了三种不同的架构：纯传统数据平面、纯可编程数据平面和混合部署数据平面[13]。对于纯传统网络，系统基于简单的计数器，监控能力有限，这导致了较高的控制器开销。而纯可编程网络虽然提供了高端的可编程性，但也存在经济、组织等方面的限制。
方法论
本部分介绍了两种在网络中部署可编程交换机的算法。第一种是用于均匀成本交换机部署的懒惰贪心算法，旨在最大化流量覆盖范围。第二种是该模型的扩展版本，它通过分数编程实现了每单位成本的最大流量覆盖。本部分介绍了这些算法、它们的理论基础以及通过复杂性分析得出的可扩展性。
结果与实验
为了严格评估我们提出的部署策略的有效性，我们在均匀成本和成本感知环境下进行了一系列实验。我们将我们的算法与广泛用于网络测量和资源分配任务的几种现有技术进行了基准测试。实验旨在从覆盖范围和重点流量检测（流量可见性）以及部署效率（成本和时间）两个方面进行评估。
结论
本文解决了可编程交换机的可扩展和高效部分部署问题，以实现网络范围内的监控。首先，它提出了一种懒惰贪心算法，用于在均匀成本假设下解决选择可编程交换机的NP难题，利用次模优化实现了高效且接近最优的部署。其次，它提出了一种参数化成本感知的懒惰贪心变体，用于解决在异构交换机环境下部署的NP难题。
CRediT作者贡献声明
阿里·纳迪姆·阿尔哈吉（Ali Nadim Alhaj）：撰写——原始草稿、可视化、验证、软件开发、资源管理、方法论研究、调查、形式化分析、数据整理、概念化。
威尔逊·奈克·布基亚（Wilson Naik Bhukya）：撰写——审稿与编辑、可视化、验证、监督、资源管理、方法论研究、调查、形式化分析、数据整理、概念化。
拉金德拉·普拉萨德·拉尔（Rajendra Prasad Lal）：撰写——审稿与编辑、可视化、验证、监督、软件开发。
利益冲突声明
作者声明与本次提交内容无关的任何利益冲突。本研究是独立进行的，未受到其他个人或组织的影响。
