ZeroNet Blogs

Static ZeroNet blogs mirror

Maple's Blog

推荐一个SS站点

- Posted in Maple's Blog by with comments

差不多一年没有用zeronet,主要因为最近翻翻facebook 才想起. 感觉很多朋友在这里的原因是因为想翻墙. 所以推荐 我在用的一个SS站点

https://www.tkzy.ml/

为了避免广告。。。 就不发我的邀请链接了。。。

对称加密算法(Symmetric-key algorithm)和非对称加密算法(asymmetric key encryption algorithm)只不过就是密码学(encryption)中的两种解密算法罢了,什么是算法,你就可以理解成为是一种规则吧,这种规则可以将信息从一种形式转变成另一种形式,不懂没关系,继续往下看。

对称加密

首先,让我们先从一个情景开始讲起,想当初我们在初中,高中,甚至于大学,每次考试都有人在试图如何更加隐蔽的作弊!那大家都想了什么方法呢?比如张三学习比李四好,李四就想在考试的时候让张三“帮助”一下自己,当然,他们俩不可能像我们平常对话一样说,第一题选A,第二题选B等等,为什么?因为监考老师明白他俩在谈论什么,也就是说这种沟通交流方式属于“明文”,所以李四就想:“我需要发明一种,只有我和张三明白的交流方式”,那李四做了什么呢?恩,李四去找张三说:“当我连续咳嗽三声的时候你看我,然后如果我摸了下左耳朵,说明你可以开始给我传答案了,如果没反应,那说明我真的是在咳嗽。。。。”, 然后,怎么传答案呢?很简单,“你摸左耳朵代表A, 摸右耳朵代表B,左手放下代表C,右手放下代表D”,好了,这就是他们的“算法(规则)”,将信息的一种形式(A,B,C,D),这里我们称为“明文”,转换成了另一种形式(摸左耳朵,摸右耳朵,放左手,放右手),这里称为“密文”,经过这种转换,很显然监考老师不会明白这些“密文”,这样,张三和李四就通过“密文”的形式实现了信息的交换。

其实,密码学不就是为了人们更好的加密传输么?有很多学者,科学家成年累月的工作,为的就是改进或者发明更好的加密算法,让这些加密算法加密的文本难以破解,达到数据安全传输的目的。

OK,回归正题,上面这个“作弊”的例子,其实就是一种对称加密算法!好了,我们来看一下对称加密算法的定义(来源:wikipedia):

对称密钥加密(英语:Symmetric-key algorithm)又称为对称加密、私钥加密、共享密钥加密,是密码学中的一类加密算法。这类算法在加密和解密时使用相同的密钥,或是使用两个可以简单地相互推算的密钥。实务上,这组密钥成为在两个或多个成员间的共同秘密,以便维持专属的通讯联系。与公开密钥加密相比,要求双方取得相同的密钥是对称密钥加密的主要缺点之一 这里我想说一点的是,wikipedia的把Symmetric-key algorithm中文翻译是 对称密钥加密,我不想把这个key翻译成密钥,因为key仅仅是一个“钥”,这里翻译成密钥会让大家对后面所说的“公钥”,“密钥”,“私钥”等等的概念弄混,好了,所以我还是比较喜欢称之为“对称加密算法”,而后面说又称“私钥”加密,共享“密钥”,这里,“私钥”就等于“密钥”,没有任何区别,英文是“private key”。

ok,我们将定义结合我们前面的例子对应一下,“这类算法在加密和解密时使用相同的密钥,或是使用两个可以简单地相互推算的密钥”,其实在我们例子中,密钥就是“将(A,B,C,D)转换成(摸左耳朵,摸右耳朵,放左手,放右手)”这么一个规则。“实务上,这组密钥成为在两个或多个成员间的共同秘密,以便维持专属的通讯联系。” 这句话很好理解了吧,密钥是张三和李四间共同的秘密!只有他俩事先知道。

所以,为什么叫对称加密呢,你可以这么理解,一方通过密钥将信息加密后,把密文传给另一方,另一方通过这个相同的密钥将密文解密,转换成可以理解的明文。他们之间的关系如下:

明文 <-> 密钥 <-> 密文 这样看,是不是感觉对称比较好理解了。ok,那么我们现在有哪些现成的对称加密算法可以用么?当然有:

常见的对称加密算法有DES、3DES、AES、Blowfish、IDEA、RC5、RC6。 想深入了解的同学,可以自行查阅资料了。

非对称加密

我们再来说说非对称加密,非对称加密是一种比对称加密更加优秀的加密算法,当然算法有利有弊,对称加密速度快但是安全性相对于非对称加密来说低,为什么呢,你想啊,要想使用对称加密,那么分享信息的各个个体之间都需要分享这个密钥,比如你们1000个人之间都使用同一个密钥进行密文传输,只要其中一个人密钥被盗窃了,那么整体加密的信息将都被破解了。好了,那么我们开始说说非对称加密。

就从上面提到的这个对称加密的缺点开始,怎么做到即时一个人的密钥被盗窃了,最起码保证你给其他人发送密文不被破解。于是,人们就想出了这么个办法,首先,我们停止分享共同的密钥,因为上面的bug就是来源于共享一个密钥,那么怎么办呢?每个人生成一个“私钥-公钥”对,这个私钥需要每个人自行进行保护!公钥可以随便分享,后面详细说,同时,生成的这个“私钥-公钥”对还有个强大的功能就是,使用私钥加密的信息,只能由该私钥对应的公钥才能解密,使用公钥加密的信息,只能由该公钥对应的私钥才能解密!

好了,比如说张三生成了他自己的一个“私钥-公钥”对,叫做“张三私钥-张三公钥”,李四生成了他自己的一个“私钥-公钥”对,叫做“李四私钥-李四公钥”,之前我们说过私钥要每个个体自己进行保存,公钥可以随便分享,目的是为什么呢?是为了加密信息!

比如,李四想给张三发送密文。于是李四开始给张三发QQ

李四: “hi哥们,我想给你发个密文,把你的公钥给我发过来用用。”

张三: “没问题的,这是我的公钥: d#8yHE8eU#hb*!neb,用这个公钥加密你的信息后给我发过来吧”

李四: “这是我想对你说的话: *&#@uehuu(**#eehu&$##bfeu&&” 恩?你是不是有点疑问呢?咳咳,李四这是作死的节奏?为什么公开问公钥?不怕被网警查水表?哈哈,非对称解密算法的威力就在这里!无所谓!随便谁截取!我们上面说了,公钥可以随意分发,所以即使别人截取了,也只是知道该公钥而已,但是要是想解密使用该公钥加密的密文!只有一个人可以办得到!就是张三! 为什么?李四使用张三的公钥加密的信息,只有张三的公钥所对应的私钥,这里就是“张三私钥”,该私钥才可以解密!所以,没有张三私钥的第三方即时截取了这些密文,也破解不了!或者更严格的说在有限时间内比如说几千年内是暴力破解不出的!

懂了吧?所以网警们哭了,本以为想监视他们的对话,可惜一无所获!

我们来看看非对称加密的官方定义:

公开密钥加密(英语:public-key cryptography,又译为公开密钥加密),也称为非对称加密(asymmetric cryptography),一种密码学算法类型,在这种密码学方法中,需要一对密钥(其实这里密钥说法不好,就是“钥”),一个是私人密钥,另一个则是公开密钥。这两个密钥是数学相关,用某用户密钥加密后所得的信息,只能用该用户的解密密钥才能解密。如果知道了其中一个,并不能计算出另外一个。因此如果公开了一对密钥中的一个,并不会危害到另外一个的秘密性质。称公开的密钥为公钥;不公开的密钥为私钥。 hmm。。这个定义有点绕,不过就是说,要想使用非对称加密算法,首先要有一对key,一个被称为private key私钥,一个成为public key公钥,然后可以把你的public key分发给想给你传密文的用户,然后用户使用该public key加密过得密文,只有使用你的private key才能解密,也就是说,只要你自己保存好你的private key,就能确保,别人想给你发的密文不被破解,所以你不用担心别人的密钥被盗,没关系。

正因为,这种加密是单向的,所以被称为非对称加密算法。

这种加密算法应用非常广泛,SSH, HTTPS, TLS,电子证书,电子签名,电子身份证等等。

这篇文章先写到这里,接下来我将像大家挨个介绍这些加密算法的应用,不过我在这里先埋个伏笔,上面我提到的李四和张三发qq,即时使用非对称加密算法,大家有没有发现仍然有哪些隐患呢?

给点提示,比如说,某个网警想知道到底李四要给张三发什么信息?网警想破解李四的密文,那么网警有什么办法可以获得李四要发的信息呢?很显然获得密文直接暴力破解是不可能的!

小提示,网警可以冒充张三!!!!发送给李四“网警的公钥”,而不是“张三的公钥”,那么当李四收到该公钥的时候,就不假思索的使用该公钥加密了他的信息,然后毫不犹豫的将加密的密文发了过去,然后网警得意的笑了。

NAT穿透解决方案介绍

- Posted in Maple's Blog by with comments

最近公司要实现在各种网络环境下面的多屏互动(机顶盒、android phone、iphone及PC端)的需求;由于IP地址资源有限的原因,目前我们使用的各种终端设备都位于局域网后面也就是多台设备共享同一个公网IP;例如:如果位于局域网里面的一个终端Agent A要与互联网上的另一个终端Agent B通信,当A发送的data packet经过局域网出口处的NAT设备时,NAT会将data packet里面的source address字段替换成相应的公网IP和Port,然后再发送data packet到Agent B。Agent B看到的source address就是经过转换后的IP和Port并不知道Agent A的局域网地址;当Agent B的响应到达Agent A的NAT设备后,NAT设备查找内存中保存的和这个外网地址相对应的内网地址,如果找到后就将这个data packet转发到这个地址,这样就实现了通信。

然而由于目前存在着各种不同类型的NAT设备对NAT有着不同的实现方式(将内外地址映射成外网地址的时候有着不同的行为方式),这就给NAT的穿透带来了麻烦;目前主要的NAT类型有如下几种:

1)Full-cone NAT, also known as one-to-one NAT

一旦一个内网地址 (iAddr:iPort) 被映射到一个外部地址 (eAddr:ePort), 来自 iAddr:iPort 的任何数据包将通过 eAddr:ePort 发送. 任何外部主机能够通过eAddr:ePort这个地址发送数据包到iAddr:iPort. 2)Address-restricted-cone NAT

一旦一个内网地址 (iAddr:iPort) 被映射到一个外部地址 (eAddr:ePort), 来自 iAddr:iPort 的任何数据包将通过 eAddr:ePort 发送. 仅只有接收到主机(iAddr:iPort)通过eAddr:ePort发送的数据包的外部主机通过该主机的任何端口发送到eAddr:ePort的数据包才能够被正确的转发到iAddr:iPort.也就是说主机有关端口无关. 3)Port-restricted cone NAT

类似于address restricted cone NAT, 但是端口号有限制.

一旦一个内网地址 (iAddr:iPort) 被映射到一个外部地址 (eAddr:ePort), 来自 iAddr:iPort 的任何数据包将通过 eAddr:ePort 发送. 仅只有接收到主机(iAddr:iPort)通过eAddr:ePort发送的数据包的外部主机通过该主机的相同端口发送到eAddr:ePort的数据包才能够被正确的转发到iAddr:iPort. 4)Symmetric NAT

来自相同内部ip和port发送到相同目的地ip和port的请求被映射到唯一的外部ip和port地址;如果相同的内部主机采用相同的ip和port地址发送到不同的目的地,那么重新分配映射地址。 只有先前收到内部主机发送的包的外部主机才能够发送返回包到内部主机。 针对前面三种NAT类型(即cone NAT)只要通信双方彼此知道对方的内部地址和外部地址的映射关系,然后通过UDP打洞的方式就可以建立相互连接的通信;但是第四种也就是Symmetric NAT的话由于每次向不同目的地发送数据包时采用不同的外部地址,也就没办法通过直接的方式建立P2P连接。

1.各种网络环境下的P2P通信解决方法:

(1)如果通信双方在同一个局域网内,这种情况下可以不借助任何外力直接通过内网地址通信即可;

(2)如果通信双方都在有独立的公网地址,这种情况下当然可以不借助任何外力直接通信即可; (3)如果通信双方一方拥有独立的公网地址另一方在NAT后面,那么可以由位于NAT后面的一方主动发起通信请求;

(4)如果通信双方都位于NAT后面,且双方的NAT类型都是cone NAT,那么可以通过一个STUN服务器发现自己的NAT类型以及内网和外网传输地址映射信息,然后通过Signaling(信令服务器,实现了SIP协议的主机)交换彼此的NAT类型及内网和外网传输地址映射信息,然后通过UDP打洞的方式建立通信连接;

(5)如果通信双方有一方的NAT类型是Symmetric NAT,则无法直接建立P2P连接,这个时候就需要借助TURN(Traversal Using Relay NAT)即转发服务器来实现间接通信;

2.协议及用到的相关技术介绍:

SDP(Session Description Protocol) 当初始化多媒体电视会议、IP电话、视频流等会话的时候,参与者之间会要求传送媒介的详细、传输地址和其他会话描述元数据等信息;SDP为这些信息提供一种和传输方式无关的标准的表现形式。也就是说SDP仅仅只是一种描述会话信息的格式。它主要被各种不同的传输协议作为一种信息交换的格式使用列如:HTTP、RTSP、SIP、Email等各种协议。 如ICE里面的SDP内容为:

 v=0
o=ice4j.org 0 0 IN IP4 192.168.106.215
s=-
t=0 0
a=ice-options:trickle
a=ice-ufrag:bc01a
a=ice-pwd:1boove7ehnpo1lqho7unefni36
m=audio 3030 RTP/AVP 0
c=IN 192.168.106.215 IP4
a=mid:audio
a=candidate:1 1 udp 2130706431 192.168.106.215 3030 typ host
a=candidate:2 1 udp 1694498815 121.15.130.xxx 64923 typ srflx raddr 192.168.106.215 rport 3030

STUN(Session Traversal Utilities for NAT)

NAT会话穿透工具;STUN提供了一种方式使一个端点能够确定NAT分配的和本地私有IP地址和端口相对应的公网IP地址和端口以及NAT的类型信息。它也为端点提供了一种方式保持一个NAT绑定不过期。NAT绑定过期则表示为相同的内网地址重新分配外网地址也就是端口号。

TURN(Traversal Using Relay NAT)

TURN是STUN协议的扩展,在实际应用中他也可以充当STUN的角色;如果一个位于NAT后面的设备想要和另外一个位于NAT后面的设备建立通信,当采用UDP打洞技术不能改实现的时候就必须要一台中间服务器扮演数据包转发的角色,这台TURN服务器需要拥有公网的IP地址;

SIP(Session Initiation Protocol) 是一种Signaling(信令)通信协议;有许多互联网应用需要创建有多个参与者的会话和管理参与者之间相互的数据交换,然而如果这些工作让应用的参与者来实现是比较复杂的如:用户也许在端点之间移动、通过多个名称寻址和也许同时使用几种不同的媒介通信。有许多协议能够实现各种形式的多媒体会话进行数据传送例如声音、视频或者文本消息。SIP能够和这些协议一同合作,使一个客服端能够发现参与这个会话的其他客服端并共享同一会话。为了定位后面加入会话的参与者等功能,SIP能够为代理服务器创建基础设施,客服端可以通过这个代理服务器实现会话注册、邀请参与会话等功能。SIP是一个创建、修改和终止会话的灵活的多种用途的工具,不依赖于底层的传输协议并且不依赖于被创建的会话类型。 ICE(Interactive Connectivity Establishment)

是实现NAT穿透的一种技术方案;ICE是一种NAT穿透技术,通过offer/answer模型建立基于UDP的媒介流。ICE是offer/answer模型的扩展,通过在offer和answer的SDP里面包含多种IP地址和端口,然后对本地SDP和远程SDP里面的IP地址进行配对,然后通过P2P连通性检查进行连通性测试工作,如果测试通过即表明该传输地址对可以建立连接。其中IP地址和端口(也就是地址)有以下几种:本机地址、通过STUN服务器反射后获取的server-reflexive地址(内网地址被NAT映射后的地址)、relayed地址(和TURN转发服务器相对应的地址)及Peer reflexive地址等。

3.ICE进行NAT穿透的基本过程:

在通常的ICE部署环境中,我们有两个客服端想要建立通信连接,他们可以直接通过signaling服务器(如SIP服务器)执行offer/answer过程来交换SDP消息。 在ICE过程开始的时候,客服端忽略他们各自的网络拓扑结构,不管是不是在NAT设备后面或者多个NAT后面,ICE允许客服端发现他们的所在网络的拓扑结构的信息,然后找出一个或者更多的可以建立通信连接的路径。 下图显示了一个典型的ICE部署环境,客服端L和R都在各自的NAT设备后面,下面简单描述下ICE建立通信的过程: (1)L和R先分别通过STUN和TURN服务器获取自己的host address,server-reflexive address、relayed address(和TURN转发服务器相对应的地址),其中server-reflexive address和relayed address通过定时刷新保证地址不过期。这些地址通常叫做candinate地址。 (2)给这些candinate地址分配优先级排序并格式化成SDP格式,通过SIP服务器交换彼此的SDP; (3)交换完成后根据一定的原则把本地的候选和远程的候选进行配对,每一对都有自己的优先级并根据优先级进行排序后放入Check列表里面(两边都会有相同的Check列表)。 (4)然后进行连接性测试,测试前会选择一个客服端扮演Controlled角色和另一个扮演Controling角色,连通性检查完成后扮演Controling角色的客服端负责在有效的Candinate对列表里面选择一个作为一个被选中的传输通道并通知Controlled的客服端。 (5)利用被选中的candinate地址对进行通信。 4.ICE JAVA实现代码

ICE4J的API文档可以参考 http://bluejimp.com/jitsi/ice4j/javadoc/ 在这个实现里面没有利用SIP服务器进行SDP信息的交换而是采用手动输入的方式,在生产环境中可以部署一台socket.io或者其他SIP服务器 5.参考资料

ICE:https://tools.ietf.org/html/rfc5245 SDP:http://tools.ietf.org/html/rfc4566 SIP:http://tools.ietf.org/html/rfc3261 NAT:http://en.wikipedia.org/wiki/Network_address_translation STUN:http://tools.ietf.org/html/rfc5389 TURN:http://tools.ietf.org/html/rfc5766 ICE4J:http://code.google.com/p/ice4j/

1 引言

随着网络的发展,尤其是大规模多媒体的开发和应用,在传统的 C/S、B/S 的结构中带宽和服务器的处理能力成为了瓶颈。相比之下,P2P 网络具有较高的自主性、可伸缩性、可靠性和对称性。尤其是可伸缩性在 P2P 网络中变成了研究热点。怎样高速和有效的查询资源节点是一个非常重要的问题。P2P路由算法根据网络的组织结构、数据的分布和路由、定位方式主要分为两类:结构化的 P2P 和非结构化的 P2P。

结构化的哈希表(DHT)主要被用在结构化的 P2P网络中。它是由在广域空间内分部的纵多分散的节点组成的一个大的哈希表。这个哈希表被分成众多不连续的部分。每个节点通过加密的哈希函数和统一的域名空间管各自的区域。同时结构化的哈希表(DHT)还具有可伸缩性、可靠性、鲁棒性和自组织的特点。同时每个节点可以动态的加入和退出网络。目前,典 型的结构化的 P2P 路由算法包括 CAN,Chord,Pastry等等。

Kademlia 是一种基于 DHT 的路由算法。和前边提到的其它的路由算法相比,Kademlia 是一种新型的DHT 覆盖拓扑结构,并且在查询速度上有明显的几个优点。它的特别之处在于利用 XOR metric 测量两个节点之间的距离,然而在查询效率和缓存策略上存在着不足。针对这种情况,本文引用了一种新的策略,该策略采用了快表技术和加权设置策略。这样就避免了 在高的刷新频率下缓存查询效率低的问题,为更高的查询命中率提供了更集中的热点资源。文章的组织如下:第二部分介绍了原始的Kademlia 算法和它的数据结构;第三部分是改进的Kademlia 路由算法;第四部分通过实验来证明该算法的有效性;最后一部分为结论。

2 Kademlia 算法描述

Kademlia 协议最早出现在 2002,美国的 PetarP.Maymounkov and David Mazieres 发表了“Kademlia:基于 XOR metric 的点对点的信息系统”的文章引起了人们的重视。随后 2005 年,基于 DHT 的 Kademlia路由算法首次运用在 BiTtorrent 中。之后,该算法在很多 P2P 的网络中得到运用,如 BitComet,BitSpirit和 eMule,它们所采用的获取值、节点和关键字的算法不同。在 Kademlia 算法中,每个节点都有一个长度为160 位的字符串作为唯一标识,这 160 个字符是通过随机函数选取自由组合而成的。同时,每个节点都有一个<关键字,值>的一个值对(但并不是必须的),值存储在最近的节点上。为了使这些值处于活跃状态,需要周期性的发布。

Kademlia 哈希表的组织形式为一个二叉树,叶子为 Kademlia 节点。根据节点 ID 的最短的唯一前缀给每个节点赋值,每个节点根据其 ID 插入树中的某一位置。从树根开始,每一位代表一个二叉树的分支。每个节点都拥有整个二叉树的一部分空间,除了自身之外,其余部分又被划分成一系列连续的子树。最高子树是除了根节点之外的整个二叉树的一半,下一个子树是剩下部分的一半,等等,以此类推。节点 0010 如图 1 所示。 Node subtree Figure 1. Node subtree 图 1. 节点子树 根据子树的结构,XOR 度量被用于计算两个节点之间的距离。举例,节点 x 和 y 之间的距离用表达式 d(x,y) = x⊕y 表示,从该表达式中我们可以看出,高的数字比低的数字有更多的影响。正如我们所知道 的:XOR 度量是单向的,每个 x 都有唯一的 y 和唯一的 d(x,y)和其相对应,搜索相同关键字会沿着同样的路径进行,该路径独立于起点。如果我们在该路径上只存储<关键字,值>对的话,这种方法能减轻热点区的压力,提高查询效率。 在 Kademlia 中,任何节点和它周围的节点都保持 logN(N 为节点数,logN 默认值为 160)个连接。此外,每个节点都有一个特殊的路由表,被称为k-bucket 表,该表和其它节点的三元组(IP 地址,UDP端口,节点 ID)至多包含 K 个入口。同时,在覆盖的节点中,为了使路由更加牢靠,通过跨越几个不相连的路径,参数 K 是一个冗余因子。例如 k-bucket[i],节点之间的信息被存储,节点之间的距离在 2i 和 2i+1之间。图 2 显示了 K=20 时,k-bucket 表的情况。 k-bucket table Figure 2. k-bucket table 图 2. k-bucket 表 总之,在 Kademlia 算法优点如下:节点 ID 之间的关系,在 k-bucket 中节点和节点位置之间的距离都被定义。

然而,高速缓存策略有一些缺点。首先,要成功查询<关键字,值>时,没有必要去存储这个值。第二,产生和搜索资源降低了效率,尤其是热点节点。如果资源是无效了,关于它的信息在每一个相关的节点上将会被清除,因此,热点节点的资源要在缓冲中重新建立。

3 改进的 Kademlia 路由算法

为了改进以上存在的问题,本文提出了一种改进的 Kademlia 算法,该算法主要通过使用快表和加权设置来提高热点区查询的效率。

3.1 高速缓存策略 由于最初的 Kademlia 算法不能区分热点节点和普通节点,新的缓存策略提出,在每个节点中除了现存的 k-bucket 外,在空间允许的基础上,要增加一个新表用于存储存在高访问率的节点信息。在本文中,该表被称为快查询表或快表,快表的每个记录包括资源和供应者即<关键字,值>对。每个节点的查询时间也被记录在表中,因此热区的存储能力和缓冲能力都被提高了。

热区由 counter 的值来定义,例如,我们定义counter>3 的资源为热区,因此,检查每个节点的counter,如果大于 3,则将该节点存储到邻居节点或者有最靠近 key 值的节点。注意,热区对于邻居节点来说意味着要把热区资源存储在表中。拥有最靠近的key 的节点的存储操作的含义是发表该 key 的信息。

3.2 更新快表 更新快表就犹如在 Kedemlia 路由模型中更新k-bucket,当一个新的记录被加入到快表中,步骤如下: (1)如果该资源已经在快表中存在,counter+ =1,然后把指针移向尾部 (2)如果资源不存在,并且记录的数目少于 k,把资源添加到快表的尾部 (3)如果表是空表,则删除表顶部的记录,然后在表的尾部增加一个新记录。

4 仿真实验

本文中,运用 PlanetSim 来运行和评估 Kademlia路由算法。PlanetSim 是一个网络模拟器,用于大规模overlay 服务的实验框架。它提供了一个统一的方法来模拟,并且可以清晰的区分算法的设计以及基于之上的应用和服务。因为节点是随意的插入 PlanetSim 平台上,算法的有效性可以保证。PlanetSim 提供了一系列的评估指标,如路由步长、查询时间延迟、查询成 功次数和失败次数等等。在本文中,该模拟实验主要通过评估路由步长、 查询时间延迟等指标来比较新旧算法关于热区查询的问题。查询数增加,参数不变。首先考虑平均路由步长,单位是一个跳变。图 3显示了平均由步长和查询数量的关系。“Orgn Kad”表示原始的 Kademlia 协议,而“NewKad”表示改进的算法。结果证明,改进的算法没有显著增加系统的负担,但可以通过增加一个合适快表的方法来改善热区搜索。

Average routing steps Figure 3. Average routing steps 图 3. 平均路由步长 同样的环境下,查询时间延时也被检测。查询时间延时被定义为平均时间延时,单位是毫秒。图 4 表明,y 值的变化依赖于 x 轴的值,通过 y 轴可以看出,随着查询数目的增加,查询时间延时会减少。统计学数据证明改进的 Kademlia 算法在减少查询时间延时方面具有显著性。 Query time delay Figure 4. Query time delay 图 4. 查询时间延时

5 结束语

本文重点关注的问题是 P2P 网络中的如何高效的发现节点和检索资源的问题。重点分析了 Kademlia算法和改进的 Kademlia 路由算法。在真正的 P2P 网络中,利用快表查询和加权设置方法可以加快热区的查询速度。实验结果证明,改进的算法具有较低的路由步长和查询时间延时,同时可靠性也得到了提高。

Kademlia详解

- Posted in Maple's Blog by with comments

前两天在网上看到世界知名的电骡服务器Razorback 2被查封、4人被拘禁的消息,深感当前做eMule / BitTorrent等P2P文件交换软件的不易。以分布式哈希表方式(DHT,Distributed Hash Table)来代替集中索引服务器可以说是目前可以预见到的为数不多的P2P软件发展趋势之一,比较典型的方案主要包括:CAN、CHORD、 Tapestry、Pastry、Kademlia和Viceroy等,而Kademlia协议则是其中应用最为广泛、原理和实现最为实用、简洁的一种, 当前主流的P2P软件无一例外地采用了它作为自己的辅助检索协议,如eMule、Bitcomet、Bitspirit和Azureus等。鉴于 Kademlia日益增长的强大影响力,今天特地在blog里写下这篇小文,算是对其相关知识系统的总结。

  1. Kademlia简述 Kademlia(简称Kad)属于一种典型的结构化P2P覆盖网络(Structured P2P Overlay Network),以分布式的应用层全网方式来进行信息的存储和检索是其尝试解决的主要问题。在Kademlia网络中,所有信息均以的哈希表条目形式加 以存储,这些条目被分散地存储在各个节点上,从而以全网方式构成一张巨大的分布式哈希表。我们可以形象地把这张哈希大表看成是一本字典:只要知道了信息索 引的key,我们便可以通过Kademlia协议来查询其所对应的value信息,而不管这个value信息究竟是存储在哪一个节点之上。在eMule、 BitTorrent等P2P文件交换系统中,Kademlia主要充当了文件信息检索协议这一关键角色,但Kad网络的应用并不仅限于文件交换。下文的 描述将主要围绕eMule中Kad网络的设计与实现展开。

  2. eMule的Kad网络中究竟存储了哪些信息? 只要是能够表述成为字典条目形式的信息Kad网络均能存储,一个Kad网络能够同时存储多张分布式哈希表。以eMule为例,在任一时刻,其Kad网络均存储并维护着两张分布式哈希表,一张我们可以将其命名为关键词字典,而另一张则可以称之为文件索引字典。 a. 关键词字典:主要用于根据给出的关键词查询其所对应的文件名称及相关文件信息,其中key的值等于所给出的关键词字符串的 160比特SHA1散列,而其对应的value则为一个列表,在这个列表当中,给出了所有的文件名称当中拥有对应关键词的文件信息,这些信息我们可以简单 地用一个3元组条目表示:(文件名,文件长度,文件的SHA1校验值),举个例子,假定存在着一个文件 “warcraft_frozen_throne.iso”,当我们分别以“warcraft”、“frozen”、“throne”这三个关键词来查询 Kad时,Kad将有可能分别返回三个不同的文件列表,这三个列表的共同之处则在于它们均包含着一个文件名为 “warcraft_frozen_throne.iso”的信息条目,通过该条目,我们可以获得对应iso文件的名称、长度及其160比特的SHA1校 验值。 b. 文件索引字典:用于根据给出的文件信息来查询文件的拥有者(即该文件的下载服务提供者),其中key的值等于所需下载文件的 SHA1校验值(这主要是因为,从统计学角度而言,160比特的SHA1文件校验值可以唯一地确定一份特定数据内容的文件);而对应的value也是一个 列表,它给出了当前所有拥有该文件的节点的网络信息,其中的列表条目我们也可以用一个3元组表示:(拥有者IP,下载侦听端口,拥有者节点ID),根据这 些信息,eMule便知道该到哪里去下载具备同一SHA1校验值的同一份文件了。

  3. 利用Kad网络搜索并下载文件的基本流程是怎样的? 基于我们对eMule的Kad网络中两本字典的理解,利用Kad网络搜索并下载某一特定文件的基本过程便很明白了,仍以 “warcraft_frozen_throne.iso”为例,首先我们可以通过warcraft、frozen、throne等任一关键词查询关键词 字典,得到该iso的SHA1校验值,然后再通过该校验值查询Kad文件索引字典,从而获得所有提供 “warcraft_frozen_throne.iso”下载的网络节点,继而以分段下载方式去这些节点下载整个iso文件。 在上述过程中,Kad网络实际上所起的作用就相当于两本字典,但值得再次指出的是,Kad并不是以集中的索引服务器(如华语P2P源动力、 Razorback 2、DonkeyServer 等,骡友们应该很熟悉吧)方式来实现这两本字典的存储和搜索的,因为这两本字典的所有条目均分布式地存储在参与Kad网络的各节点中,相关文件信息、下载 位置信息的存储和交换均无需集中索引服务器的参与,这不仅提高了查询效率,而且还提高了整个P2P文件交换系统的可靠性,同时具备相当的反拒绝服务攻击能 力;更有意思的是,它能帮助我们有效地抵制FBI的追捕,因为俗话说得好:法不治众…看到这里,相信大家都能理解“分布式信息检索”所带来的好处了吧。但 是,这些条目究竟是怎样存储的呢?我们又该如何通过Kad网络来找到它们?不着急,慢慢来。

  4. 什么叫做节点的ID和节点之间的距离? Kad网络中的每一个节点均拥有一个专属ID,该ID的具体形式与SHA1散列值类似,为一个长达160bit的整数,它是由节点自己随机生成的, 两个节点拥有同一ID的可能性非常之小,因此可以认为这几乎是不可能的。在Kad网络中,两个节点之间距离并不是依靠物理距离、路由器跳数来衡量的,事实 上,Kad网络将任意两个节点之间的距离d定义为其二者ID值的逐比特二进制和数,即,假定两个节点的ID分别为a与b,则有:d=a XOR b。在Kad中,每一个节点都可以根据这一距离概念来判断其他节点距离自己的“远近”,当d值大时,节点间距离较远,而当d值小时,则两个节点相距很近。 这里的“远近”和“距离”都只是一种逻辑上的度量描述而已;在Kad中,距离这一度量是无方向性的,也就是说a到b的距离恒等于b到a的距离,因为a XOR b==b XOR a

  5. 条目是如何存储在Kad网络中的? 从上文中我们可以发现节点ID与条目中key值的相似性:无论是关键词字典的key,还是文件索引字典的key,都是160bit,而节点ID恰恰 也是160bit。这显然是有目的的。事实上,节点的ID值也就决定了哪些条目可以存储在该节点之中,因为我们完全可以把某一个条目简单地存放在节点ID 值恰好等于条目中key值的那个节点处,我们可以将满足(ID==key)这一条件的节点命名为目标节点N。这样的话,一个查找条目的问题便被简单地转化 成为了一个查找ID等于Key值的节点的问题。 由于在实际的Kad网络当中,并不能保证在任一时刻目标节点N均一定存在或者在线,因此Kad网络规定:任一条目,依据其key的具体取值,该条目 将被复制并存放在节点ID距离key值最近(即当前距离目标节点N最近)的k个节点当中;之所以要将重复保存k份,这完全是考虑到整个Kad系统稳定性而 引入的冗余;这个k的取值也有讲究,它是一个带有启发性质的估计值,挑选其取值的准则为:“在当前规模的Kad网络中任意选择至少k个节点,令它们在任意 时刻同时不在线的几率几乎为0”;目前,k的典型取值为20,即,为保证在任何时刻我们均能找到至少一份某条目的拷贝,我们必须事先在Kad网络中将该条 目复制至少20份。 由上述可知,对于某一条目,在Kad网络中ID越靠近key的节点区域,该条目保存的份数就越多,存储得也越集中;事实上,为了实现较短的查询响应 延迟,在条目查询的过程中,任一条目可被cache到任意节点之上;同时为了防止过度cache、保证信息足够新鲜,必须考虑条目在节点上存储的时效性: 越接近目标结点N,该条目保存的时间将越长,反之,其超时时间就越短;保存在目标节点之上的条目最多能够被保留24小时,如果在此期间该条目被其发布源重 新发布的话,其保存时间还可以进一步延长。

  6. Kad网络节点需要维护哪些状态信息? 在Kad网络中,每一个节点均维护了160个list,其中的每个list均被称之为一个k-桶(k-bucket),如下图所示。在第i个 list中,记录了当前节点已知的与自身距离为2^i~2^(i+1)的一些其他对端节点的网络信息(Node ID,IP地址,UDP端口),每一个list(k-桶)中最多存放k个对端节点信息,注意,此处的k与上文所提到的复制系数k含义是一致的;每一个 list中的对端节点信息均按访问时间排序,最早访问的在list头部,而最近新访问的则放在list的尾部。 kad bucket k-桶中节点信息的更新基本遵循Least-recently Seen Eviction原则:当list容量未满(k-桶中节点个数未满k个),且最新访问的对端节点信息不在当前list中时,其信息将直接添入list队 尾,如果其信息已经在当前list中,则其将被移动至队尾;在k-桶容量已满的情况下,添加新节点的情况有点特殊,它将首先检查最早访问的队首节点是否仍 有响应,如果有,则队首节点被移至队尾,新访问节点信息被抛弃,如果没有,这才抛弃队首节点,将最新访问的节点信息插入队尾。可以看出,尽可能重用已有节 点信息、并且按时间排序是k-桶节点更新方式的主要特点。从启发性的角度而言,这种方式具有一定的依据:在线时间长一点的节点更值得我们信任,因为它已经 在线了若干小时,因此,它在下一个小时以内保持在线的可能性将比我们最新访问的节点更大,或者更直观点,我这里再给出一个更加人性化的解释:MP3文件交 换本身是一种触犯版权法律的行为,某一个节点反正已经犯了若干个小时的法了,因此,它将比其他新加入的节点更不在乎再多犯一个小时的罪……-_-b 由上可见,设计采用这种多k-bucket数据结构的初衷主要有二:a. 维护最近-最新见到的节点信息更新;b. 实现快速的节点信息筛选操作,也就是说,只要知道某个需要查找的特定目标节点N的ID,我们便可以从当前节点的k-buckets结构中迅速地查出距离N 最近的若干已知节点。

  7. 在Kad网络中如何寻找某特定的节点? 已知某节点ID,查找获得当前Kad网络中与之距离最短的k个节点所对应的网络信息(Node ID,IP地址,UDP端口)的过程,即为Kad网络中的一次节点查询过程(Node Lookup)。注意,Kad之所以没有把节点查询过程严格地定义成为仅仅只查询单个目标节点的过程,这主要是因为Kad网络并没有对节点的上线时间作出 任何前提假设,因此在多数情况下我们并不能肯定需要查找的目标节点一定在线或存在。 整个节点查询过程非常直接,其方式类似于DNS的迭代查询: a. 由查询发起者从自己的k-桶中筛选出若干距离目标ID最近的节点,并向这些节点同时发送异步查询请求; b .被查询节点收到请求之后,将从自己的k-桶中找出自己所知道的距离查询目标ID最近的若干个节点,并返回给发起者; c. 发起者在收到这些返回信息之后,再次从自己目前所有已知的距离目标较近的节点中挑选出若干没有请求过的,并重复步骤1; d. 上述步骤不断重复,直至无法获得比查询者当前已知的k个节点更接近目标的活动节点为止。 e. 在查询过程中,没有及时响应的节点将立即被排除;查询者必须保证最终获得的k个最近节点都是活动的。 简单总结一下上述过程,实际上它跟我们日常生活中去找某一个人打听某件事是非常相似的,比方说你是个Agent Smith,想找小李(key)问问他的手机号码(value),但你事先并不认识他,你首先肯定会去找你所认识的和小李在同一个公司工作的人,比方说小 赵,然后小赵又会告诉你去找与和小李在同一部门的小刘,然后小刘又会进一步告诉你去找和小李在同一个项目组的小张,最后,你找到了小张,哟,正好小李出差 去了(节点下线了),但小张恰好知道小李的号码,这样你总算找到了所需的信息。在节点查找的过程中,“节点距离的远近”实际上与上面例子中“人际关系的密 切程度”所代表的含义是一样的。 最后说说上述查询过程的局限性:Kad网络并不适合应用于模糊搜索,如通配符支持、部分查找等场合,但对于文件共享场合来说,基于关键词的精确查找 功能已经基本足够了(值得注意的是,实际上我们只要对上述查找过程稍加改进,并可以令其支持基于关键词匹配的布尔条件查询,但仍不够优化)。这个问题反映 到eMule的应用层面来,它直接说明了文件共享时其命名的重要性所在,即,文件名中的关键词定义得越明显,则该文件越容易被找到,从而越有利于其在 P2P网络中的传播;而另一方面,在eMule中,每一个共享文件均可以拥有自己的相关注释,而Comment的重要性还没有被大家认识到:实际上,这个 文件注释中的关键词也可以直接被利用来替代文件名关键词,从而指导和方便用户搜索,尤其是当文件名本身并没有体现出关键词的时候。

  8. 在Kad网络中如何存储和搜索某特定的条目? 从本质上而言,存储、搜索某特定条目的问题实际上就是节点查找的问题。当需要在Kad网络中存储一个条目时,可以首先通过节点查找算法找到距离 key最近的k个节点,然后再通知它们保存条目即可。而搜索条目的过程则与节点查询过程也是基本类似,由搜索发起方以迭代方式不断查询距离key较近的节 点,一旦查询路径中的任一节点返回了所需查找的value,整个搜索的过程就结束。为提高效率,当搜索成功之后,发起方可以选择将搜索到的条目存储到查询 路径的多个节点中,作为方便后继查询的cache;条目cache的超时时间与节点-key之间的距离呈指数反比关系。

  9. 一个新节点如何首次加入Kad网络? 当一个新节点首次试图加入Kad网络时,它必须做三件事,其一,不管通过何种途径,获知一个已经加入Kad网络的节点信息(我们可以称之为节点 I),并将其加入自己的k-buckets;其二,向该节点发起一次针对自己ID的节点查询请求,从而通过节点I获取一系列与自己距离邻近的其他节点的信 息;最后,刷新所有的k-bucket,保证自己所获得的节点信息全部都是新鲜的。

ZeroNet 端口15441

- Posted in Maple's Blog by with comments

第一次建立博客,感觉都比较让人头疼,家里是路由器,所以最好端口开放15441.或者在路由器中打开UPnP设置。

关于打不开自己的站点

- Posted in Maple's Blog by with comments

今天尝试了下,除了自己外其他的访问似乎都存在打不开的问题. 看上去有那么几个点.在论坛里也有朋友说无法打开 正在进一步查看。初步认为是网络同步的问题。

电影下载站-海盗湾

- Posted in Maple's Blog by with comments

几乎所有的电影都能找到,推荐给大家。 海盗湾地址

什么是海盗湾?

海盗湾(The Pirate Bay,缩写:TPB)是一个专门储存、分类及搜寻BT种子的网站,并自称“世界最大的BT种子服务器(BitTorrent tracker)”,提供的BT种子除了有自由版权的收集外,也有不少被著作人声称拥有版权的音频、视频、电脑应用软件与电子游戏,为网络分享与下载的重镇之一。因此,海盗湾也多次遭到取缔。2013年3月,海盗湾声称已经获得了朝鲜政府的虚拟庇护。

bit域名注册

- Posted in Maple's Blog by with comments

看到这个居然可以注册域名,感觉还是很不错的。也尝试去注册一个。 其实注册的流程也是很简单的。就是发一封比特信。 官方文档 我自己申请的格式如下: 标题:want cnmaple.bit domain 内容: domain:cnmaple.bit
ZeroNet site: 1Xu7L66gqq5dc7LEiHPgo9n54F9xq7uym

剩下的就是等待.会给你回一封比特信的。 隔了12个小时,现在已经OK了。

关于Zeronet如何发图片

- Posted in Maple's Blog by with comments

摸索了一会,到处查了查,这个博客的写法与常见的后台编辑器略显不同. 写法为Markdown。 具体的语法就自行google. 我这里主要讲解如何发布图片。 效果如下: image alt 后台代码如下:

![image alt](img/myfirstimg.jpg)