基于路由器随机标识的路径恢复方法及装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106027395A(43)申请公布日2016.10.12(21)申请号201610282716.4(22)申请日2016.04.29(71)申请人清华大学地址100084北京市海淀区100084-82信箱(72)发明人徐恪吴波沈蒙(74)专利代理机构北京清亦华知识产权代理事务所(普通合伙)11201代理人张大威(51)Int.Cl.H04L12/733(2013.01)H04L12/743(2013.01)H04L12/751(2013.01)H04L12/703(2013.01)权利要求书2页说明书7页附图3页(54)发明名称基于路由器随机标识的路径恢复方法及装置(57)摘要本发明公开了一种基于路由器随机标识的路径恢复方法及装置，其中该方法包括：源端在数据包中加预留域RF1和RF2均为0的PRM头部；数据包转发到路由器i并判断RF1和RF2是否均为0；均为0，路由器i产生随机数r并判断r是否大于Pi，r不大于Pi，路由器i的自身标识赋予RF1，路由器i+1的哈希值赋予RF2；r大于Pi，路由器i转发数据包至路由器i+1；均不为0，判断RF2的哈希值与路由器i的IP地址的哈希值是否相等，不相等时转发数据包至路由器i+1，相等时路由器i自身标识Mi赋予RF2；目的端根据RF1和RF2获得路由器对，通过排序算法恢复数据包实际走过的路径。该方法降低了数据包头部的复杂度，增加网络实际吞吐率；在保证可行性的同时，提高整个网络系统的安全性和可信性。CN106027395ACN106027395A权利要求书1/2页1.一种基于路由器随机标识的路径恢复方法，其特征在于，包括以下步骤：S1，源端在数据包的IP头部和TCP头部之间增加一个PRM头部，所述PRM头部的预留域RF1和RF2均为0；S2，所述数据包转发到路由器i，所述路由器i判断所述数据包中的预留域RF1和RF2是否均为0；如果所述预留域RF1和RF2为0，执行S3，路由器i产生随机数r，并判断r是否大于Pi，其中，Pi为路由器i对收到的数据包进行标识的概率，0≤Pi≤1，i为正整数，0≤r≤1；如果r小于等于Pi，执行S4，将所述路由器i的自身标识Mi赋予RF1，并将下一跳路由器i+1的地址哈希值赋予RF2后进入S5；如果r大于Pi，执行S5，所述路由器i直接转发所述数据包至路由器i+1；如果所述预留域RF1和RF2均不为0，执行S6，判断RF2的哈希值与所述路由器i的IP地址的哈希值是否相等；如果所述RF2的哈希值与所述路由器i的IP地址的哈希值不相等，执行S5，所述路由器i直接转发所述数据包至路由器i+1；如果所述RF2的哈希值与所述路由器i的IP地址的哈希值相等，执行S7，则将所述路由器i的自身标识Mi赋予所述RF2后进入S5；S8，目的端根据所述数据包的预留域RF1和RF2获得路由器对，并通过排序算法恢复所述数据包实际走过的路径。2.如权利要求1所述的路径恢复方法，其特征在于，还包括：所述S8进一步包括：S81，所述目的端获取所述数据包经过每个路由器的密钥Ki，并计算出所述每个路由器的标识Mi；S82，所述目的端根据所述数据包中的预留域RF1和RF2，识别出相应的路由器对<Rm,Rm+1>；S83，所述目的端收到一个数据包，路由器得到一个相邻路由器对，在收到一定数量的数据包之后，目的端根据路由器对中的相对位置关系利用相关排序方法得到数据包的实际路径。3.如权利要求1所述的路径恢复方法，其特征在于，所述路由器i的IP地址的哈希值计算公式为：Hash’＝H(ip_address)。4.如权利要求1所述的路径恢复方法，其特征在于，所述RF2的地址哈希值计算公式为：Hash＝H(next_add)。5.如权利要求1所述的路径恢复方法，其特征在于，所述预留域RF1和RF2包含相邻路由器的标识。6.一种基于路由器随机标识的路径恢复装置，其特征在于，包括：初始化模块，用于源端在数据包的IP头部和TCP头部之间增加一个PRM头部，所述PRM头部的预留域RF1和RF2均为0；第一判断模块，用于所述数据包转发到路由器i，所述路由器i判断所述数据包中的预留域RF1和RF2是否均为0；第二判断模块，用于在所述预留域RF1和RF2为0时，路由器i产生随机数r，并判断r是否大于Pi，其中，Pi为路由器i对收到的数据包进行标识的概率，0≤Pi≤1，i为正整数，0≤r≤2CN106027395A权利要求书2/2页1；第一赋值模块，用于在r小于等于Pi时，将所述路由器i的自身标识Mi赋予RF1，并将下一跳路由器i+1的地址哈希值赋予RF2；第一转发模块，用于在r大于Pi时，所述路由器i直接转发所述数据包至路由器i+1；第三判断模块