Fissione: A Scalable Constant Degree and Low Congestion DHT Scheme Based on Kautz Graphs阅读笔记

Fissione: A Scalable Constant Degree and Low Congestion DHT Scheme Based on Kautz Graphs

摘要：

分布式哈希表（DHT）已经成为许多大规模P2P网络的核心组件。度、直径和拥塞是DHT中很重要的评估标准。现有的DHT机制多基于传统的互相联络技术，其中具有代表性的是Kautz图；Kautz图具有最理想的直径，最佳的容错性和低拥塞。

在这片论文中，我们提出了FISSIONE——第一个基于Kautz图的有效的DHT机制。FISSIONE是常量度的，直径是O(logN)，拥塞不会超过（1+O（1））。FISSIONE说明了一个常量度和常量拥塞的DHT机制仍然能够保持O（logN）的直径，这个直径比以前的直径下界要低。FISSIONE的平均度是4，直径小于2logN，维护消息的开销少于3logN。平均路由长度约为logN，在同样度情况下，FISSIONE的路由长度比CAN或者Koorde都要小。同时，FISSIONE还拥有较好的负载均衡、高性能、低拥塞；FISSIONE的这些特性将通过论文后续部分的理论证明和仿真来实现。

关键词：

对等网,分布式哈希表,DHT,Kautz graph,congestion-free。

第一部 Introduction and Related Work

DHT有两个重要的评估标准：度和直径。前者是指每一个节点维护的路由表的大小；后者是指查询过程在最坏情况下的路由跳数。

使用静态的Kautz图构建动态的P2P网络有以下三个问题：

1. 节点的ID应该是Kautz字符串，但是目前还没有能够在Kautz名字空间中生成独一无二的Kautz的算法，因此我们提出了一个Kautz_hash算法来实现Kautz字符串的生成。

2. 修改路由最短路径算法以适应于动态P2P网络。

3. FISSIONE提出了一个拓扑规则 neighborhood invariant 来均衡负载以及获得更小的直径。

第二部分 Kautz Graph and Low Congestion

A. 静态Katuz图

定义1：长度为k基为d的Kautz String ks 定义为一个string ,其中是集合{0,1,2,……,d}中的一个元素，并且（1<= i <= k-1)。

定义2：Kautz名字空间KautzSpace(d,k)定义为包含所有长度为k基为d的Kautz string的集合。KautzSpace(d,k)={is a Kautz string}。在KautzSpace(d,k)中共有N=个字符串。

定义3：Kautz图K(d,k)是指一个所有节点的ID都是由KautzSpace(d,k)中的Kautz String给定的有向图。显然，K(d,k)中的每个节点的出度和入度都是d，K(d,k)中共有N=个节点。节点U和节点V之间有一条边(U->V)当且仅当V能够通过U左移一位得到,例如，节点U=有一条边指向V=（对U是出度，对V是入度），当且仅当x!=并且x{0,1,2, ……,d}。

Kautz图和de Bruijn图的唯一区别是：de Bruijn图的节点ID是普通的字符串，而Kautz图的节点ID是Kautz串。

证明Kautz图有最短直径。

给定度d和直径k，图中节点数目的上限N由Moore定理给出：N=1+d+。Kautz图中的节点数目K(d,k)=，非常接近Moore定理的上界。考虑k=2,那么一个图中节点的最大数量是d+d*d，此时Kautz图是完备的（K(d,2)，N=d+d*d）。根据Moore定理，容易计算出一个有N个节点的图的直径的下界是，此时直径为k的Kautz图K(d,k)达到了这个下界。（因为 = k+1-1=k，即二者相等）。

B. 低拥塞路由

Kautz图选择长路径路由算法(Long Path Routing algorithm)。

定义4：长路径路由算法：Kautz图K(d,k)中节点U=到节点V=的路由路径是一个如下所示的长度为k的路径：

U==V （）

U==V（）(此时长度为k-1)

这样可以计算出Long path routing algorithm的平均路径长度h=（d/(d+1))*k+(1/(d+1))*(k-1)=k-(1/(d+1))。这个长度比shortest path routing算法要长一些，但是long path routing algorithm算法负载均衡性更好。

定义5：P2P网络中的c-congestion-free（c是常数且c>=1）是指：在all-to-all通信的情况下，此P2P网络既是c-node-congestion-free，也是c-edge-congestion-free的。c-congestion-free指网络中只有c个拥塞或者常数个拥塞。c-node-congestion-free是指每个节点处理的平均通信数量不会超过c个，c-edge-congestion-free是指每条边处理的平均通信数量不会超过c个。

uniform all-to-all communication（完全all-to-all通信）是指：对于每一对节点U，V（U！=V），在U和V之间有且只有一个单元的通信量。静态P2P网络是指，假定名字空间中所有节点都存在且在线。

在uniform all-to-all 情况下，网络中共有N*（N-1）个路由消息，假设路由路径平均长度是h，那么每个节点将处理（N-1）*h个路由消息，而每条边将处理N*（N-1）*h/|E| (E是指网络中边的条数)条消息。

定理1：采用long path routing算法，Kautz图K(d,k)是(1+O(1))-congestion-free的。

通过5个定义和1个定理，我们从理论上分析了FISSIONE的特性，FISSIONE具有常量度，最优直径，最好的容错特性。在网络足够大的时候，FISSIONE是congestion-free的。

Fissione Design

A. Overview

Fissone使用度为2的Kautz图K(2,k)作为其静态拓扑。Fissione中多有节点共同组成二维笛卡尔坐标空间，每个节点拥有一个区域。初始时，所有节点的ID长度相同，且共同组成Katuz空间。当有新节点加入或离开时，Kautz空间会被划分（分割大区域原则，合并小区域原则），节点ID的长度有可能改变。出于维护性能的需要

© 2007, dolf. All rights reserved.