自然之道

chord.ppt ： Manan Rawal, Bhaskar Gupta

Chord：

定义：

m-bit ID

数据结构：

    succesor(k) = first node whose identifier is >= identifier of k in identifier space.
    Finger Table: finger [k] = first node that succeeds (n+2^(k-1))mod(2^m)
    finger [1] 即 succesor

    路由表:

        前驱，后继

基本逻辑：路由（可扩展的）

    n.find_successor(id) 问节点n：你知道id A的后继是哪个吗？：功能：找内容，因为id A的内容就存在id A的后继上。

// ask node n to find the successor of id
n.find_successor(id)
    if (id belongs to (n, successor])
        return successor;
    else
        n0 = closest preceding node(id);
        return n0.find_successor(id);

// search the local table for the highest predecessor of id
n.closest_preceding_node(id)
    for i = m downto 1
        if (finger[i] belongs to (n, id))
            return finger[i];
    return n;

特别逻辑：对付网络的变化，如节点加入、离开、异常断开

A：节点加入和稳定

节点A加入: 操作：
    1）改变A前驱的successor为A
        找到A的前驱，通知它
            加入新数据结构：前驱
                前驱的维护

    2) 初始化A的succssor和finger table
            succssor即其前驱的successor
            finger table从其前驱和后继的finger table可以初始化

Chord方法：每个节点周期运行稳定算法，更新数据结构

n.create()
    predecessor = nil;
    successor = n;

n.join(m)    初始化后继
    predecessor = nil;
    successor = m.find_successor(n);

n.stabilize() 周期运行，更新自己的后继为后继的前驱。并通知该后继节点更新自己的前驱为我
    x = successor.predecessor;
    if (x in (n, successor))
        successor = x;
    successor.notify(n);

n.notify(m)
    if (predecessor is nil or m in (predecessor, n))
        predecessor = m;

n.fix_fingers()    周期运行，更新finger table的项
    next = next + 1 ;
    if (next > m)
        next = 1 ;
    finger[next] = find_successor(n + 2^(next-1));

n.check_predecessor()    周期运行，检查前驱的正确性
    if (predecessor has failed)
        predecessor = nil;

维护正确的后继是关键

加副本：r个副本

改进：让那种主动退出的节点做一些退出前的迁移工作：
    - 把存的key传给后继
    - 通知前驱和后继：自己要走了，请更新自己的后继或前驱

Triantafillou, P. (2003), “PLANES: The Next Step in Peer-to-Peer Network Architectures”, In SIGCOMM Workshop on Future Directions in Network Architectures (FDNA-03), Karlsruhe, Germany, 27th August 2003.

用大公无私的节点做簇头，组成顶级的Overlay。用Hashing把node id映射到簇。

性能评估：O(logn）类似的讨论。

UK

ROME协议可以根据Chord环的负载调节它的大小，即节点监视自己的负载情况，然后节点可以根据网络的负载情况加入或离开，这样N保持最优。由bootstraper服务器中心控制（2005）

将多个网的自举服务器联起来，形成高层网络。实现跨网的服务器共享。

server通过关键字声明自己能支持和不能支持的业务，这样才能匹配两个服务器。

查询带上查询节点的关键字。通过的节点利用这些关键字觉得它是否是语义上更好的邻居。

优先保证本地的。给本地留有余地。

过程：
- 登记：初始化自己的邻居表。要求邻居把自己加到邻居表里。消息经过的时候更新自己的邻居表。
- 查询；用TTL防止无限循环和死锁。不能部分reserve

仿真：
- 目的：证明能增加系统整个的负载量
- 三步：关键词产生、server构造和初始化。

参考；
Castro, M., Druschel, P., Kermarrec, A-M. and Rowstron, A. (2002), “One Ring to Rule Them All: Service Discovery and Binding in Structured Peer-to-Peer Overlay Networks”, in Proceedings of the SIGOPS European Workshop, France, September 2002.

Mislove, A. and Druschel, P. (2004), “Providing Administrative Control and Autonomy in Structured Peer-to-Peer Overlays”, In Proceedings of the 3rd International Workshop on Peer-to-Peer Systems (IPTPS‘04), San Diego, CA, USA, 26th-27th February 2004, pp. 162-172.

通过ID空间的划分，反映连接限制。对应用来说是透明的一个网络。
- 内容和路由的本地化。
- 原生性地支持NAT和防火墙

每个环有一个环ID。顶级环的环ID为全0.

所有节点加入顶级环（负载均衡），除非在NAT后。所有节点也加入自己的环。

网关节点在自己加入的各组内声明自己外联的网络。（通过加入Anycast组）

路由：Key: 环ID+Key。
通过环ID，走Anycast，默认是顶级环。

如何得到key对应的环ID：将Key对应的环ID存在顶级环里。

通过cache解决性能的问题。

在FreePastry里面实现了。

参考：

Skipnet [13] 第一个清楚地表达了对内容和路由的本地化的需求。它按位置分配节点ID。
Scribe [5],[6] 在组内维护一个组员到组长的生成树，实现组播和单播。
Coral[9], 用多个环提供数据本地存储。根据测量的Ping延时动态配置。
[14]在一个Chord环里通过特别的路由办法，找到一个子环里的最近的节点。（不提供路由本地化）

[13]  N. Harvey, M. Jones, S. Saroiu, M. Theimer, and A. Wolman.
Skipnet: A scalable overlay network with practical locality properties.
In Proc. USITS 2003, Seattle, WA, 2003.

[5]  M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. SCRIBE:
A large-scale and decentralized application-level multicast infrastruc-
ture. IEEE JSAC, 20(8), Oct. 2002.

[6]  M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron.
Scalable application-level  anycast for highly dynamic groups.   In Proc. NGC
2003, Munich, Germany, 2003.

proximity neighbor selection [3, 12],

[9]  M. Freedman and D. Mazieres.   Sloppy hashing and self-organizing
clusters. In In Proceedings of the 2nd International Workshop on Peer-
to-Peer Systems (IPTPS ’03), Berkeley, CA, 2003.

[14]  D. Karger and M. Ruhl.   An augmented Chord protocol supporting
heterogeneous subgroup formation in peer-to-peer networks.  In Pro-
ceedings of the 3nd International Workshop on Peer-to-Peer Systems
(IPTPS’04), San Diego, CA, 2004.

这里提到的其他论文的概括还不错。

Garcés-Erice, L., Biersack, E.W., Ross, K.W., Felber, P.A. and Urvoy-Keller, G. (2003), “Hierarchical peer-to-peer systems”, in Parallel Processing Letters, Vol. 13, No. 4, pp. 643-657.

2级Chord。先找组，再在组内找节点。

学习Internet的等级路由。

好处：
    - 减少查找的跳数
    - 在组内查找快
    - 以组为单位进行管理。组可以用不同的DHT协议。

每组挑出一些超级节点作为网关节点。网关节点组成顶级Overlay，负责组间消息的路由。

合作缓存机制：减少数据传输延时

算法：
    - 分配节点到组
    - 选出超级节点
    - 维护顶级Overlay

具体分析了用Chord做顶级overlay的性能：
    - 模型
    - 分析了期望的查找跳数

查询：到本组超级节点，到负责该Key的组的超级节点，再到负责该key的节点。

关键问题也就是这些问题：
    - 到本组超级节点：集中的超级节点列表（不论是中央服务器还是作为键值对存在网络中）
    - 组间路由：明确指定组ID/ID空间划分间接组寻址

当多级的时候，总是先路由到顶级。然后一级级下来。

节点加入组g。
     - 在网络中存g-超级节点list。 
    - 节点查询key=g，得到超级节点的list，然后向这些节点申请加入。（所以ID空间是独立的）

超级节点维护候选超级节点列表，并定时发给各节点。
    - 监视组内节点特点：开机时间、CPU、带宽、

当一个超级节点失败时，候选超级节点列表中的第一个节点主动加入上一级Overlay。并通知组内节点和上一级Overlay的邻居节点。

用组内的对应于该Key的节点做Cache。改善性能。

修改Chord。变邻居IP为邻居IP列表，其中包括邻居组的超级节点列表

当组的超级节点变化时，立刻更新前驱和后继的路由表，但Lazily更新finger表的自己。

模型分析：

性能改善来自稳定节点的选取和环内节点数的减少

P个节点、I个组。两种节点：稳定节点(宕机概率Ps）、不稳定节点（宕机概率Pr）。Pr>>Ps

考虑（N，p）。

假设：
- N个Peer在2^m上均匀分布，距离2^m/N
- finger table里的项有p的概率宕机，但后继总是对的：因此，总能前进

随机选择的查询节点和产生的Key，H：跳数。T：查询节点和Key之间的距离（随机变量），求E[H]。
要求h(n)=E[H|T=n]. h(1)=1
jn: finger表中n前面的finger表项的个数。
所以：如果第jn项的peer没宕机，一跳能前进x=(2^jn)*(2^m/N)这么多的距离。h(n)=h(n-x)+1
如果第jn项的peer宕机，而第jn-1项的peer没宕机,一跳能前进x=(2^（jn-1）)*(2^m/N)这么多的距离。h(n)=h(n-x)+1
这样就得到回归方程式。

忽略组内查表（组很小，64-256）。模型Chord的查询跳数与N, Pr的关系。

参考：

<100个节点的全连接网络用CARP [18].
100-1000用consistent hashing [19]
[14] 测量与M个landmark的RTT，将结果排序，判断自己属于M!个组中的哪一个。然后获得这个空间的ID。由此实现位置敏感的Overlay。用CAN做了实验。
KaZaA：高可用和高性能节点做超级节点，新节点联到RTT最近的超级节点。超级节点组成一个Overlay. CAP[15]用类似的结构
Brocade [16] 类似于[14]+[15]. 但如果有[14]了，它为何还要[15]呢？需要看一下它的论文。
[17]:改进了Pastry, 每一跳路由时选择最近的节点。但越往后，可供选择的余地越小，而最后一跳往往是最长的。

14.  S.   Ratnasamy,   M.   Handley,   R.   Karp,   and   S.   Shenker,
“Topologically-aware overlay construction and server selection,”
in Proceedings of Infocom’02, (New York City, NY), 2002.

15.  B. Krishnamurthy, J. Wang, and Y. Xie,
“Early measurements of a cluster-based architecture for p2p systems,”
in ACM SIGCOMM Internet Measurement Workshop, (San Francisco, CA), November 2001.

16.  B. Y. Zhao, Y. Duan, L. Huang, A. D. Joseph, and J. D. Kubiatowicz,
“Brocade: Landmark routing on overlay networks,”
in In Proceedings of IPTPS’02, (Cambridge, MA), March 2002.

17.  M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron,
“Exploiting network proximity in peer-to-peer overlay networks,”
Tech. Rep. MSR-TR-2002-82,  Microsoft  Research,  One  Microsoft  Way, Redmond, WA 98052, 2002.

18.  K. W. Ross, “Hash-routing for collections of shared web caches,”
IEEE Network Magazine, vol. 11, 7, pp. 37–44, Nov-Dec 1997.

19.  D. Karger, A. Sherman, A. Berkhemier, B. Bogstad, R. Dhanidina, K. Iwamoto, B. Kim, L. Matkins, and Y. Yerushalmi,
“Web caching with consistent hashing,”
in Eighth International World Wide Web Conference, May 1999.