当前位置: 首页 > article >正文

文献阅读记录8--Enhanced Machine Learning Sketches for Network Measurements

一、预备知识

网络测量中的噪声:主要指的是由于哈希冲突流量特征变化导致的Sketch估计结果与真实值之间的偏差

二、论文部分

题目:Enhanced Machine Learning Sketches for Network Measurements

创新点:首次将机器学习与网络测量中的草图技术相结合,提出了一种动态适应网络流量特征变化的通用框架

2 Related Works

该部分详细介绍了现有的草图技术及其在流大小、Top-K流和流数量估计中的应用,同时指出了这些技术在面对网络流量特征变化时的局限性。这些背景知识为文章后续提出的基于机器学习的优化框架提供了研究动机,展示了如何通过机器学习技术克服现有草图技术的不足。

1. 流大小估计(Estimation of Flow Size)

介绍了两种经典的草图技术——Count-Min (CM) SketchConservative Update (CU) Sketch,它们被广泛用于记录和估计流的大小。这两种草图的数据结构相同,由多个计数器数组和哈希函数组成。它们的主要区别在于更新规则:

  • CM Sketch:对每个流的哈希计数器都加1。

  • CU Sketch:仅对最小的哈希计数器加1。

工作原理:
  • 记录:当数据包到达时,根据哈希函数将数据包的流ID映射到多个计数器,并根据上述规则更新计数器。

  • 查询:通过计算流ID的哈希值,找到对应的计数器,并返回最小计数器的值作为流大小的估计值。

局限性:

尽管这些草图技术在特定场景下表现良好,但它们的准确性高度依赖于网络流量的特征。例如,当流量特征发生变化时,草图中存储的信息噪声会增加,导致估计误差增大。

2. Top-K流估计(Estimation of Top-K Flows)

Top-K流问题是指识别具有最大数据包数量的K个流,并估计它们的大小。最常用的方法是结合CM Sketch和最小堆(min-heap)来实现:

  • 记录:在CM Sketch中插入数据包,并根据最小堆的规则更新堆中的流信息。

  • 查询:返回最小堆中的K个流及其大小估计值。

局限性:

Top-K流估计不仅面临估计误差的问题,还可能因CM Sketch的过度估计而误将非Top-K流插入堆中,导致误分类误差。这种误差在网络流量特征变化时尤为明显。

3. 流数量估计(Estimation of the Number of Flows)

流数量估计是网络测量中的另一个重要任务。文章重点介绍了FM Sketch,它通过哈希函数将流ID映射到位图中,并通过统计位图中的零位位置来估计流的数量。

工作原理:
  • 记录:对每个到达的数据包,计算其哈希值,并将对应的位图位置设置为1。

  • 查询:通过统计位图中最低零位的位置,使用特定公式估计流的数量。

局限性:

FM Sketch的准确性依赖于哈希函数的分布和位图的大小。当位图大小较小时,估计误差会显著增加,尤其是在网络流量特征变化时。

总结

所有这些草图技术的共同问题是它们的准确性高度依赖于网络流量的特征。当流量特征发生变化时,这些草图技术无法准确去除噪声,导致估计误差增加。此外,现有的草图技术通常需要对网络流量特征做出假设,这限制了它们的通用性和适应性。

3 Method

1.采样(Sampling)

由于网络流量的速率很高,直接使用所有数据包来训练机器学习模型会导致计算开销过大。因此,作者提出了一种采样方法,只使用一小部分数据包来生成学习草图。采样率可以根据网络管理员的资源限制进行调整。

2.构建学习草图(Building Learning Sketch)

学习草图是使用采样数据包生成的草图,用于训练机器学习模型。学习草图的大小通常比常规草图小,但足以提供足够的信息用于模型训练。

  • 学习草图的大小与采样率成反比。

  • 学习草图可以由交换机生成并发送到服务器,或者直接在服务器上生成。

3.特征提取和训练集生成(Feature Extraction and Training Set Generation)

从学习草图中提取特征,并生成用于训练机器学习模型的样本。特征的选择取决于要测量的流级指标,例如流大小、Top-K流或流的数量。

4.训练(Training)

使用提取的特征和训练样本训练机器学习模型。由于草图技术通常应用于高速数据流场景,因此作者选择了简单且训练速度快的线性回归模型。

5.查询(Querying)

使用训练好的机器学习模型和常规草图回答查询请求。当查询一个流的大小或Top-K流时,框架会根据模型的输出提供更准确的估计值。

4 Case Studies

1.Estimating Flow Sizes

Flow Size Estimation的基本版本:

目标
  • 主要目标:识别容易产生高误差的流(error-prone flows),并对这些流使用机器学习模型进行优化估计,从而提高整体的估计准确性。

  • 背景:传统的草图技术(如CM Sketch和CU Sketch)在某些情况下会产生较大的估计误差,尤其是在网络流量特征变化时。机器学习可以动态学习这些特征,从而减少误差。

方法
1. 识别易出错流(Error-Prone Flows)
  • 观察:作者通过实验发现,对于那些估计误差较大的流,其最小计数器值(smallest counter value)通常远小于第二小的计数器值(second smallest counter value)。基于这一观察,作者提出了一种简单的规则来识别这些流。

  • 规则:对于一个流,计算其所有哈希计数器的值,并找到最小值 v1​ 和第二小的值 v2​。如果 ∣v1​−v2​∣ 大于某个阈值 θ,则认为该流是易出错流。

  • 阈值选择:阈值 θ 是一个超参数,需要根据实验结果进行调整。在实验中,作者发现选择合适的 θ 对性能有显著影响。

2. 特征提取(Feature Extraction)
  • 特征选择:对于每个易出错流,使用其在学习草图中的所有哈希计数器值作为特征。这些计数器值能够反映流的大小和噪声信息。

  • 目标值(Target Value):使用哈希表记录的实际流大小作为训练的目标值。

3. 模型训练(Training)
  • 模型选择:选择线性回归模型作为机器学习算法,因为它计算简单、训练速度快,适合在高速数据流场景中使用。

  • 训练过程:使用提取的特征和目标值训练线性回归模型,得到一个能够估计流大小的模型。

  • 模型公式

    • 假设函数:

    • 其中,\alpha _{i} 是学习参数,A_{i}[h_{i} mod\ w ] 是第 i 个哈希计数器的值。

4. 查询优化(Querying)
  • 查询过程:当查询一个流的大小时,首先判断该流是否为易出错流。

    • 如果是易出错流,则使用训练好的线性回归模型进行估计。

    • 如果不是易出错流,则使用传统的草图技术(如CM Sketch或CU Sketch)的估计值。


Flow Size Estimation的增强版本: 

增强版本的核心目标
  • 目标:解决基本版本的两个主要问题:

    1. 特征信息不足:基本版本仅使用哈希计数器值作为特征,可能无法提供足够的噪声和冲突信息。

    2. 对易出错流的依赖:基本版本依赖于阈值 θ 来识别易出错流,但选择合适的阈值较为困难,且模型性能对阈值非常敏感。

  • 方法:增强版本通过引入新的特征(如冲突ID信息)和流分类方法,进一步优化机器学习模型的性能。

增强版本的主要改进
1. 新的特征选择(New Feature Selection)
  • 冲突ID信息:在基本版本中,仅使用流的哈希计数器值作为特征,可能无法充分反映噪声和冲突信息。增强版本通过引入冲突ID信息(conflict IDs),为模型提供更多关于噪声的特征。

  • Pointer-Based Version(增强版本一)

    • 方法:为每个计数器添加指针,指向最小计数器的地址。通过这种方式,可以记录冲突ID的信息,从而为模型提供更多关于噪声的特征。

    • 问题:指针会增加内存开销,因此需要更高效的存储方法。

2. 新的特征存储方法(New Feature Storage)
  • 增强版本二(Enhanced Version Two)

    • 方法:将每个计数器分为两部分(假设计数器总长度为 b 位,每部分 b/2 位)。第一部分用于存储冲突ID信息,第二部分用于存储计数器值。

    • 存储逻辑

      • 如果某个计数器的值需要超过 b/2 位来表示,则不存储冲突ID信息。

      • 如果某个计数器的值和冲突ID信息都可以用 b/2 位表示,则将冲突ID信息存储在第一部分。

      • 通过一个额外的标志位(flag)来标识计数器是否存储了冲突ID信息。

    • 优势:这种方法在不显著增加内存开销的情况下,为模型提供了更多的特征信息。

流分类(Flow Classification)
  • 分类方法:增强版本不再依赖于阈值 θ 来识别易出错流,而是根据流的特征自动对流进行分类。

  • 分类逻辑

    • 对于每个流,根据其哈希计数器中包含的特征数量(如冲突ID信息的数量),将流分为不同的类别。

    • 例如,如果一个流的哈希计数器中有更多的大值,则该流更可能是大象流,噪声对其影响较小;反之,如果一个流的哈希计数器中有更多的小值,则该流更可能是老鼠流,噪声对其影响较大。

    • 自动分类:根据特征数量,流被自动分为 d+1 个类别(其中 d 是哈希函数的数量),每个类别对应不同的模型。

模型训练(Model Training)
  • 分类模型训练:为每个类别训练一个独立的线性回归模型。每个模型根据其对应的特征数量进行优化。

  • 模型公式

 其中,D_{j}表示冲突ID信息的特征值,\alpha _{i}\beta _{j}是学习参数。

查询优化(Querying)
  • 查询过程:当查询一个流的大小时,根据流的特征数量选择对应的模型进行估计。

    • 如果流的特征数量较少(如老鼠流),则使用包含冲突ID信息的模型进行估计。

    • 如果流的特征数量较多(如大象流),则使用更简单的模型进行估计。

  • 优势:通过分类和选择合适的模型,增强版本能够更准确地估计不同类型的流大小,同时减少对阈值 θ 的依赖。

2.Estimating Top-K Flows

Top-K流估计的任务描述
  • 目标:识别网络中流量最大的K个流,并准确估计它们的大小。

  • 传统方法:使用CM Sketch记录流的大小信息,并结合Min-Heap数据结构动态维护当前Top-K流。然而,这种方法存在以下问题:

    1. 误分类误差(Misclassification Error):一些不属于Top-K的流可能被错误地插入到Min-Heap中,导致误判。

    2. 估计误差(Estimation Error):CM Sketch的估计值可能因噪声而不够准确。

机器学习优化方法
1. 减少误分类误差(Reducing Misclassification Error)
  • 问题分析:误分类误差主要由于CM Sketch的过度估计导致一些小流量(老鼠流)被错误地插入到Min-Heap中。

  • 解决方案:利用机器学习模型识别哪些流不应该被归为Top-K流,从而减少误分类误差。

    • 特征选择:使用流在Min-Heap中的初始计数值和最终计数值作为特征,因为这些值能够更好地反映流的大小变化。

    • 模型选择:使用逻辑回归模型进行分类,判断一个流是否属于Top-K流。

    • 分类公式

      其中,

      • A_{i}[h_{i}\left ( f \right ) mod\ w ] 是哈希计数器的值。

      • final\left ( f\right )initial\left ( f \right ) 分别是流在Min-Heap中的最终和初始计数值。

      • label 是布尔值,表示流是否属于Top-K流。

2. 减少估计误差(Reducing Estimation Error)
  • 问题分析:即使流被正确识别为Top-K流,CM Sketch的估计值仍可能因噪声而不准确。

  • 解决方案:使用线性回归模型对Top-K流的大小进行优化估计。

    • 特征选择:使用流的哈希计数器值作为特征。

    • 模型选择:使用线性回归模型进行估计。

    • 估计公式

增强版本(Enhanced Version)

为了进一步优化Top-K流估计的性能,作者提出了增强版本,通过引入更多的特征和更复杂的模型来提高准确性。

  • 特征选择优化:除了上述特征外,增强版本还引入了冲突ID信息等额外特征。

  • 模型训练优化:为不同类型的流(如大象流和老鼠流)训练不同的模型,以更好地适应不同流量特征。

  • 查询优化:在查询时,结合分类模型和估计模型的结果,返回Top-K流及其估计大小。

 3.Estimating Number of Flows

流数量估计的任务描述
  • 目标:准确估计网络中不同流的总数。

  • 传统方法:使用FM Sketch(Flajolet-Martin Sketch)进行估计。FM Sketch通过哈希函数将流ID映射到位图中,并通过统计位图中最低零位的位置来估计流的数量。

    • 优点:计算效率高,适合实时网络测量。

    • 缺点:当草图规模较小时,估计误差可能较大,尤其是在网络流量特征变化时。

机器学习优化方法
1. 特征提取(Feature Extraction)
  • 特征选择:作者提出使用FM Sketch的低比特位置(low-bits)和高比特位置(high-bits)作为特征。

    • 低比特位置(Low-bits):表示位图中最低零位的位置。

    • 高比特位置(High-bits):表示位图中最高一位的位置。

    • 动机:低比特和高比特位置都是流数量的单调递增函数,能够提供关于流数量的有用信息。

2. 模型训练(Model Training)
  • 模型选择:使用线性回归模型进行训练,因为其计算效率高,适合实时应用。

  • 训练过程

    • 生成多个学习FM Sketch,每个Sketch对应一个训练样本。

    • 使用低比特位置和高比特位置作为特征,实际流数量的对数值作为目标值。

    • 通过最小化预测值与实际值之间的交叉熵误差,训练线性回归模型。

    • 模型公式

      • L_{i}H_{i}​ 分别表示第 i 个FM Sketch的低比特和高比特位置。

      • \alpha _{i}\beta _{i}是学习参数。

3. 查询优化(Querying)
  • 查询过程:使用训练好的线性回归模型对常规FM Sketch的低比特和高比特位置进行预测,从而估计流数量。

    • 步骤

      1. 从常规FM Sketch中提取低比特和高比特位置。

      2. 使用线性回归模型计算流数量的对数值。

      3. 将对数值转换为实际流数量。

  • 优势:通过机器学习模型,能够更准确地估计流数量,尤其是在传统FM Sketch误差较大的情况下。

5 Implementation

 系统架构设计(Overall System Design)

作者设计了一个包含交换机和服务器的系统架构,用于实现和评估基于机器学习的草图优化框架。系统的主要组件和功能如下:

  • 交换机(Switch)

    • 负责生成常规草图(如CM、CU和FM草图)。

    • 从网络接口接收流量,并将草图和采样数据发送到服务器。

    • 使用DPDK(Data Plane Development Kit)加速数据包处理,减少内核空间和用户空间之间的数据拷贝。

  • 服务器(Server)

    • 配备两块网卡,一块用于接收网络流量,另一块用于接收查询请求并返回结果。

    • 使用三个线程(Thread)分别处理数据包接收、模型训练和查询响应。

    • 线程1(Thread 1):从硬件环形队列(HW Ring)中接收数据包,分析内容,并将数据包地址指针插入到软件环形队列(SW Ring)中。

    • 线程2(Thread 2):从SW Ring中读取数据包,生成学习草图,并训练机器学习模型。

    • 线程3(Thread 3):从SW Ring中读取常规草图,结合训练好的模型响应查询请求。

机器学习框架的实现(Implementation of Our ML Framework)

作者详细描述了如何在服务器上实现机器学习框架,包括数据包处理、草图生成、模型训练和查询响应的具体实现细节:

  1. 数据包处理(Packet Processing)

    • 使用DPDK技术加速数据包的接收和处理。

    • 数据包被存储在内存池(Memory Pool)中,通过环形队列(Ring)传递数据包的地址指针,避免数据拷贝。

  2. 草图生成(Sketch Generation)

    • 交换机生成常规草图,并将采样数据包的流ID发送到服务器。

    • 服务器根据采样数据生成学习草图,用于训练机器学习模型。

  3. 模型训练(Model Training)

    • 使用线性回归模型对学习草图中的特征进行训练。

    • 模型训练完成后,将训练好的模型传递给查询响应线程(Thread 3)。

  4. 查询响应(Query Response)

    • 线程3结合常规草图和训练好的模型,对查询请求进行响应。

    • 使用机器学习模型优化草图的估计结果,提高查询的准确性。

6 Experimental Results

实验结果表明,机器学习优化后的草图技术在流大小估计、Top-K流估计和流数量估计任务中均表现出显著的性能提升,尤其是在处理小流和误差较大的场景中。此外,该框架在资源开销和扩展性方面也表现出色,证明了其在实际网络测量中的可行性和优越性。


http://www.kler.cn/a/519657.html

相关文章:

  • BLE透传方案,IoT短距无线通信的“中坚力量”
  • Linux进程概念:【环境变量】【程序地址空间】
  • 15_业务系统基类
  • 被占用的电脑文件推沟里
  • vue3 获取百度天气
  • [操作系统] 进程地址空间管理
  • UE4通过反射获取蓝图或子类属性值
  • PAT甲级-1023 Have Fun with Numbers
  • JVM常见知识点
  • IOS 自定义代理协议Delegate
  • 页高速缓存与缓冲区缓存的应用差异
  • YOLOv9改进,YOLOv9检测头融合ASFF(自适应空间特征融合),全网首发
  • 【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】1.1 从零搭建NumPy环境:安装指南与初体验
  • 【Docker】ubuntu中 Docker的使用
  • 面向长文本的多模型协作摘要架构:多LLM文本摘要方法
  • MyBatis框架基础学习(1)
  • 低代码系统-产品架构案例介绍、轻流(九)
  • 亚博microros小车-原生ubuntu支持系列:10-画笔
  • 【架构面试】三、高可用高性能架构设计
  • Gradle自定义任务指南 —— 释放构建脚本的无限可能
  • 解读2025年生物医药创新技术:展览会与论坛的重要性
  • 即梦(Dreamina)技术浅析(一)
  • 自动驾驶中的多传感器时间同步
  • 【自定义函数】编码-查询-匹配
  • python爬虫 爬取站长素材 (图片)(自学6)
  • Pyecharts之词云图、面积图与堆叠面积图