最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

基于IPv4选项包标记的路径重构策略

IT圈 admin 21浏览 0评论

2024年10月2日发(作者:力迎南)

第37卷 第13期 

、,01-37 

计算机工程 

2011年7月 

July 2011 

NO.13 Computer Engineering 

网络与通信・ 文章缩号t l000__-3428(2011)13—0086__o3 文献标识码t A 中啊分类号;TP393 

基于IPv4选项包标记的路径重构策略 

赵涛。,唐学文a,b张眺。 

(重庆大学a.计算机学院;b.信息与网络管理中心,重庆400044) 

摘要:针对IP包头中带标记的ID字段在进行重组时存在的ID值不一致和ID字段容易被篡改等局限性,提出一种基于IPv4选项包标 

记的路径重构策略,用于对攻击路径的重构。同传统的基于ID字段进行标记的策略相比,采用该策略时不仅路由器节点的误报数较小, 

而且重构路径的复杂度有所降低,在路由器进行包处理的时间上具有明显的优势。 

关健诃:包标记;路径重构;IPv4选项;生存时间 

Path Rec0nfigurati0n Strategy 

Based 0n IPv4 Options Packet Marking 

ZHAO Tao ,TANG Xue。wena,b

ZHANG Hai-longa 

(a.College of Computer Science;b.Center of Information and Network,Chongqing University,Chongqing 400044,China) 

[Abstract]Aiming at the limitations on he rteorganization of ID ifelds wih tmark in he ItP packets,such as he tinconsistency in he tID values and 

he ID ftield is illegally altered.A path reconfiguration strategy based on IPv4 options packet marking is proposed and used tO reconfigure the 

attacking paths.Compared wih tthe traditional ID—based marked strategy,the number of mistaken router nodes is less and the complexity is lower 

adopting this strategy.In addition,it possesses obvious advantages in he tpacket processing time of routers. 

[Key words]packet marking;path reconfiguraifon;IPv4 options;Time to Live(TTL) 

DOI:10.3969/j.issn.1000—3428.2011.13.027 

1概述 

随着Internet的发展,网络上的恶意犯罪行为也在快速 

增长,主要包括恶意病毒、恶意木马、黑客入侵、垃圾软件、 

拒绝服务攻击等。其中拒绝服务攻击又占据了恶意行为的相 

当大的比例。针对攻击的入侵,现有的手段主要是检测、防 

御和追踪。对于入侵追踪,文献[1】提出包标记技术,其方法 

就是在数据包经过路由器时,标记路由器对经过的IP数据包 

选项,选项部分主要包括3个部分的功能:提供时间戳,安 

全和处理限制,指定路由的功能”】。 

2.2利用选项进行路由标记的编码方案 

原有Traceroute[41方法的不足之处在于必须把Traceroute 

功能加到路由器中去,并且实现的功能必须依赖于生存时间 

(Time To Live,TTL)的响应,如果网络堵塞,实现起来比较困 

难,本文提出的利用选项进行路由标记的算法,不依赖于 

进行路由器信息标记。当受害者遭受攻击时,利用标记对攻 

击源进行追踪,从而重构攻击路径。 

常用的包标记 技术有基本概率包标记技术、高级概率 

包标记技术、带认证的概率包标记技术、自适应概率包标记 

技术等。以上技术都是针对IP包头中的ID字段,以一定的 

概率进行标记。但对IP包头中的ID字段中进行标记时存在 

ICMP数据包的询问操作。为遵循路由选项的原有格式,本 

文对新类型的路由标记算法采用一种新的格式,如表2所示。 

表2概率包标记在IP包头逸】曩I中定义盼恪式 

其中,拷贝为1表示如果路由器标记这个路由的信息, 

如下弊端:一方面,当发送者传送的包过长时,必须进行分 

片,但是如果在ID标识符字段中进行标记,其结果就是当接 

收者收到发送者传送的IP包时,会发现本来应该重组的IP 

包中的ID值不一致,无法进行IP包的合并。另一方面,攻 

击者有意地进行ID字段的篡改,同样无法重构攻击路径。 

基于上述原因,本文采取一种折中的办法,即在标记IP 

同时当产生分片时,就会把相应的标记信息拷贝到分片中。 

由于选项类别2在可选项中表示的意义为调试测试用,而本 

文的算法仅提供了一种可供参考的算法,在本文中仍然采用 

2表示。选项号占5 bit,由于0、I、2、3、4、7、8、9都已 

经采用,此处采用十进制的10,即二进制的01010。这样选 

项类型就是11001010,即十进制数字202。长度为类别、选 

项号、长度、标记信息的总长度。 

由于受IP包头中ID字段的长度限制,在IP包头中进行 

标记时需要对IP信息进行压缩。当IP包标记标注到ID字段 

中后,在传送过程中容易遭受劫持者的攻击而被修改,使得 

当受害者进行路由重构时,无法正确的重构攻击路径。另外, 

对IP信息进行分片,其中的一片信息变更同样会造成重构攻 

击路径的差错。此外,如果在路由器端进行IP信息计算,计 

作者筒介:赵涛(1985一),男,硕士,主研方向:网络安全,路径 

重构策略;唐学文,高级工程师;张海龙,硕士 

信息时,其标记信息存入IPv4包头的选项部分。 

2基于IPv4选项的编码方案 

2.1 IPv4选项部分简介 

下面介绍一些常见的IP选项部分,如表l所示。 

表1常见路由选项 

选项类别选项号长度 描述 

0 

O 

0 

3 

9 

7 

变量松源路由,根据源端提供的信息路由数据包 

变量严松源路由,根据源端提供的信息路由数据包 

变量记录路由,用来跟踪数据包的路由 

IPv4的选项(options)部分提供了一些对控制功能有用的 

收稿日期:2010—11-23 E-mail:zhlong@cqu.edu.cn 

第37卷第13期 赵涛,唐学文,张海龙:基于IPv4选项包标记的路径重构策略 87 

算量往往比较大。本文采用以空间换取时间的策略。 

3性能分析 

3.1误报数分析 

在进行路径重构时,如果只有一个攻击者,那么从受害 

者端重构攻击路径是非常有效的。但是,如果存在多个攻击 

者,就会存在多条攻击路径。追踪的目的就是找出一条攻击 

路径,由于重构的路径太多,当从受害者端重构路径时,不 

可避免地会出现多种组合,而每一种组合都要进行一次hash 

运算,导致的结果就是运算结果非常大。高强度的hash运算, 

不可避免地会产生误报情况。 

假设在实际的攻击树丁中,有k个节点到受害者的距离 

在标记IP信息时,无需对IP信息进行分片,而是直接 

利用32 bit的IP地址进行计算。此外,为了进行数字签名, 

本文继续采用IP产生的32 bit的哈希值,包在传送过程中的 

格式如表3所示。 

表3选项中进行标记的稿码格式 bit 

其中,长度为1 bit的tag字段表示待标记路由器为域内 

路由器还是边界路由器,这里采用二进制的0表示为域内路 

由器,t表示边界路由器。distance值占4 bit,当tag的值为 

0时distance为本路由器相对于本自治系统内标记的第1个域 

内路由器的相对距离,为1时distance表示此次标记的边界 

路由器是相对于第1个边界路由器的距离。此外长度为32 bit 

的IP address信息表示标记的本路由器的IP地址与上一跳传 

送过来的标记信息相异或的结果的填充信息,tag字段为0 

时标记的是域内路由器的IP信息,为1时标记的是边界路由 

器的IP信息。长度为32 bit的散列值表示本路由器经过hash 

运算产生的32bit的hash值,用于当IP信息出错时进行比较。 

2.3利用可选项标记路由的标记算法 

本文路由器的标记算法描述如下: 

第1步当标记的路由器为第1跳路由器时,对标记的路 

由器做路由器识别,判断本次标记的路由器是否为域内路由 

器,如果是则填充tag字段为1,填充相应的distance字段值 

为1,并在IP address中填充32 bit的本路由器IP地址信息, 

同时利用相应的哈希函数计算出哈希值填充到IPhash value 

中;否则执行第2步。 

第2步路由器抽取32 bit的本路由器IP地址信息IP_ 

value,并对本路由器进行哈希运算,产生32 bit的hash_。 

value进行异或操作IP address=IP address 0 IP—value; 

IPhash value=IPhash value0hash

_

value。把产生的IP address 

和IPhash value值分别填充到提取的包标记信息中,然后转到 

下一跳路由器。 

第3步判断本跳是否为受害者,如果是,则停止标记; 

否则返回第2步操作。 

算法对应的标记流程如图1所示。 

圈1 Options进行路由器信息标记的过程 

都是n+1,那么对于相同的距离n和相同的偏移,会得到多 

个不同的分块。设对应偏移从0到7的互不相同的分块的数 

量分表有ko,k 一,k7个,则需要检查nk1种不同的组合。于 

i=O 

是,所有的ki均近似于v(2 ,七)具有相同的概率分布,其中, 

v(2 , )表示从Ⅳ个元素的集合D={1,2,…,Ⅳ)中随机地、等 

概率低、可重复地抽取n个所得到的不同数据的个数。显然 

当k不足够大时,l-Ik 随着k的指数级增长。如果k的规模 

i--0 

超过25时,其运算量就已经超出了实际的运算范围。为了降 

低组合错误,文献[5】采用32 bit的错误检验码。虽然8个随 

机块的组合通过检测的概率为2-32k,已非常低。但是,在上 

面的假设中,FIki种组合中只有k个组合会得到真正的合法 

i--'O 

节点,而其余的l-Iki—k种组合通过检验的数量平均为: 

i=O 

厂7 I1-Ik 

\i-o 

i—k l

、 

×2一

一 

 2-3z兀t 

7 

i--0 

(1) 

式(1)的数就是误报数。表4为一组关于k为特殊值的情 

况下这个误报率的情况。 

表4节点k的值及相应的误报数 

k值 误报数 

17 

1.01 

20 

88.70 

30 2 920.00 

40 33 438.0O 

50 213 658.00 

从表4中可以看出,当采用基本概率包标记算法时,如 

果距离超过20跳,那么将会产生多于88个的误报数。 

肘表示在因特网中与同一个路由器直接连接的上游路由 

器的平均数量。那么高级概率包标记的误报数情况为: 

7 7 

2一 (kM—k)1-Iki 2 ̄"4MI-Iki (2) 

i=O i=O 

虽然本文采用的算法的误报数与高级包标记算法相同, 

但在攻击路径相同、k相同的条件下,本文提出的标记算法 

的误报数会更小,约为k/2+ ,其中, 为每个自治系统内 

的路由器平均个数。 

3.2重构攻击路径的复杂度分析 

定义: 

d:攻击路径上距离受害者的距离。 

ki:距离受害者距离为d的每一个分片的个数,其中,i 

表示8个分片中的某一个。 

(d):距离受害者距离为d的节点个数。 

Comp :基于固定概率包标记算法进行路径重构时, 

受害者重构攻击路径的复杂度。 

Complexopti :本文采用的利用IP包头中的可选项部分 

进行标记的标记方案的重构路径的复杂度。利用ID字段进行 

标记时受害者重构攻击路径复杂度为: 

88 计算机工程 2011年7月5日 

Complexto=I-IZ:( ( xFl ki) 

采用options进行标记时受害者重构攻击路径复杂度为: 

从图2可以看出,用选项进行IP包标记的算法,路由器 

在处理包的时间消耗上明显低于用ID字段进行的包标记算 

法;利用选项部分进行编码处理的速度大约是用ID字段进行 

编码的3倍。 

Complexo 。 =I-IZ: (d) 

3.3实验结果对比 

本文运用VC6.0平台,利用c++封装路由节点类和处理 

4结束语 

本文提出了一种基于IPv4选项的包标记方案,该方案从 

算法上改进了追踪过程的复杂度,减小了追踪过程中数据包 

数据流的方法来模拟发包的过程,对每个路由节点标记为AS 

边界路由或域内路由,针对不同的路由节点采用不同的方法 

处理数据流来模仿路由器标记方案。 

的误报数,同用ID字段进行包标记的算法相比,在路由器对 

包的处理时间上具有明显的优势。 

由于IP选项部分的大小完全可以容纳下一个不用分片 

的IP信息,因此本文继续采用牺牲空间换取时间的策略,以 

便路由器能在短时间内解决包的处理转发,从而减少对网络 

服务质量、时延、吞吐率等的影响。本文对填充ID、options 

参考文献 

[1】Burch H,Cheswick B.Tracing Anonymous Packets to Their 

Approximate Source[C]//Proc.of the 14th Conference on Systems 

Administration.New Orleans,Louisiana,USA:【S.n.】,2000:3 19— 

327. 

2种标记处理信息的时问作对比,由于采用的模拟实验,因 

此不能全面反映整个路由器的处理情况。为了达到更加明显 

的效果,采用的数据是每个路由器都处理100 000个包后的 

时间,2种标记算法路由器的标记时间对比如图2所示。 

[2]高大鹏,於时才,闫文芝.复合包标记IP追踪算法研究[J】 l

计算机工程,2009,35(10):115—117. 

[3】Stevens W R.TCP/IP详解卷一:协议[MI.范建华,译.北京: 

机械工业出版社,2000. 

【4]Pestel J.Internet Control Message Protocol[S].RFC 792,1981—09. 

[5】Green P Progress in Optical Network[J].IEEE Communication 

Magazine,2001,39(1):54—61. 

图2 2种标记算法路由器的标记时问对比 

编辑索书志 

(上接第85页) 

些4环对译码性能影响较大,在10 时出现误码平台。由前 

述可知,新QC—LDPC码编码只需要(w一1+R)N—L= 

(3.3—1+0.5)×1000—50=2750次模2加运算,比RU方法减少 

1一P=1一((w一1+R)n一1)/((w—l+R)n一3+ /2)=1-70%=30% 

参考文献 

【1]Gallager R G Low Density Parity Check Codes[M].Cambridge, 

USA:MIT Press,1963. 

[21 Richardson T J,Urbanke R L.Eficifent Encoding of Low—density 

的计算量,而随机QC—LDPC码大概需要R(1一R)N /2= 

1/2x(1—1/2)xl000 /2=125000次模2加运算才能完成编码 

Parity—check Codes[J].IEEE Trans.on Information Theory,2001, 

47(2):638—656. 

[3】Yang M,Ryan W E,Li Yan.Design of Eficientlfy Encodable 

Moderate-length High—rate I ̄egular LDPC Codes[J].IEEE Trans. 

on Communications,2004,52(4):564-571. 

操作。由此可见,新构造的QC—LDPC码大大降低了编码复 

杂度,提高了编码效率,减小了编码时延。文献[5]中提出的 

方法,编码复杂度与新构造的QC—LDPC码差不多,但由于 

匹配项 的存在,会出现少量的4环,性能受到一定限制, 

在BER为10。时,约有0_3 dB的信噪比损失。文献【4冲给 

出实用化Block—LDPC,合理选择子块 中子矩阵位置,其 

编码复杂度为(w一1+R)N一2L,与新构造的Qc—LDPC码相 

当,但性能稍差。 

[41 Myung S,Yang K,Kim J.Quasi—cyclic LDPC Code for Fast 

Encoding[J].IEEE Trans.on Information Theory,2005,5l(8): 

2894—2900. 

[51 Kim J K,Balakannan S Lee M O.Low Complexity Encoding of 

LDPC Codes for High・-rate and High--speed Communication[C]// 

Proc.of the lst International Conference on Distributed Frame— 

5结束语 

本文构造了一类有近似下三角矩阵的高效Qc—LDPC码, 

work nd aApplications.IS.1.]:IEEE Press,2009:189—193. 

给出了其简单的编码过程,并证明了在码长为Ⅳ、码率为R、 

校验矩阵日的平均列重为W时,其编码复杂度为 

(w一1+R)N—L。仿真结果表明,新构造的Qc—LDPC码具有 

较好的性能。同时,由于其校验矩阵具有特殊的结构,缩减 

【61敬龙江,林竞力,朱维乐.一种高码率低复杂度准循环LDPC 

码设计研究[JJ.电子与信息学报,2008,3O(6):1385—1389. 

[7]周水红,端木春江,黄志亮,等.高性能准循环LDPC码构造方 

法的改进IJI.计算机工程,2010,36(1):277—279. 

了存储资源,有利于在实际通信系统中的应用。 

编辑顾逸斐 

2024年10月2日发(作者:力迎南)

第37卷 第13期 

、,01-37 

计算机工程 

2011年7月 

July 2011 

NO.13 Computer Engineering 

网络与通信・ 文章缩号t l000__-3428(2011)13—0086__o3 文献标识码t A 中啊分类号;TP393 

基于IPv4选项包标记的路径重构策略 

赵涛。,唐学文a,b张眺。 

(重庆大学a.计算机学院;b.信息与网络管理中心,重庆400044) 

摘要:针对IP包头中带标记的ID字段在进行重组时存在的ID值不一致和ID字段容易被篡改等局限性,提出一种基于IPv4选项包标 

记的路径重构策略,用于对攻击路径的重构。同传统的基于ID字段进行标记的策略相比,采用该策略时不仅路由器节点的误报数较小, 

而且重构路径的复杂度有所降低,在路由器进行包处理的时间上具有明显的优势。 

关健诃:包标记;路径重构;IPv4选项;生存时间 

Path Rec0nfigurati0n Strategy 

Based 0n IPv4 Options Packet Marking 

ZHAO Tao ,TANG Xue。wena,b

ZHANG Hai-longa 

(a.College of Computer Science;b.Center of Information and Network,Chongqing University,Chongqing 400044,China) 

[Abstract]Aiming at the limitations on he rteorganization of ID ifelds wih tmark in he ItP packets,such as he tinconsistency in he tID values and 

he ID ftield is illegally altered.A path reconfiguration strategy based on IPv4 options packet marking is proposed and used tO reconfigure the 

attacking paths.Compared wih tthe traditional ID—based marked strategy,the number of mistaken router nodes is less and the complexity is lower 

adopting this strategy.In addition,it possesses obvious advantages in he tpacket processing time of routers. 

[Key words]packet marking;path reconfiguraifon;IPv4 options;Time to Live(TTL) 

DOI:10.3969/j.issn.1000—3428.2011.13.027 

1概述 

随着Internet的发展,网络上的恶意犯罪行为也在快速 

增长,主要包括恶意病毒、恶意木马、黑客入侵、垃圾软件、 

拒绝服务攻击等。其中拒绝服务攻击又占据了恶意行为的相 

当大的比例。针对攻击的入侵,现有的手段主要是检测、防 

御和追踪。对于入侵追踪,文献[1】提出包标记技术,其方法 

就是在数据包经过路由器时,标记路由器对经过的IP数据包 

选项,选项部分主要包括3个部分的功能:提供时间戳,安 

全和处理限制,指定路由的功能”】。 

2.2利用选项进行路由标记的编码方案 

原有Traceroute[41方法的不足之处在于必须把Traceroute 

功能加到路由器中去,并且实现的功能必须依赖于生存时间 

(Time To Live,TTL)的响应,如果网络堵塞,实现起来比较困 

难,本文提出的利用选项进行路由标记的算法,不依赖于 

进行路由器信息标记。当受害者遭受攻击时,利用标记对攻 

击源进行追踪,从而重构攻击路径。 

常用的包标记 技术有基本概率包标记技术、高级概率 

包标记技术、带认证的概率包标记技术、自适应概率包标记 

技术等。以上技术都是针对IP包头中的ID字段,以一定的 

概率进行标记。但对IP包头中的ID字段中进行标记时存在 

ICMP数据包的询问操作。为遵循路由选项的原有格式,本 

文对新类型的路由标记算法采用一种新的格式,如表2所示。 

表2概率包标记在IP包头逸】曩I中定义盼恪式 

其中,拷贝为1表示如果路由器标记这个路由的信息, 

如下弊端:一方面,当发送者传送的包过长时,必须进行分 

片,但是如果在ID标识符字段中进行标记,其结果就是当接 

收者收到发送者传送的IP包时,会发现本来应该重组的IP 

包中的ID值不一致,无法进行IP包的合并。另一方面,攻 

击者有意地进行ID字段的篡改,同样无法重构攻击路径。 

基于上述原因,本文采取一种折中的办法,即在标记IP 

同时当产生分片时,就会把相应的标记信息拷贝到分片中。 

由于选项类别2在可选项中表示的意义为调试测试用,而本 

文的算法仅提供了一种可供参考的算法,在本文中仍然采用 

2表示。选项号占5 bit,由于0、I、2、3、4、7、8、9都已 

经采用,此处采用十进制的10,即二进制的01010。这样选 

项类型就是11001010,即十进制数字202。长度为类别、选 

项号、长度、标记信息的总长度。 

由于受IP包头中ID字段的长度限制,在IP包头中进行 

标记时需要对IP信息进行压缩。当IP包标记标注到ID字段 

中后,在传送过程中容易遭受劫持者的攻击而被修改,使得 

当受害者进行路由重构时,无法正确的重构攻击路径。另外, 

对IP信息进行分片,其中的一片信息变更同样会造成重构攻 

击路径的差错。此外,如果在路由器端进行IP信息计算,计 

作者筒介:赵涛(1985一),男,硕士,主研方向:网络安全,路径 

重构策略;唐学文,高级工程师;张海龙,硕士 

信息时,其标记信息存入IPv4包头的选项部分。 

2基于IPv4选项的编码方案 

2.1 IPv4选项部分简介 

下面介绍一些常见的IP选项部分,如表l所示。 

表1常见路由选项 

选项类别选项号长度 描述 

0 

O 

0 

3 

9 

7 

变量松源路由,根据源端提供的信息路由数据包 

变量严松源路由,根据源端提供的信息路由数据包 

变量记录路由,用来跟踪数据包的路由 

IPv4的选项(options)部分提供了一些对控制功能有用的 

收稿日期:2010—11-23 E-mail:zhlong@cqu.edu.cn 

第37卷第13期 赵涛,唐学文,张海龙:基于IPv4选项包标记的路径重构策略 87 

算量往往比较大。本文采用以空间换取时间的策略。 

3性能分析 

3.1误报数分析 

在进行路径重构时,如果只有一个攻击者,那么从受害 

者端重构攻击路径是非常有效的。但是,如果存在多个攻击 

者,就会存在多条攻击路径。追踪的目的就是找出一条攻击 

路径,由于重构的路径太多,当从受害者端重构路径时,不 

可避免地会出现多种组合,而每一种组合都要进行一次hash 

运算,导致的结果就是运算结果非常大。高强度的hash运算, 

不可避免地会产生误报情况。 

假设在实际的攻击树丁中,有k个节点到受害者的距离 

在标记IP信息时,无需对IP信息进行分片,而是直接 

利用32 bit的IP地址进行计算。此外,为了进行数字签名, 

本文继续采用IP产生的32 bit的哈希值,包在传送过程中的 

格式如表3所示。 

表3选项中进行标记的稿码格式 bit 

其中,长度为1 bit的tag字段表示待标记路由器为域内 

路由器还是边界路由器,这里采用二进制的0表示为域内路 

由器,t表示边界路由器。distance值占4 bit,当tag的值为 

0时distance为本路由器相对于本自治系统内标记的第1个域 

内路由器的相对距离,为1时distance表示此次标记的边界 

路由器是相对于第1个边界路由器的距离。此外长度为32 bit 

的IP address信息表示标记的本路由器的IP地址与上一跳传 

送过来的标记信息相异或的结果的填充信息,tag字段为0 

时标记的是域内路由器的IP信息,为1时标记的是边界路由 

器的IP信息。长度为32 bit的散列值表示本路由器经过hash 

运算产生的32bit的hash值,用于当IP信息出错时进行比较。 

2.3利用可选项标记路由的标记算法 

本文路由器的标记算法描述如下: 

第1步当标记的路由器为第1跳路由器时,对标记的路 

由器做路由器识别,判断本次标记的路由器是否为域内路由 

器,如果是则填充tag字段为1,填充相应的distance字段值 

为1,并在IP address中填充32 bit的本路由器IP地址信息, 

同时利用相应的哈希函数计算出哈希值填充到IPhash value 

中;否则执行第2步。 

第2步路由器抽取32 bit的本路由器IP地址信息IP_ 

value,并对本路由器进行哈希运算,产生32 bit的hash_。 

value进行异或操作IP address=IP address 0 IP—value; 

IPhash value=IPhash value0hash

_

value。把产生的IP address 

和IPhash value值分别填充到提取的包标记信息中,然后转到 

下一跳路由器。 

第3步判断本跳是否为受害者,如果是,则停止标记; 

否则返回第2步操作。 

算法对应的标记流程如图1所示。 

圈1 Options进行路由器信息标记的过程 

都是n+1,那么对于相同的距离n和相同的偏移,会得到多 

个不同的分块。设对应偏移从0到7的互不相同的分块的数 

量分表有ko,k 一,k7个,则需要检查nk1种不同的组合。于 

i=O 

是,所有的ki均近似于v(2 ,七)具有相同的概率分布,其中, 

v(2 , )表示从Ⅳ个元素的集合D={1,2,…,Ⅳ)中随机地、等 

概率低、可重复地抽取n个所得到的不同数据的个数。显然 

当k不足够大时,l-Ik 随着k的指数级增长。如果k的规模 

i--0 

超过25时,其运算量就已经超出了实际的运算范围。为了降 

低组合错误,文献[5】采用32 bit的错误检验码。虽然8个随 

机块的组合通过检测的概率为2-32k,已非常低。但是,在上 

面的假设中,FIki种组合中只有k个组合会得到真正的合法 

i--'O 

节点,而其余的l-Iki—k种组合通过检验的数量平均为: 

i=O 

厂7 I1-Ik 

\i-o 

i—k l

、 

×2一

一 

 2-3z兀t 

7 

i--0 

(1) 

式(1)的数就是误报数。表4为一组关于k为特殊值的情 

况下这个误报率的情况。 

表4节点k的值及相应的误报数 

k值 误报数 

17 

1.01 

20 

88.70 

30 2 920.00 

40 33 438.0O 

50 213 658.00 

从表4中可以看出,当采用基本概率包标记算法时,如 

果距离超过20跳,那么将会产生多于88个的误报数。 

肘表示在因特网中与同一个路由器直接连接的上游路由 

器的平均数量。那么高级概率包标记的误报数情况为: 

7 7 

2一 (kM—k)1-Iki 2 ̄"4MI-Iki (2) 

i=O i=O 

虽然本文采用的算法的误报数与高级包标记算法相同, 

但在攻击路径相同、k相同的条件下,本文提出的标记算法 

的误报数会更小,约为k/2+ ,其中, 为每个自治系统内 

的路由器平均个数。 

3.2重构攻击路径的复杂度分析 

定义: 

d:攻击路径上距离受害者的距离。 

ki:距离受害者距离为d的每一个分片的个数,其中,i 

表示8个分片中的某一个。 

(d):距离受害者距离为d的节点个数。 

Comp :基于固定概率包标记算法进行路径重构时, 

受害者重构攻击路径的复杂度。 

Complexopti :本文采用的利用IP包头中的可选项部分 

进行标记的标记方案的重构路径的复杂度。利用ID字段进行 

标记时受害者重构攻击路径复杂度为: 

88 计算机工程 2011年7月5日 

Complexto=I-IZ:( ( xFl ki) 

采用options进行标记时受害者重构攻击路径复杂度为: 

从图2可以看出,用选项进行IP包标记的算法,路由器 

在处理包的时间消耗上明显低于用ID字段进行的包标记算 

法;利用选项部分进行编码处理的速度大约是用ID字段进行 

编码的3倍。 

Complexo 。 =I-IZ: (d) 

3.3实验结果对比 

本文运用VC6.0平台,利用c++封装路由节点类和处理 

4结束语 

本文提出了一种基于IPv4选项的包标记方案,该方案从 

算法上改进了追踪过程的复杂度,减小了追踪过程中数据包 

数据流的方法来模拟发包的过程,对每个路由节点标记为AS 

边界路由或域内路由,针对不同的路由节点采用不同的方法 

处理数据流来模仿路由器标记方案。 

的误报数,同用ID字段进行包标记的算法相比,在路由器对 

包的处理时间上具有明显的优势。 

由于IP选项部分的大小完全可以容纳下一个不用分片 

的IP信息,因此本文继续采用牺牲空间换取时间的策略,以 

便路由器能在短时间内解决包的处理转发,从而减少对网络 

服务质量、时延、吞吐率等的影响。本文对填充ID、options 

参考文献 

[1】Burch H,Cheswick B.Tracing Anonymous Packets to Their 

Approximate Source[C]//Proc.of the 14th Conference on Systems 

Administration.New Orleans,Louisiana,USA:【S.n.】,2000:3 19— 

327. 

2种标记处理信息的时问作对比,由于采用的模拟实验,因 

此不能全面反映整个路由器的处理情况。为了达到更加明显 

的效果,采用的数据是每个路由器都处理100 000个包后的 

时间,2种标记算法路由器的标记时间对比如图2所示。 

[2]高大鹏,於时才,闫文芝.复合包标记IP追踪算法研究[J】 l

计算机工程,2009,35(10):115—117. 

[3】Stevens W R.TCP/IP详解卷一:协议[MI.范建华,译.北京: 

机械工业出版社,2000. 

【4]Pestel J.Internet Control Message Protocol[S].RFC 792,1981—09. 

[5】Green P Progress in Optical Network[J].IEEE Communication 

Magazine,2001,39(1):54—61. 

图2 2种标记算法路由器的标记时问对比 

编辑索书志 

(上接第85页) 

些4环对译码性能影响较大,在10 时出现误码平台。由前 

述可知,新QC—LDPC码编码只需要(w一1+R)N—L= 

(3.3—1+0.5)×1000—50=2750次模2加运算,比RU方法减少 

1一P=1一((w一1+R)n一1)/((w—l+R)n一3+ /2)=1-70%=30% 

参考文献 

【1]Gallager R G Low Density Parity Check Codes[M].Cambridge, 

USA:MIT Press,1963. 

[21 Richardson T J,Urbanke R L.Eficifent Encoding of Low—density 

的计算量,而随机QC—LDPC码大概需要R(1一R)N /2= 

1/2x(1—1/2)xl000 /2=125000次模2加运算才能完成编码 

Parity—check Codes[J].IEEE Trans.on Information Theory,2001, 

47(2):638—656. 

[3】Yang M,Ryan W E,Li Yan.Design of Eficientlfy Encodable 

Moderate-length High—rate I ̄egular LDPC Codes[J].IEEE Trans. 

on Communications,2004,52(4):564-571. 

操作。由此可见,新构造的QC—LDPC码大大降低了编码复 

杂度,提高了编码效率,减小了编码时延。文献[5]中提出的 

方法,编码复杂度与新构造的QC—LDPC码差不多,但由于 

匹配项 的存在,会出现少量的4环,性能受到一定限制, 

在BER为10。时,约有0_3 dB的信噪比损失。文献【4冲给 

出实用化Block—LDPC,合理选择子块 中子矩阵位置,其 

编码复杂度为(w一1+R)N一2L,与新构造的Qc—LDPC码相 

当,但性能稍差。 

[41 Myung S,Yang K,Kim J.Quasi—cyclic LDPC Code for Fast 

Encoding[J].IEEE Trans.on Information Theory,2005,5l(8): 

2894—2900. 

[51 Kim J K,Balakannan S Lee M O.Low Complexity Encoding of 

LDPC Codes for High・-rate and High--speed Communication[C]// 

Proc.of the lst International Conference on Distributed Frame— 

5结束语 

本文构造了一类有近似下三角矩阵的高效Qc—LDPC码, 

work nd aApplications.IS.1.]:IEEE Press,2009:189—193. 

给出了其简单的编码过程,并证明了在码长为Ⅳ、码率为R、 

校验矩阵日的平均列重为W时,其编码复杂度为 

(w一1+R)N—L。仿真结果表明,新构造的Qc—LDPC码具有 

较好的性能。同时,由于其校验矩阵具有特殊的结构,缩减 

【61敬龙江,林竞力,朱维乐.一种高码率低复杂度准循环LDPC 

码设计研究[JJ.电子与信息学报,2008,3O(6):1385—1389. 

[7]周水红,端木春江,黄志亮,等.高性能准循环LDPC码构造方 

法的改进IJI.计算机工程,2010,36(1):277—279. 

了存储资源,有利于在实际通信系统中的应用。 

编辑顾逸斐 

发布评论

评论列表 (0)

  1. 暂无评论