一个节点收到建树消息后，首先得到本节点的树坐标。然后根据本节点的坐标计算M个子节点的坐标Nn，如式3–1所示。
得到子节点坐标后，通过坐标号计算节点的序号Sn，如式3–2所示。
Sr为根节点的序号。如果这个序列号大于St那么序列号为Sc = Sn-St为表的总序列号，否则Sc=Sn。
特殊情况下，会发生领导节点失效或退出的情况。因为领导节点处于组内的边缘，是组内信息传递的根节点，所以在种情况下需要特殊处理。领导节点之间有Keep-Live信息确保相邻节点在线。如果一个邻居节点的退出或失效，那么相邻的领导节点把信息直接传给失效节点的子节点以确保失效组内不受Lg失效的影响而能继续通过传播树的来传播信息。但这是应急传播结构，这种应急结构会使失效节点的邻居节点负责的过多的事务，还要通过重构机制来重新构筑失效组的传播树。重构机制中首先把失效节点的后继节点作为新的Lg节点，并把原Lg节点的传播树子节点作为新Lg节点的子节点，这样就可以只需要重构传播树的一层结构就可以恢复传播树的功能。找到新的Lg节点并重构传播树后还需要其它节点更新GLM标识信息，Lg失效后各个节点更新路由表中的GLM标识信息。
图3–7消息传播路径树建立的过程伪代码
3–4) 算法性能分析
在G 1-Hop算法中拓扑变化事件消息的传播路径为树状传播，与One-hop的路径不同。在原算法中的拓扑信息传播方式中把节点分为若干个Slice，一个Slice分为若干个Unit。每个Slice都有一个Slice Leader，每个Unit也有一个Unit Leader，其他节点为普通节点。消息的传播路径为:SL一其它SL-UL一后继或者前驱节点依次传播，本质上是一种线状传播路径。本方法中传播的路径为:GL一各层子节点，采用的是一种树状的传播方式，这样能更快的传播消息。在原方法中，首先从发现事件的节点传到SL节点，再从SL节点到其他SL节点。事件消息经过SL到UL节点。前面这几次传播需要3跳，最后从UL节点线性传播出去，一个Unit的节点数量为U，那么时间消息传遍Unit的跳数为U/2，所需的总跳数为3十U/2，跳数的渐进函数集合为O(n)。
如消息直接从发现消息的节点发送到M个GL节点，不需要经过本组的GL节点发送到其他GL节点。每个节点都有相同的路由信息，所以这样能充分利用这些信息，直接把消息传到所有GL节点。到达GL节点后，以GL节点为根节点通过消息传播子树把事件消息通知给每一个节点。所以G1-hop传播拓扑变换消息所需的跳数为H，如式3–4–1所示。跳数的渐进函数集合为Φ logs (n)。
计算可得两种算法消息传播跳数对比如表3–4–1，对应的传播跳数对比如图3–8所示。算法1为G 1-hop算法，算法2为One-hop算法。从图4–14中可以看出，G 1-hop所需的跳数少于One-hop算法。而且随着网络中节点数量的增加，这种差距更大。在传播时间上，One-hop算法的事件消息的总传播时间分为传播时间和周期等待时间，所以总的消息传播时延除了包括每一跳对应的传播时间外，还要包括周期等待时间。G1-hop算法不需要等待时间，所以总的消息传播时延
只需要每一跳对应的传播时间。在同样网络的条件下，每一跳对应的平均传播时间相同，所以G 1-hop算法的消息传播时延小于One-hop算法。G1-Hop是一种分布式P2P系统中的全局资源发现算法，算法的性能瓶颈在于网络交互时延，通过事件消息传播树机制减少了信息在网络中的传播跳数，从而也减少了信息在网络中的传播时间，把每一跳作为网络传播基本时间，原传播方法的网络传播时间复杂度为。(n)，而Gl-Hop传播方法的网络传播时间复杂度为Φ (logs (n))
表3–4- 1两种事件消息传播算法所需跳数计算结果
图3–8 G1-hoop与One-Hop消息传播跳数对比
3–5）局域内容路由算法LCRR
3–5–1）LCRR基于结构化DHT网络，每个服务器协作组SCG为一个独立的结构化DHT网络。当一个节点要加入服务器协作组SCG的时候，通过节点加入算法找到所归属的全局内容资源发现层入口节点与相应的SCG组。找到所归属的内容资源发现层节点后，新加入的节点与相关节点完成信息交换与更新。
如图3–9所示，SCG节点中与LCRR相关的模块包括路由表、索引表、索引存储与缓存模块、服务区分与负载调度模块、L-G转换模块等。LCRR基于路由表与索引表中的信息完成请求过程。路由表中存储的是服务器协作组SCG的辑层网络路由信息，包括网络中节点的逻辑层地址信息。索引表中存储的是内容对象所在服务器的信息。网络中内容索引信息分散在SCG的各个节点中，每个SCG节点保存部分内容索引信息。通过内容索引存储与缓存模块控制内容索引在网络中的存储分配，并且通过关联内容索引缓存机制对内容索引进行缓存。当内容请求被路由到内容所在节点后，要通过服务区分与负载调度模块来为请求分配服务资源。如果SCG中没有Client所需内容，那么通过L-G转换模块把局域内容路由过程转换为全局内容资源发现过程，通过全局内容资源发现算法去全局范围内查找内容资源。
在此详细介绍网络节点加入方法、G-L协作机制、内容索引分配与缓存机制、服务区分与负载调度、请求路由过程。
图3–9 LCRR相关模块
3–5–2）网络节点的加入
LCRR位于架构的SCG层。服务器协作组SCG是距离较近的服务器的集合，这些服务器组成一个P2P协作网络。另外，SCG组之间需要协作，这个协作是通过全局资源发现层来实现的。每个服务器协作组SCG都要选择一个较近的资源发现层节点作为进入全局资源发现层的入口节点。所以当一个节点需要加入服务器协作组时，需要找到一个入口节点。找到了入口节点也就找到了所要加入的服务器协作组。
全局资源发现层的节点分布在网络中。CDN管理层存储有这些节点的谱系图信息。通过谱系图可以得到这些节点之间的分组信息。本节所设计的入口节点选择方法主要思想是:首先，需要加入网络的节点找到距离上比较近的全局资源发现层节点分组。然后在这个分组中找到距离较近的节点。把这个节点作为入口节点。
根据谱系图可以把所有资源发现层节点分为K组。当节点要加入时首先获得网络中一个一直在线的固定节点信息，相当于其它方法中的自举节点。加入节点首先通过固定节点告知网络有节点要加入。当服务器协作组SCG有节点要加入时，监测节点MP测量这个节点的时延距离Dti找到与Dti时延差最小的分组，把这个分组作为入口分组。然后加入节点在这个分组中找到距离最近的节点，把这个节点作为入口节点。
每一个入口节点负责一个服务器协作组。节点找到入口节点后，从入口节点下载服务器协作组节点的拓扑信息。然后找到前驱节点和后继节点，即找到加入的位置。与前驱节点和后继节点建立连接。最后把拓扑更新信息传播到其它节点。
Step 1:要加入节点向固定节点上报信J息、。
Step2:测量MP到加入节点的距离。
Step3:得到最近的内容资源发现层分组信J自、。
Step4:从分组选择接入节点。
Steps:下载服务器协作组SCG的拓扑信J息
Step6:找到前驱与后继节点，更新拓扑信息表，告知其它SCG组内节点。
3–5–3） G-L协作机制
全局资源发现层与服务器协作组SCG层在一些情况下需要相互协作。服务器协作组在组内的服务器之间协作，所以SCG层的局域路由只支持在同一个服务器协作组之内的内容共享。如果服务器协作组中不存在所请求的内容，会启动全局资源发现过程在全局范围内查找所请求的内容。通过全局资源发现系统找到存储有所请求内容的服务器协作组。全局资源发现层只能定位到内容所在的服务器协作组，如果需要定位到内容所在的服务器同样需要局域路由系统的协助。这就需要一个在全局资源发现层与局域请求路由之间的协作模块。这里设计了路由表和相关的功能模块支持局域路由系统与全局资源发现层之间的协作。
首先介绍从局域路由系统转换到全局资源发现系统的机制。当一个用户对内容的请求被重定向系统定向到最近的服务器后，如果这个服务器中没有所请求的内容，请求将被发送到局域路由系统。请求将被路由系统路由到服务器协作组中具有所请求内容的服务器中。如果服务器协作组中没有所请求的内容那么请求被导向全局资源发现层。
为了实现上面所述的机制，设计一种路由表，并基于路由表由L-G转换模块控制转换。路由表的第一个功能是维护服务器协作组的网络拓扑信息。路由表的第二个功能是提供接入全局资源发现层所需的信息。服务器协作组中的每个节点维护一个路由信息表，每个节点中的路由信息表是相同的。路由表分为两个部分，组内路由信息和组外路由信息。当协作组内没有所请求的内容资源时，请求被路由到组外去寻找相应的内容资源。组外的路由信息是服务器协作组到资源发现层的入口节点列表。这些列表就是节点加入方法中的同一个聚类分组中资源发现层节点的信息。一般情况下SCG节点接入到直接负责本协作组的入口节点，当直接负责入口节点出现故障的时候可以通过列表依次选择其它节点。
从图3–10可以看到，组内路由信息由协作组中节点的拓扑信息组成。一个服务器的地址信息对应表的一项。所以在组内路由时可以通过这个表找到相应节点的地址信息。组外的路由信息由全局层接入点的地址信息组成。一般情况下，由距离协作组最近的一个或者几个全局层节点作为接入点。
如图3–10所示，全局层有四个节点，协作组也有四个节点。路由表中的条目Ga_ID是这个服务器协作组的全局接入点。接入点是ID为2的节点。路由表的组内信息有四项，是组内的四个节点的地址信息、。
其次，还需要设计从全局资源发现层到局域路由转换机制。全局资源发现层只能定位到内容所在的服务器协作组，如果需要定位到内容所在的服务器就需要内容所在协作组的局域路由系统的协助。所以，入口节点要保存SCG的拓扑信息表，并通过G-L模块控制全局资源发现层与服务器协作组层的转换。
图3–10 G-L协作机制与相关模块
3–5–4) 内容索引分配与缓存机制
在LCRR中设计了一种关联内容索引缓存的方法来提高内容路由效率。用户对内容的请求是有关联的，把有关联的内容索引缓存到相应的节点。当用户再需要其它内容的时候就不需要再次对内容请求路由。
内容的索引项是与内容数据对象的存储相对应的，每个内容对象对应一条内容索引。例如，如果CDN中分发的内容为视频文件，以切片为单位存储，那么每个切片对应一条索引。当一个内容切片存储在服务器中后，索引项也随之建立。索引项的形式是<P.id, N.id> .P.id是文件切片名称的ID，也就是切片名字的Hash值。N.id是协作组中的节点ID，也就是节点IP地址的Hash值。切片索引项存储在切片名称关键字P.ID的后继节点中。所谓内容关键字的后继节点就是在节点空间中第一个ID大于P.id的节点。同一个视频文件中若干项不同的切片为关联内容，这些切片相对应的索引是关联索引。把相互关联索引缓存到第一个切片索引所在节点中。每个切片索引项中加上相关索引标号RaID ,RaID为第一个切片的ID。这样每个节点通过RaID就可以找到所有相关索引所在的位置。
图3–11索引的存储
例如，如图4–17所示，有三个点的协作组。文件有四个切片，首个切片的ID为3，后继节点为4，所以存储在节点4中。其它切片ID为1} 2} 4。其它三个切片的索引从节点1和2缓存到节点4中。CK3.1, CK3.2与CK3.3为ID为ID3的三个关联索引。
伪代码如图3–12所示。
图3–12索引存储过程
3–3–5) 服务区分与负载调度
内容请求被路由到服务器节点后，服务器满足服务请求。服务器节点的服务负载能力是有限的，如何分配服务资源是一个需要解决的问题。前面已经介绍，内容对象是有质量等级区分的。对不同质量等级的内容提供不同的服务。在服务器节点的服务资源分配上也是根据服务等级区分的。这里设计了基于多队列的服务资源分配机制。
在内容路由时，同一个内容会有多个副本，需要在多个副本之间做出选择。这里根据“近期忙标记数，，做副本选择。在多队列服务资源分配的基础上，根据排队论理论，控制多个队列的队长来控制排队时间。如果排队时间超过一定的时间，发出忙标记。并在内容的索引中记录忙标记信息。通过标记信息选择副本。
下面详细介绍服务区分与负载调度机制。
通过多队列管理与调度模块实现服务资源的服务区分。如图3–13所示，与之相交互的模块包括重定向系统与局域路由系统。当请求通过重定向系统或者局域路由系统达到服务器后，通过多队列模块来决定是否接受这个请求和如何分配资源。
图3–13多队列服务资源分配调度机制相关模块图
图3–14队列管理与调度
如图3–14所示，多队列服务资源分配调度机制包括以下模块:请求队列，分类模块，队列管理，子队列，资源请求调度模块，服务资源。当用户的请求来自重定位系统或者内容路由子系统，请求按先后顺序排列在请求队列中，分类模块根据内容等级把请求分配到子队列中。子队列管理系统负责对子队列的管理。根据等待时间要求来控制队长，确定请求插入子队列或者是拒绝服务。调度模块负责从各个子队列中选择请求分配服务资源。子队列管理模块通过控制队长来控制最大等待时间。内容路由时面临多副本选择，每个内容都有多个副本，统计多个副本的近期忙标记数。选择近期忙标记较低的副本作为请求的选择副本。这样就可以把请求均衡地导向服务器。
3–5–6) 内容请求路由过程
当本地服务器中没有所请求内容的时候就需要发起局域内容路由过程，把请求导向内容所在的服务器。LCRR算法请求路由过程的伪代码如图3–15所示。首先通过路由表找到内容ID的后继节点作为下一跳节点。跳到下一跳后，查找索引表，找到内容ID所对应的索引。查看索引中的RaID，如果RaID与ID相同，那么查看所有RaID与ID相等的记录，每个P.ID选择一个内容。如果RaID与ID不相同，查找路由表把RaID的后继节点作为下一跳节点，找到所有相关索引记录。经过以上步骤获得了与请求内容相关的所有内容的信息，然后把内容请求导向相应的节点。
图3–15 LCRR伪代码
3–5–7)智能调度流程
BlockCDN的节点调度分为两层:
节点选择层:通过不同的选点方式，选出所有符合的节点信息
选点方式包括:
(1) 内容调度:对指定规则的文件请求调度到指定的节点
(2) Location(区域)调度:根据工IP的location进行调度
节点筛选层:根据不同的筛选规则，将由上一层选出的节点进行筛选筛选的方式包括:
(1) 负载均衡:根据不同节点的负载信息进行筛选。
(2) 随机:在列出的节点中随机选择一个
流程图:
图3–16调度模块流程图
图3–17主要实现伪代码:
4）区块链在BlockCDN中的应用
如何在将闲置设备变成CDN缓存节点
BlockCDN是基于开源Squid，结合SDK和P2P技术开发的智能CDN节点部署软件。充分发挥了P2P和传统CDN的智能节点调度和SDK实现数据串行变并行、单路变多路，算法与协议可长期持续优化，且100%防盗链防劫持的多重优点。轻松让智能设备升级为CDN节点。BlockCDN团队充分掌握和利用分布式CDN、智能调度，分层发布、动态部署、动态防御DDOS等核心技术优势。有效的实现了互联网热门领域如：游戏下载、移动应用、视频点播、智能硬件和在线直播等的加速服务。并团队计划研发以分布CDN 节点为基础的衍生产品：云计算和云存储。
Squid开源代码如下：
https://github.com/squid-cache/squid如何运用区块链智能合约完成支付
上面的图片是操作框架。
钱包：数字钱包保持令牌（BCDN）。钱包可以在自助平台购买CDN加速量，通过输入需要加速网站和加速流量大小，流量单价。
CDN需求者：为网站，通过虚拟钱包买了自己需求的CDN服务
分享者：通过闲置的PC、路线、电视盒、手机等可以成为CDN缓存节点和为网站提供分布式加速，根据上传流量获得相应的BlockCDN代币 。
交易平台：用户可以通过第三方交易平台购买和出售BCDN。
以上图片为CDN加速采购流程。
用户可以通过交易和官网众筹获得代币BCDN并保存它在钱包。
需要加速的网站主只要将需要加速的域名和加速流量以及bcdn需要支付数量输入BlockCDN平台。
上面的图片是bcdn获得、交易过程。
节点分享者通过上传上传加速流量根据区块链智能合约获得代币BCDN，他可以将BCDN保存在钱包。也可以在第三方交易平台出售或直接出售给需要CDN的客户。
交互所有数据所涉及的记录在blockchain随时可查，绝对公平正义和防修改。
CDN需求者的网站所有者可以在自助服务平台BlockCDN发布自己网站的加速度任务和奖励，该网站的数据将被部署在全网的缓存节点并通过数据将分散的SDK来保护数据的安全性。当网站被缓存节点用户附近的用户访问时， DNS智能调度和P2P的几个节点将为用户完成访问提供服务。节点缓存部署软件通过API提供上传数据（工作量）到blockchain节点。blockchain智能合同根据工作量奖励自动支付代币BCDN给节点分享者。
总结：
BlockCDN 充分融合P2P网络在分布式文件，共享及定位等方面的优势，通过将各分享节点变成对等数据缓存库，并运用负载均衡、集群节点和服务定位等关键调度技术，使的CDN系统更灵活性、更健康、更具动态性。并BlockCDN保留了传统的Web服务器,让访问者在不用改变传统访问习惯，直接登陆Web服务器，系统会根据访问者的IP地址查找本地对应关系表，定位到相应的邻近节点服务器。由附近的节点服务器负责处理请求，并通过本地动态负载分配调度全局范围内的节点服务器进行动态负载均衡、内容分发、查找和管理从而建立完善的数据传输体系。作为自助CDN交易平台的BlockCDN通过融入区块链技术，让CDN交易更透明、更公正、价格更低廉，也又于区块链代币的支付功能让全民参与变得简单，让节点分享者收益支付更加便捷。
