Pastry学习笔记

作者 cnss  2004-8-19版权所有 转载请注明出处http://blog.csdn.net/cnss

★Pastry是一套peer-to-peer网络协议,Pastry有如下基本特性:

1. 每个节点都有一个随机生成的128位nodeid.当收到一条含128位key的消息时,节点能高效地将消息发送到在当前节点中,数值上nodeid最接近key的节点.在Pastry网络中里,发送步骤的复杂度应该是O(log N),在每个Pastry节点中,路由表要维护节点数量的复杂度是O(log N).在消息传递经过的每个Pastry节点时,会通知回调函数,应用程序可以对这条消息做一些处理.

2. 每个Pastry节点监视和它nodeid值最接近的L个节点(这个集合叫作leaf set,其中比当前节点nodeid大及小的节点各占L/2),应用程序可以通过回调知道leaf set中新节点的加入,节点的失效,节点的恢复.

3. 在互联网上的位置很重要,Pastry探寻消息传递的最小距离,比如以ping的延时作为判断的依据. Pastry网络是分散的,灵活的,自组织的;当出现新节点,死节点,节点失败时它会自动配置.

★几个重要的参数:b:一般取1,2,3,4.内部处理128位id时用的进制为(2的b次方).L: leaf set的容量,一般取(2的b次方)或(2的b+1次方).M: neighborhood set的容量,一般取(2的b次方)或(2的b+1次方).为表达方便,N代表网络中存活的节点数.

★节点需要维护的三种数据,如图1:

1. leaf set:容量为L,用于保存在数值上最接近nodeid的节点,其中smaller和larger各占一半.

2. routing tableLog以(2的b次方)为底N的对数行,每行(2的b次方)-1条数据.第n行表示nodeid与当前节点的前n位相同,且第n+1位与当前节点的不相同.图1中阴影部分表示当前节点nodeid的相应段,把每行的阴影读下来就是当前节点的nodeid.

3. neighborhood set保存节点的直接邻居(如ping值最小的M个节点),它不是用来路由消息的,而是为配置网络服务的.

图1: