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

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上找到。

帮顶。

IM本身就需要數據庫的支持，雖然沒有做過，但也有看過這方面的原理

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也可以用这种方式。（用途很多，[][]）
那么，在p2p网络中不 需要服务器。 每个节点都是服务器。不需要数据库，每个节点都可以充当“数据库”。 这个数据库够大吧！
上面只是一个例子,现实中这样做肯定行不通.比如: 我说"文件在节点间复制", 这肯定不行,网络承受的了吗?! 比如: 有很多主机是动态ip，ip不停在变。

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

如果你不是来回答我的问题。
也不是来帮顶的。
只发些没有用的信息，甚至反面信息，就不要来搅和了。

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

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

//////////////////////////////////////////////////////////
建议你的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？
所以，前缀节点和后缀节点都必须要。

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


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

--->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的思想，任何两个网络节点之间，都可以找到一条可达的路径，只有这样，才满足你的需求。

"你这个只是一个单环的结构，你就保证网络上的主机都只能建立一个单环吗？"
chord网络就是一个单环的结构。
http://pdos.csail.mit.edu/chord/faq.html#what

谢谢您的回答！

EMC的那种主机HA软件能实现你的问题三，一个结点段线后（心跳能检测），另外的结点迅速接管过来。

to luoyanqing119:
你的 回答只是对软件功能的描述，能有原理上的东西么？
thanx