p2p之Chord协议的一些问题(50分)

  • 主题发起人 linuxping
  • 开始时间
L

linuxping

Unregistered / Unconfirmed
GUEST, unregistred user!
1,nat穿透最好使用什么技术? upnp?
互联网上容易找到的nat穿透方法都需要一个具有公网ip的server。这有点违背p2p精神。
如何实现只需要知道p2p grid中一个已经存在的节点(种子)就可以登录p2p grid?

假设已经知道了一个p2p grid中的节点NodeA(ip xxx.xxx.xxx.xxx,port 12345 当然这只是映射到nat之后的ip,port)。它的前缀节点是predA,后缀节点是SuccA。
问题2:
如果NodeA处在一个nat后面,而没有server,如何连接到NodeA?

问题3:
Chord 上的节点A突然下线(比如 直接关机)。 ,在没有服务器的情况下,如何通知它的前缀节点和后缀节点? 一个方法是每个节点都定时轮询它的前缀节点predA和后缀节点SuccA。当节点A突然下线时,前缀节点predA轮询发现NodeA无法连接,它怎么重新建立chord 环?
一个容易想到的方法是在每个节点上存储多个前缀节点(predA1,predA2,predA3.。。。),多个后缀节点(SuccA1,SuccA2,SuccA3。。。),当前缀节点predA1轮询发现NodeA无法连接时,他就直接连接到succA1,建立chord环。但是这时轮询成本增大,如果每个节点上存储5个前缀节点,5个后缀节点,哪么它就要轮询10个节点? 这会增加网络负荷。 有没有什么更好的方法?
如果每个节点上保存的前缀节点和后缀节点太少,那么,如果choed环上的几个连续的节点同时下线,怎么办?
即使我们保存足够多的前缀节点和后缀节点,choed环上的足够多的连续的节点同时下线的可能还是有的。这时chord环会断裂。chord网络会崩溃。怎么办?


////////////////////////////////////////////////////////////
最后给个网站: http://pdos.csail.mit.edu/chord/#downloads
程序下载: http://pdos.csail.mit.edu/chord/snapshots/
还有Macedon (C++).
i3/Chord (C, appears to support Windows).
P2 (A custom declarative language).
The Circle (Python).
Open Chord (Java).
Overlay Weaver (Java).
i3 (Java, J2EE).
nchord (C#)
可以在sf.net上找到。
 

地质灾害

Unregistered / Unconfirmed
GUEST, unregistred user!
L

leonmtv

Unregistered / Unconfirmed
GUEST, unregistred user!
IM本身就需要數據庫的支持,雖然沒有做過,但也有看過這方面的原理
 
L

linuxping

Unregistered / Unconfirmed
GUEST, unregistred user!
IM本身就需要數據庫的支持.
在分布式存储里不一定需要数据库。
举个例子:
比如: 你想向chord网络上载一个文件。 假设将文件分成10块。part1,part2.。。。。。part10.
现在使用一个hash算法(这个hash算法会使不同的内容得到不同的hash值,也就是说只要文件不同,hash结果就不同。电子签名就这个原理)
v1=hash(part1),v2=hash(part2)。。。。。。。。。。
现在将vi再进行一次hash,使hash结果得到一个整数。int1=hash(v1),int2=hash(v2)。。。
假设网络上已经有很多主机A,B,C。。。。。。
将每个主机的ip,port(当然指公网的)进行hash,使hash结果得到一个整数,而且不同ip,port hash结果不同。 ipportA=hash(ipA,portA),ipportB=hash(ipB,portB),。。。。。。。。。ipportN=hash(ipN,portN),

然后,将文件的第x块存储(udp,tcp等传输)到 和第x块文件hash出的整数int1与主机hash出的整数ipportX最接近的主机上(就是intx和ipportX接近)。
当某个主机下线时,它必须重新计算和它存储的文件块的intx最接近的主机,把文件传给这个主机。
当你要下载文件时,你只要给出每块的vx,然后,在网络上查找,存储有hash结果为vx的文件的主机,建立连接即可。
这样文件被很随机地存储到网络上的节点中。每个节点都有可能,而且当节点下线时,文件在节点间复制。
QQ的消息留言也可以用这个方式来做。甚至email也可以用这种方式。(用途很多,[:D][:D])
那么,在p2p网络中不 需要服务器。 每个节点都是服务器。不需要数据库,每个节点都可以充当“数据库”。 这个数据库够大吧!
上面只是一个例子,现实中这样做肯定行不通.比如: 我说"文件在节点间复制", 这肯定不行,网络承受的了吗?! 比如: 有很多主机是动态ip,ip不停在变。

一言难尽。 看看资料吧。http://user.qzone.qq.com/254930005 有一些资料.
 
L

linuxping

Unregistered / Unconfirmed
GUEST, unregistred user!
如果你不是来回答我的问题。
也不是来帮顶的。
只发些没有用的信息,甚至反面信息,就不要来搅和了。
 
X

xmcccc

Unregistered / Unconfirmed
GUEST, unregistred user!
这种技术还不成熟吧,数据快速恢复,快速查找,如果网络主机很多,你如何通过一种算法,能够快速在在网络里广播一条查询请求,如果有很多查询请求呢,又如何做,还有数据在存储也是非常难做的,一句话,不成熟,如果技术成熟了,大公司肯定早这样做了,这样没有服务器,运营成本就非常低了
 
C

cqwty

Unregistered / Unconfirmed
GUEST, unregistred user!
这个问题很有深度啊,不想通过公网上的server来完成穿透。
这里就我的理解,随便说说,可能有说错的地方,关于p2p方面是很久以前就看过的了。
首先,现在的p2p网络并没有违反什么p2p法则。公网上的服务器只是维持p2p中的节点的信息而做的,并且必须首先连接到这个server才可以从局域网的电脑打洞出来,通过nat转换,获得相应的公网上的ip地址和端口的映射,如果这个完不成,后面的工作就没有办法做了。而这个server的主要工作,就是维护这些信息。
第二,你说到chrod中某个节点突然下线或者掉线,那么以他为前缀的节点如何处理的问题。在这个上,建议你的chrod网络中每个节点只保留前缀节点,而不保存后缀节点,而且前缀节点也不要保留过多,建议保留3到5个即可。那么,如此一来,每个节点轮训的时候,它只负责轮训它的前缀节点了,这样就大大的减少轮训是带来的网络负载。这里你可能会问,保留的3到5个前缀节点理由是什么。这里你可以看一下层次网格方面的研究了。层次网络在现有的物理网络上建立了一个逻辑的分层次的网络体系,模型类似于行政管理模型。比如国家的行政管理模型,顶端就是核心,然后下来是几大部委,再下来是各省市,……。那么在人事管理制度上就类似的有某个领导调离的情况了。如果财政部长调离了,那么下面的各省的领导自然知道,自己的某个上级领导调离了,应该找另外一个,而调离的部长没有必要挨个通知(轮训)自己的上级和下级,告诉他们自己调离了,对吧。当然这个例子有不合适的地方,那就是这种人事任免,上面都会发公文公告的了。但是咱们这里只是例子。通过这个例子,chrod网络中的任何一个节点,只对自己的前缀节点也就是上级节点负责,不对下级节点负责。现在回答,为什么建议只保留3到5个,主要是考虑网络中使用到前缀节点的时候,只会使用到一个,那么其他的基本都没有用,当有最主要的一个实效以后,那么把备用的顶替上来,然后又根据算法查找一个合适的来填充这一个空缺的。这样就不用轮训那么多前缀节点了。
不知道我的说法是否有可取的地方,如有说错,勿取笑。要搞p2p,建议在网络模型上,学习一下网格。虽然到现在为止,网格还在出于实践阶段。
如果到了ipv6真正投入互联网使用的时候,ip地址不在受到限制,那么大家都能获得一个公网的ip地址,这样就不用公网服务器了,也不需要nat转换了,p2p网络就真正实现了。
 
L

linuxping

Unregistered / Unconfirmed
GUEST, unregistred user!
//////////////////////////////////////////////////////////
建议你的chrod网络中每个节点只保留前缀节点,而不保存后缀节点
//////////////////////////////////////////////////////////
--->A--->B------->C
| |
|----E<----- D<--|
假设有5个主机a,b,c,d,e。 chord环是上面这个样子。
现在,A保存B,C的信息,B保存C,D的信息。。。。。。。。。。
假设现在 主机B下线。B必须通知A与C建立连接,但B上没有A的信息,如何通知A?
所以,前缀节点和后缀节点都必须要。
 
L

linuxping

Unregistered / Unconfirmed
GUEST, unregistred user!
来自:xmcccc, 时间:2008-10-7 9:25:55, ID:3924330
这种技术还不成熟吧,数据快速恢复,快速查找,如果网络主机很多,你如何通过一种算法,能够快速在在网络里广播一条查询请求,如果有很多查询请求呢,又如何做,还有数据在存储也是非常难做的,一句话,不成熟,如果技术成熟了,大公司肯定早这样做了,这样没有服务器,运营成本就非常低了


chord网络的查询成本是O(log(N)),N为网络中节点数。
也就是说如果网络中有1000,1000(QQ平均在线人数也没有一百万吧)个主机。只路由只需要20跳(2^20=1024*1024>1000,000)。这可以接受。
 
C

cqwty

Unregistered / Unconfirmed
GUEST, unregistred user!
--->A--->B------->C
| |
|----E<----- D<--|
假设有5个主机a,b,c,d,e。 chord环是上面这个样子。
现在,A保存B,C的信息,B保存C,D的信息。。。。。。。。。。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
你的A为什么要保存B和C的信息呢?按照你的说法,A只保存B和E的信息了。
假设现在 主机B下线。B必须通知A与C建立连接,但B上没有A的信息,如何通知A?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
如果你的B主机不是正常下线,那么你的就是保存了信息,你又如何通知呢?你轮训出来?
所以,前缀节点和后缀节点都必须要。

继续我的疑问:你这个只是一个单环的结构,你就保证网络上的主机都只能建立一个单环吗?而且,如果公网不需要一个服务器,那么在现有的网络上,一台局域网内的电脑,如何和其他的电脑连接上呢?这是现有协议不许可的啊。按照p2p的思想,任何两个网络节点之间,都可以找到一条可达的路径,只有这样,才满足你的需求。
 
L

linuxping

Unregistered / Unconfirmed
GUEST, unregistred user!
"你这个只是一个单环的结构,你就保证网络上的主机都只能建立一个单环吗?"
chord网络就是一个单环的结构。
http://pdos.csail.mit.edu/chord/faq.html#what

谢谢您的回答!
 
L

luoyanqing119

Unregistered / Unconfirmed
GUEST, unregistred user!
EMC的那种主机HA软件能实现你的问题三,一个结点段线后(心跳能检测),另外的结点迅速接管过来。
 
L

linuxping

Unregistered / Unconfirmed
GUEST, unregistred user!
to luoyanqing119:
你的 回答只是对软件功能的描述,能有原理上的东西么?
thanx
 
顶部