利用报文抽样和二次哈希方法实现长流识别

４　福建　电脑　２００７年第４期　利用报文抽样和二次哈希方法实现长流识别　景泉　，刘卫江２＇３，白磊　（１．辽宁石化职业技术学院计算机系辽宁锦州１２１０００　２．大连海事大学计算机科学与技术学院，辽宁大连，１１６０２６　３．东南大学计算机科学与技术学科博士后流动站江苏南京２１００９６　４．渤海大学信息科学与工程学院辽宁锦州１２１００３　１　【摘要】：识别长流对于网络操作和网络管理有着重要的意义。本文给出了利用报文抽样和二次哈希方法识别长流的　算法。使用二次哈希的方法，极大的减少了哈希过程中的冲突。实验结果表明，该算法可以精确地获得长流的标识，并通过估　计的方法得出的长度信息接近其真实值。　【关键词】：长流；报文抽样；哈希；闽值　Ｏ．引言　则发生冲突的概率为：Ｐ：１一Ｐｔ　（Ｎ一１）ｚ２～　Ｎｚ２－ｒ　（１）　如果在某次测量中．流的数目较大或选择的哈希函数的随　都会增加哈希冲突的发生率。通过二次哈希的方法可　分布特征　。即大多数流（短流）仅包含很少数目的报文，而很少　机性不好．部分流（长流）却携带着很大数目的报文。长流被描述为只在　以极大的降低冲突的概率　二次哈希即需要我们引入两个　一对网络流进行测量、统计后发现，流往往呈现很强烈的重尾　流的总数量中占很小一部分却占据了大部分网络通信量的流Ｍ　的哈希函数。当到来报文的流标识通过第一个哈希函数作用后　识别长流对于设计高效的流量工程方案有着重要的意义．而且　得到一个比特的哈希值．我们把这一哈希值作为该报文的哈希　获得这些长流的信息对于网络操作和管理是非常有用的。使用　地址　第二个哈希函数的作用结果就是上面所提到的为了区分　抽样技术识别长流不仅减少了对存储空间的要求．而且降低了　报文中的流标识所需的比特的哈希值　如果某一个哈希函数作　对测量系统的负荷．避免了对链路上的所有报文都要进行处理　用到不同流标识的报文上发生了冲突．则可以通过另一个哈希　　而带来的过大的存储开销和计算开销．并且通过对报文样本所　函数加以区分。这样就大大降低了冲突发生的概率。反映出来的特征进行还原和估计．能够推断出原链路上近似的　由式（１），在理想的情况下，采用二次哈希方法产生冲突的　流量特征　使用哈希技术克服了利用硬件哈希表记录流标识带　概率Ｐ　Ⅳ　２…　（２）　来的存储空间大、计算复杂性大的弊端　１．长流的定义　与式（１）相比．哈希冲突的概率缩小了２・倍。　２．３长流识别算法　ＩＰ网中的流是指在某时间段内通过一个观测点的具有相　由于对网络上的流统计呈现很强烈的重尾分布特性．通过　同流标识的报文集合　。在本文中流是指具有相同的源、宿ＩＰ地　抽样，长流比短流会更容易抽到。如果我们对链路上的报文每Ｒ　址，源、宿端口信息，受到超时约束的ＴＣＰ或ＵＤＰ的报文集合　个抽取一个．我们可以把阈值Ｔ１确定为：Ｔ１一Ｔ，Ｒ。如果某个流包　含的报文数超出了Ｔ１．我们就把它识别为长流。识别算法的过　长流被描述为占据了大部分的网络通信量．而在数量上相　程如下：　对较少的流。对长流的描述仅是一个定性的描述『ｑ．定性的定义　１．对链路上通过的报文以每Ｒ个随机的抽取一个　长流．能够使网络操作员依据他们的标准随意决定哪些流是长　２．将抽到的报文样本通过第一个哈希函数Ｈ１作用得出的　流。长流的定义是：如果某个流中包含的报文数或总字节数超出　哈希值作为存储地址．每个地址指向一链表。链表中每＿＿二结点由　了预先定义好的一个值Ｔ（这个值叫做阈值），我们称这个流为　三部分值构成．分别是记录报文样本经第二个哈希函数Ｈ，作用　长流。　得到的哈希值、存储报文的命中次数、指向下一结点的指针　如　２．长流识别过程　果报文样本经Ｈ．作用找到了存储的首地址，接下来将会被Ｈ，　２．１分层随机抽样　作用　如经Ｈ，作用后的哈希值与该首地址指向链表中某结点的　（不考虑协议）。　分层随机抽样是将被测量总体报文平均分成Ｌ个两两互不　哈希值相等，则将其结点的报文命中次数增１；否则，是由于不　交叉、互不重叠的组群，我们把每一个组群称为一层。分层后，再　同流标识的报文经Ｈ，作用后产生了冲突，则新建一个结点，并　从各层中运用随机抽样技术提取样本　分得的层数由抽样频率　记录下相关的信息。如果某一结点中报文命中次数超出了阈值．　来确定。本文使用分层随机抽样对报文进行抽取．抽样频率是在　就在内存中建立这个流的一个标识项来记录它的信息　随后其　每Ｒ个报文中随机抽取一个．即每一层中的报文数为Ｒ　所属报文被抽到后直接对内存中该流的标识项作用　２－２二次哈希方法及哈希冲突的分析　３．测量结束后，要对流长度进行还原估计。根据简单的线形　在高速、大容量的流测量过程中．通过硬件哈希表保存流标　关系．识别出长流的报文数可以被估计为该流中被抽到报文数　识的方法已经不再适用　哈希技术可有效的降低保存每个哈希　的Ｒ倍。　表项所需的存储空间的大小，使之与流标识的字节数无关．仅与　２．４实例分析　被测链路上流的数目有关。但在哈希的过程中．会产生不同的流　利用在ＣＥＲＮＥＴ华东北网络江苏省网边界上获得Ｔｒａｃｅｓ　标识哈希到同一存储空间．从而产生冲突。下面给出了发生哈希　进行实验　选择对链路上的报文每１Ｏ个抽取１个．使用抽样方　冲突的概率：　法阈值ＴＩ＝Ｔ／１０．Ｔ１被确定为１０００个报文。每个识别出的长流　假设某一存储空间同时支持流的数量为个．哈希函数将流　中的报文数可以被估计为该流中被抽到报文数的１Ｏ倍。表１给　标识压缩为比特。设每个到来报文经哈希函数作用后．都随机　的映射到的存储空间中．则哈希过程中没有发生冲突的概率近　似的表示为：　Ｐ．‘　＝　（２ｒ）　ｌ一（Ⅳ一１）ｚ２一ｒ　‘　’　表ｌ识别出的长流信息和估计的报文数（下转第３页）　基金项目：国家重点基础研究发展规划（９７３）（２００３ＣＢ３１４８ｏ４）；教育部科学技术重点研究项目（１０５０８４）；　江苏省网络与信息安全重点实验室ｆＢＭ２００３２０１）：江苏省博士后科研资助计划项目．　维普资讯 http://www.cqvip.com

２００７年第４期　福建　电脑　３　龟　：：　囊　累・。　：：　图１分组投递率和平均速度的关系　端延时（ｅｎｄ—ｅｎｄ　ｄｅｌａｙ１，最少的平均跳数（ａｖｅｒａｇｅ　ｈｏｐ　ｃｏｕｎｔ）。采　用Ｒａｎｄｏｍ　Ｄｉｒｅｃｔｉｏｎ模型的节点．由于必须要运动到仿真区域　的边界，才能改变方向，因此，数据传送的平均跳数，往往比采用　其他模型的网络高，且更易被分割，所以它在分组投递率，最低　的端一端延时．最少的平均跳数方面。表现最差。ＲａｎｄｏｍＷａｌｋ模　型的表现介于上述两种模型之间。　图２为三种模型的平均跳数随节点移动速度变化的情况。。　４．结语　可以看出随着节点速度的增大。平均跳数基本不变，这是因为节　本文介绍了几种典型的Ａｄ　Ｈｏｃ网络移动模型．并在ＯＰ．　点受限在固定的区域内移动，且ＤＳＲ采用的是路由缓存机制．　ＮＥＴ中用ＤＳＲ协议对这三种模型进行了仿真测试．对仿真数据　使得平均跳数不会随着网络拓扑的变化．而明显地增加。采用　进行了曲线模拟和分析。可以看出，同样的移动Ａｄ　Ｈｏｃ网络路　Ｒａｎｄｏｍ　Ｄｉｒｅｃｆｉｏｎ模型的节点。必须要运动到仿真区域的边界，　由协议采用不同的移动模型。得到的性能分析结果，差异是巨大　才能改变方向或速度．所以在低速情况下（０～５ｎｄｓ），随着仿真时　的。因此．如何选取一个合适的移动Ａｄ　Ｈｏｃ网络移动模型。来对　间的推移，节点的分布比较散，路由经过的跳数是增加的，由于　移动Ａｄ　Ｈｏｃ网络路由协议进行性能评估是一个重要的研究课　节点受限在固定的区域内移动。且发射功率范围较大，所以，当　题。目前在该领域．以下几个方面还有待进一步深人地研究：１。　节点的移动速度逐步增大的时候．节点出现在仿真区域中心位　提高移动模型的精确性，使之能更好地反映和接近现实世界。２，　置的概率增大，导致平均跳数．略有下降。　ＱｏＳ是Ａｄ　Ｈｏｃ网络领域研究的热点问题之一．因此设计一种能　满足ＱｏＳ要求的移动模型．是今后工作的重点。　参考文献：　１．Ｔ．Ｃａｍｐ．Ｊ．Ｂｏｌｅｎｇ，ａｎｄ　Ｖ．Ｄａｖｉｅｓ．Ａ　ｓｕｒｖｅｙ＂ｏｆ　ｍｏｂｉｌｉｔｙ　ｍｏｄｅｌｓ　ｆｏｒ　ａｄ　ｈｏｃ　ｎｅＤａｒｏｒｋ　ｒｅｓ￣ｑＩｃｈ．Ｗｉｒｄｅ　ＣＯｔ￣ｔｌ＂ｌＨｎｉｃａｔｉｏｎｓ＆Ｍｏｂｆｌｅ　Ｃｏｍｐｕｔｉｎｇ　（ＷＣＭＣ】，２（５）：１－２，２ｏｏ２．　２．Ｍ．Ｓａｎｃｈｅｚ　ａｎｄ　Ｐ．Ｍａｎｚｏｌｌｉ．Ａｎｅｊｏｓ：Ａ　ｉａｖａ　ｂａｓｅｄ　ｓｉｍｕｌａｔｏｒ　ｆｏｒ　ａｄ—ｈｏｃ　ｎｅｔｗｏｒｋｓ．Ｆｕｔｕｒｅ　Ｇｅｎｅｒａｔｉｏｎ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ，１７（５）：５７３—５８３，２００１　３．Ｃ．Ｂｅｔ岱ｔｅｔｃｅ　ｒ．Ｈ．Ｈａｒｔｅｍｔｅｉｎ．ａｎｄ　Ｘ．Ｐｅｒｅｚ－－ＣＯＳｒａ　Ｓｔｏｃｈａｓｔｉｃ　ｐｒｏｐｅｒｔｉｓ　ｅｏｆ　ｔｈｅ　ｒａｎｄｏｍ　ｗａｙｐｏｉｎｔ　ｍｏｂｉｌｉｙ　ｍｏｄｅｔｌⅡ】．ＡＣＭ／Ｋｌｕｗｅｒ　ＷｉｒｅｌｅｓｓＮｅｔ－　ｗ＇ｏｒｋｓ：Ｓｐｅｃｉ￣Ｉｓｓｕｅ　ｏｎ　Ｍｏｄｅｈｎｇ　ｎｄ　ＡｎａＪａｙｓ￣ｏｆ　ＭｏｂｉｌｅＮｅｔｗｏｒｓ，２００４，ｋ１０　（５）：５５５—５６７．　４．ＲＯＹＥＲ　Ｅ　Ｍ，ＭＥＬＬＩＡＫ－ＳＭＩＴＨ　Ｐ　Ｍ，ＭＯＳＥＲ　Ｌ．Ａｎ　ａｎａｌｙｓｉｓ　ｏｆ　ｄｌｅ　ｏｐｔｉｍｕｍ　ｎｏｄｅ　ｄｅｎｓｉｙｔ　ｆｏｒ　ａｄ　ｈｏｃ　ｍｏｂｉｌｅ　ｎｅｔｗｏｒｓ［ｋＡＩ．１ｎｔ　Ｃｏｎｆｅｒｃｎｃｅ　ｏｎ　ＣｏｒｎｌＴｌｕｍｃａｔｉｏｌ￣Ｐｒｏｃｅｅｄｉｎｇｓ．ＩＥＥＥ［ａ．２００１．８５７－８６１．　图３端一端延时和平均速度的关系　５．Ｖ．Ｔｏｌｅｔｙ．Ｌｏａｄ　ｒｅｄｕｃｔｉｏｎ　ｉｎ　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｓ　ｕｓｉｋｎｇ　ｍｏｂｉｌｅ　ｓｃⅣｅｒｓ．　Ｍａｓｔｅｒ　ｓ　ｄｌｅｓｉｓ．Ｃｏｌｏｒａｄｏ　Ｓｃｈｏｏ１　ｏｆ　Ｍｉｎｅｓ．１９９９．　随着节点移动速度的增加．网络拓扑变化更加频繁．导致分　组投递率（ｐａｃｋｅｔ　ｄｅｌｉｖｅｒｙ　ｒａｆｔｏ）急剧下降。由于采用Ｒａｎｄｏｍ　６．王文博，张金文编著．ＯＰＮＥＴ　Ｍｏｄｄｅｒ与网络仿真（第１版）【Ｍ】．北　Ｗａｙｐｏｉｎｔ模型的节点穿过仿真区域中心的概率非常高．且节点　京：人民邮电出版社．２００３。１０．　ｏｈｎｓｏｎ　ａｎｄ　Ｄ．Ｍａｌ旺，ＤｙＩ１ａｍｉｃ　ｓｏｕｒｃｅ　ｒｏｕｔｉｎｇ　ｉｎ　ａｄ　ｈｏｃ￣Ｓｒｅｌｅｓｓ　每到达一个新的位置，采用一定的停留时问，这样更容易构成一　７．Ｄ，ｌ种相对稳定的网络．所以它具有最高的分组投递率．最低的端一　ｎｅｔｗｏｒｋｓ．Ｉｎ　Ｔ．Ｉｍｅｌｉｍｋｙ　ａｎｄ　Ｈ．Ｋｏｒｔｈ，ｅｄｉｔｏｒｓ，Ｍｏｂ￣ｅ　Ｃｏｍｐｕｔｉｎｇ，ｐａｇｅｓ　１５３－１８１．Ｋ１ｕｗｅｒ　Ａｃａｄｅｍｉｃ　Ｐｕｂｌｉｓｈｅｒｓ．１９９６．　（上接第４页）　表２给出了Ｔｒａｃｅｓ中真实的长流信息和每个长流中包含的　使用本文提出的识别长流的算法可以准确的识别出长流的ＩＩ）　报文数。　孽口地垃　２ｌｎ卫　惦１１４　２ｌ１Ｊｌ　ｌ２ＵｌＯ　３旺ｌＩＵ‘ＩＯ　地址和端口信息．并且通过估计得出的报文数与实际长流中包　宿口ｊｂ址　２１１　ｌ　ｌ９］　舭ｌ１１２４．１０　２１１．７１　ｍ１１０　蠢端口　２９砷　ｌ７０１　Ｉ　１　宿端口　６鹞，　ｌ　ｌ　１７０Ｉ　撮芏置　ｌ叮耵　ＩＳ６　２眦Ｉ　含的报文数是比较接近的。　参考文献：　１．Ｋｏｈｌｅｒ　Ｅ，Ｌｉ　，Ｐｇ￣ｏｎ　Ｖ　ａｎｄ　Ｓｈｅｎｋｅｒ　Ｓ．Ｏｂｓｅｒｖｅｄ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ａｄ－　通过表１和表２的比较。我们可以看出，使用本文提出的识　ｄｒ－＇￣ｓｅｓ　ｉｎ　ｉｐ　ｔｒａ￣ｃ［Ａ】．Ｉｎｔｅｒａｃｔ　Ｍｅａｓｕｒｅｍｅｎｔ　Ｃｏｎｆｅｒｅｎｃｅ【ｑ．Ｎｅｗ　Ｙｏｒｋ，　ＮＹ，ＵＳＡ，２００２．２５３－２６６．　别长流的算法能够准确的识别出长流信息。但是，估计的报文数　与真实长流中包含的报文数存在一些差异：主要是由于报文抽　２．Ｔ．Ｍｏｒｉ。Ｒ．Ｋａｗａｈａｒａ。Ｓ．Ｎａｉｔｏ　ａｎｄ　Ｓ．Ｇｏｔｏ．Ｏｎ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｎｔｅｍｅｔ∞伍ｃ　ｖａｒｉａｂｉｌｉｙ：ｓｔｐｉｋｅｓ　ａｎｄ　ｄｅｐｈａｍｓ［Ａ】．Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ！ＦＦＦ／　样具有随机性，不能够按报文的真实分布进行抽取；另外，通过　ｉＰＳＪ　ＳｔｕＮＴ［Ｃ］．Ｔｏｋｙｏ，Ｊａｐａｎ。２００４．９９—１０６．　估计的方法也会给结果带来一定的误差：第三，虽然本文使用二　Ｉ次哈希降低了哈希过程中的冲突．但是不能避免冲突的发生。　３．结论　３．Ｗ．Ｆａｎｇ．ａｎｄ　Ｌ．Ｐｅｔｅｒｓｏｎ．Ｉｎｔｅｒ—ＡＳ　ｔｒａ￣ｃ　ｐａｔｔｅｒｎｓ　ａｎｄ　ｔｈｅｉｒ　ｉｍｐ￣ｃａｆｉｏｍ　［Ａ】．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＥＥＥ　ＧＬＯＢＥＣＯＭ［Ｃ】．Ｒｉｏ，Ｂｒａｚｉｌ，Ｄｅｃｅｍｂｅｒ　１９９９．　１８５９－１８６８．　４．Ｆｅｌｄｍａｎｎ　Ａ。Ｇｒｅｅｎｂｅｒｇ　Ａ，Ｌｕｎｄ　Ｃ　ａｎｄ　Ｒ．ｅｉｎｇｏｌｄ　Ｎ．Ｄｅｒｉｖｉｎｇ∞伍ｃ　本文使用分层随机抽样和二次哈希方法实现长流的识别　使用哈希技术可以把流标识映射到很短的哈希串所代表的空　ｄｅｍａｎｄｓ　ｆｏｒ　ｏｐｅｍｔｉｏｎ￣ｉＰ　ｎｅｔｗｏｒｓ：ｍｅｔｋｈｏｄｏｌｏｇｙ　ａｎｄ　ｅｘｐｅｒｉｅｎｃｅ［Ａ］．Ｐｒｏ－　间。使之与流标识的字节数无关，仅与被测链路上流的数目有　ｃｅｅｄｉｎｇｓ　ｏｆ　ＡＣＭ　ＳＩＧＣＯＭＭ【ｃＪ．２０００．２６５—２７９．　关．极大的减少了由于维护流标识而带来的资源开销，但哈希的　５．Ｒｅｑｕｉｒｅｍｅｎｔｓ　ｆｏｒ　ｉｐ　ｆｌｏｗ　ｉｎｆｏｒｍａｔｉｏｎｅｘｐｏｒ￣ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／　．过程不可避免带来哈希冲突　二次哈希方法很好的解决了哈希　ｒｆｃ／ｒｆｃ３９１７．ｔｘｔ　ｌ　Ｔ。Ｕｃｈｉｄａ　Ｍ，Ｋａｗａｈａｒａ　Ｒ．Ｉｄｅｎｔｉｆｙｉｎｇ　ｅｌｅｐｈａｎｔ　ｌｆｏｗｓ　ｔｈｒｏｕｇｈ　ｐｅ－　冲突问题。它通过选择两个的哈希函数，当某一个哈希函数　６．Ｍｏｉｉｏｄｉｃａｎｙ　ｓａｍｐｌｅｄ　ｐａｃｋｅｍ［Ａ］．ｔＭＣ［Ｃ］，Ｉｔａｌｉｙ，２００４．１　１５—１２０．　作用到不同流标识的报文上发生了冲突．则可以通过另一个哈　ｒ希函数加以区分．这样就大大降低了冲突的发生率。实验表明：