一种大数据环境下基于树形网络和数据分块的锁步分发方法

摘要

树形网络的大数据分发技术，通过把大数据进行分块和按序编号，并搭建高度最小的最优树形网络结构，使大数据文件在网络中的数据分发能以流水线的形式进行，从而在很大程度上减少了数据分发延迟和计算开销，同时，这种方法还能为数据在树形网络中的传输时间进行预测。在本发明中提出了一种大数据在树形网络中锁步分发的方法，通过找出一个固定的、所有节点都一样的上传速率让整个数据分发时间变得最小，同时提出一种新的通过采用流水线技术和降低树形网络的高度来提高数据分发速率的方法，极大地降低了大数据在树形网络的数据分发的开销。

说明书

技术领域

本发明涉及网络中的数据分发，特别是树形网络中的大数据分块分发。

背景技术

大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合，是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。大数据具有5V特点(IBM提出)，分别是Volume(大量)、Velocity(高速)、Variety(多样)、Value(低价值密度)、Veracity(真实性)。

树形网络：如图1所示：树形网络是由多个层次的星型结构纵向连接而成，树的每个节点都是计算机或转接设备。一般来说，越靠近树的根部，节点设备的性能就越好。与星型网络相比，树形网络总长度短，成本较低，节点易于扩充，但是树形网络复杂，与节点相连的链路由故障时，对整个网络的影响较大。

数据分块：由于数据文件比较大，传输延时也很大，而且一旦发生错误，将导致文件重新发送，不利于传输；因此，要对数据文件进行按序分块，即使发送出错，也能根据序号选择数据块重新发送和数据拼接。

锁步：CPU的锁步模式就是指锁定CPU内存频率一致，防止异步频率导致的蓝屏死机；在这里指的是树形网络中，使每一层节点对子节点的数据传输时间、速率保持一致。

发明内容

本发明的目的是提供一种大数据在树形网络中锁步分发的方法，即找出一个固定的、所有节点都一样的上传速率让整个数据分发时间变得最小，同时提出一种新的通过采用流水线技术和降低树形网络的高度来提高数据分发速率的方法，极大地降低了系统的开销。

具体思路是：由于参与数据分发操作的节点以及节点的上传能力都是已经确定的，那么所有节点都采用的固定上传速率r的大小就会影响到这个树形网络的高度，同时以流水线的方式把分好块的数据在树形网络高度最小的情况下进行分发，这样就能让数据分发的完成时间变得最小。所以，我们的目标就是找到让数据分发完成时间最小的那个上传速率r。

具体方法按照以下6个步骤实施：

1.初始化：把参与分发数据的所有n个节点的上传能力(单位kbps)集合{c₁,c₂,...,c_n}作为输入，并按由高到低的顺序进行排序。其中c_i为第i个节点的上传能力。

2.固定的上传速率r(图2和3：算法一、二)：在树形网络中，第i个节点以c_i的上传能力和相同的上传速率r给它的子节点们发送数据，那么r的最小值在只有两层节点的情况下取得，即r的最大值为其中l为叶子节点个数。所以r的取值范围但此时的r的取值范围是连续的，由于树中所有节点的出度k(1≤k≤n-1)都是正整数，那么根据(遍历c和k)和r的取值范围，便可以把r离散化，得到有限个r的取值。同时，由于不考虑节点所处的位置而只考虑完成时间，则可以对集合{c₁,c₂,...,c_n}中相同的值进行合并去重，不必把每个c都进行计算，从而减少计算量。

3.树的高度h：在步骤1中，节点已经按照上传能力由大到小排序，把上传能力最大的节点作为根节点，次之作为根节点的最左边的节点，由左至右，以此类推。这样节点的出度也从根节点往下递减，树的高度也会变得最小。当只有两层节点的时候，树的高度h最小为1；h的最大值为

4.数据按序分块：把大数据文件进行分块，数据块大小为B，并编上序号。这样，即使数据传输出错，也能等下一次重新发送时进行数据拼接，而不用重新发送这个数据文件，减少了传输时延。

5.建立树形网络(图3：算法三)：根据步骤2和步骤3得出的r和h的取值范围，我们可以遍历r和h，找到使完成时间D(即每一层的用时是一共h层)最小的那个r的取值。以集合中第一个节点作为根节点，接下来的k1个节点作为它的子节点(k1为根节点的出度)，依次类推，直到所有节点都加到树中。

6.流水线分发：在根节点中，把分好块、排好序的数据文件进行分发，这样，就能以流水线的方式把数据以最快的速度分发给树中每一个非根节点。

附图说明

图1是算法所适用的树形网络。

图2是算法一流程图。

图3是算法二流程图。

图4是算法三流程图。

图5是本申请实施例建立的树形图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。

实施例

给出节点上传能力降序集合{3,3,2,2,2,1,1,1,1,1}，按照上述方法，树形网络的高度h范围为[1,8]，r的取值范围为[3/9,10/9]，因为出度k是整数，取值范围为[1,9]，所以我们可以把r离散化(r＝c/k)，得r的取值范围为{1/9,1/8,1/7,1/6,1/5,1/4,1/3,1/2,1,2/9,2/7,2/5,2/3,2,3/8,3/7,3/5,3/4,3/2,3}，由h和r的取值范围，遍历r和h，找到使完成时间D(即每一层的用时是一共h层)最小的那个r的取值,假设B＝1，最后可以得出r^*＝1，h＝2，建立如图5所示的树形网络。这样就让树形网络变得更加紧凑，数据分发时间也变得最小。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。