一种资源节约的快速一维网络流量聚合方法摘要.PDFVIP

种资源节约的快速 维网络流量聚合方法 * 1,2 1,3 江洁欣 ，程光 （1.东南大学计算机科学与工程学院，南京 210096 ；2.江苏省计算机网络重点实验室，南京 210096 ； 3. 东南大学计算机网络和信息集成教育部重点实验室） 摘要 网络流量是一种具有多维属性的数据，流量聚合的目的是掌握链路上的主要流量模式。一维聚合是 流量聚合的最简单情况，同时也是多维聚合的基础。文章通过分析流量一维聚合的主要时间和空间消 耗，提出了一种基于层次域的流量一维聚合算法，通过采用自 向下的聚合策略避免在层次树中创建非 重聚合点，从而减少算法总体运行时间并大大降低了内存占用。 关键词 网络测量，流量聚合，流信息挖掘 1 研究背景 网络管理员必须随时掌握链路上的流量信息以便及时对网络进行管理，然后针对性的优化、部署和 调度各种资源。在采集到流量数据后，需要对数据进行分析整理，提取有价值的摘要信息报告管理员。 采集到的原始流量是不可用的，因为流量信息的详细程度和管理员的理解能力是一对矛盾；详细的 报文级信息虽然能无损的反映网络状况，但对管理员来说是完全不可用的。从实用角度出发，流量报告 需要提供尽可能详细、可用的信息，使管理员只通过少量的摘要信息就能够掌握全局 况。另一方面， 由于高速链路流量巨大，采集到的原始流量需要按照一些标准进行聚合，提取其中的 “主要”流量模 式，它们的流量超过总流量一定百分比的流量。 流量聚合用于解决这个问题。网络流量具有多维属性，为了全面了解流量构成和主要流量模式，需 要对原始流量进行一维和多维的聚合，将聚合后超过总流量百分比的流量模式提取出来作为对流量构成 的总体概括。一维聚合是指在一个维度上对流量进行聚合，是流量聚合的最简单情况，也是多维流量聚 合算法的基础。 2 相关工作 C.Estan 在[1]中提出一种基于层次域的一维聚合算法，将五元组流定义的五个维度上的取值空间形成 层次域，把流量按照层次之间的包含关系进行聚合，离线计算重聚合点。Wang 在[2] 中对Estan 的方法进 行改进，认为算法的主要消耗发生在潜在的排序操作上，提出了一种自 向下的聚合方法，以流记录的 反复查找代替排序操作并通过一些优化手段减少算法的总体消耗。Zhang 和P.Truong 分别在[3]和[4] 中提 出了一种实时在线近似算法，通过一个split 阈值控制层次树规模的增长，每个达到的流记录至多引起一 次计数器更新和新节点创建操作，达到减少内存占用并提高算法效率的目的。 3 问题提出 设 为按照时间顺序达到的网络流，其中每一项 由键 与一个整数 构成。 是一组与 相关联的信号量，每个新的网络流 的到达将会引起相应信号量 的更新 金项目：本文获江苏省自然基金项目（BK2008288 ），国家科技支撑项目（2008BAH37B04 ）资助。 作者简介：江洁欣（1984～），硕士研究生，主要研究领域网络测量、网络行为学。程光（1973～），教授，硕士研究生导 师，主要研究领域网络测量、网络行为学、网络管理与网络安全。 定义1 （重聚合点）：一个流记录集合 （重集），其总流量为 。给定实数 ，设 表示流记录集合S 中与 相关的总流量，重聚合点定义为集合 。 寻找重聚合点问题定义为在网络流中找出所有的k 以及和他们相关联的流量。 定义2 （层次域中的重聚合点）设输入的网络流 中的键 从层次域 中取值，层次域 的高度为 。对层次域 中的任意前缀 而言，设 为前缀 的所有子前缀的集合，令 表示前缀 的所有流量。层次重聚合点可以定义为一系列前缀 的集合 在五元组的流规范中，源宿IP 地址可以自然地按照前缀划分形成层次域 ，端口和协议号则按 照习惯简单地构成层次域 和 。流量的一维聚合问题就是将所有流量分别在五元组流的五 个维度上分解到相应的层次域中，然