随着计算机网络的快速发展, 人们对各种信息、服务以及资源获取的要求变得越来越高. 传统基于C/S架构的应用由于采用的是集中式的结构, 使客户端承担着网络拥堵所产生的巨大风险. 为了改善这种问题, 研究人员提出了P2P技术, 通过Internet网络, 把加入到网络中的各个节点连接起来, 实现节点之间资源、服务和信息的共享. P2P文件共享系统中的节点不仅可以向其它节点请求文件, 也可以在本地存储文件并为其它节点提供相关服务. 从微观的角度来看, 系统中节点从其它节点获取所需文件的过程就是该节点与其它节点的交互过程. P2P文件共享系统中影响节点之间交互过程的算法有很多, 主要有节点选择算法、带宽分配算法、文件阻塞算法等.

以P2P文件共享系统和流媒体服务系统为代表的网络服务系统的流行使得P2P网络的研究工作越来越热, 针对P2P网络的研究主要包括基于实际测量流量数据和用户数据的研究方法和基于模型的研究方法. 很多学者基于实际测量的网络数据以及系统用户日志等用户数据, 对P2P文件共享系统中的用户行为特征进行分析, 建立基于用户行为的系统模型. Feng QY等人通过分析MAZE系统的用户日志, 对加入系统中用户节点的重下载、文件审查、文件删除以及搭便车行为进行建模, 并分析了用户节点行为特征的统计规律^[1]. 山秀明等人以P2P文件共享系统中用户节点所拥有的共享文件数量为主要参数, 建立了用户共享行为的复杂网络演化模型, 研究了P2P网络中不同的用户节点在文件共享行为上的差异^[2]. 还有一些学者通过对系统演化过程的分析, 建立系统的数学模型, 进而对系统的演化规律进行研究. Qiu DY等人提出了一个BT系统的流体模型, 从宏观角度分析系统中节点数目的演化过程和不同因素对系统的影响, 但没有考虑系统中各个节点状态的变化^[3]. Yin BQ等人提出了一个P2P媒体分发网络的动力学模型, 并且分析了节点选择算法和带宽分配算法对系统的影响^[4,5]. 不同于文献[3], 文献[4,5]是从微观角度对P2P文件共享系统进行研究的.

这些研究工作大多是对系统中用户日志和网络测量数据进行总结, 分析用户行为的统计规律, 建立系统的用户行为模型; 或通过对系统演化过程进行分析, 建立系统的动力学模型, 并没有将用户行为的统计规律和系统演化统一起来, 因此研究结果的适应性较差. 实际上, 系统中用户行为和系统演化过程是交互影响、不可分割的整体, 应该将两者统一起来进行研究. 本文将系统中用户行为的统计规律和P2P文件共享系统的结构以及相关的算法结合起来研究, 提出了一种基于在线概率的动力学模型来研究P2P文件共享系统的演化过程.

由于系统中用户行为的随机性以及其它的随机因素的影响, 节点加入和退出网络的行为同样是随机的, 为了更好地刻画节点行为的随机性, 本文引入了节点的在线概率, 然后, 从微观的角度研究了系统中节点之间文件的传输过程, 并以节点待发送的数据量为状态变量, 建立了基于在线概率的动力学模型. 在此基础上, 分析了节点选择算法、带宽分配算法与节点阻塞算法的具体形式, 并对算法进行改进, 提出了基于在线概率的节点选择算法、带宽分配算法与节点阻塞算法. 最后通过仿真实验对模型的正确性进行了验证, 并分析了在线概率对系统演化过程的影响.

1 动力学模型

系统中节点通过P2P文件共享系统向其它节点发起文件下载请求. 其它节点在收到该节点发出的请求之后, 根据既定的策略为其分配上传带宽. 系统中每个节点从其它节点下载所需文件的同时也为这些节点分配上传带宽.

为了增加模型的拓展性, 简化研究工作, 我们对系统做了一些必要的假设: 节点上线和下线的流量变化过程持续的时间可以忽略不计; 系统下载带宽远大于上传带宽, 也就是影响节点下载速度的瓶颈为节点的上传带宽; 忽略节点之间握手信息的流量以及时间延迟. 模型中定义了以下参数:

N表示系统中在线的用户节点数目. 由于我们引入了在线概率, 所以系统的拓扑结构是稳定的;

${p_i}(t)$ 表示t时刻系统中用户节点i的在线概率, 其中, $0 \le {p_i}(t) \le 1$ ;

${x_i}(t)$ 表示t时刻节点i收到请求但还没有发送出去的数据量, 为t时刻节点i的状态量;

M表示系统中文件片的数目;

c_i表示节点i的上传带宽;

D_m表示编号为m的文件片的大小;

${p_{mi}}(t)$ 表示t时刻节点i是否拥有第m个文件片, 当节点i存储第m个文件片时, ${p_{mi}}(t)$ =1, 否则 ${p_{mi}}(t)$ =0;

$P(t)$ 表示t时刻系统的文件存储矩阵, 其中, $P(t) = [{p_{mi}}(t)]$ ;

${q_{ij}}(t)$ 表示t时刻系统中节点i和节点j之间的连接关系. 当节点j向节点i发出下载请求, 并且节点i还没有发完节点j请求的文件时, ${q_{ij}}(t)$ =1; 当节点i已经将节点j请求的数据发送完成或者节点j没有向节点i发出下载请求时, ${q_{ij}}(t)$ =0;

$Q(t)$ 表示t时刻系统中节点之间的连接关系矩阵, $Q(t) = [{{\rm{q}}_{ij}}(t)]$ ;

${N_{cap}}$ 表示系统中每个节点最多可以服务的节点数目;

${N_{{\rm{req}}}}$ 表示单个节点单位时间内可以向其它节点请求的文件片的最大数目.

下面介绍基于在线概率的P2P网络系统的一般模型.

函数 ${f_{ij}}({x_1},\cdots,{x_n},Q,{p_i},{c_i})$ 表示t时刻节点i分配给节点j的上传带宽, 反映了节点的带宽分配算法;

函数 ${k_{ij}}({x_1},\cdots,{x_n},Q)$ 表示t时刻节点i对来自节点j的文件下载请求的态度, 如果节点i不想为节点j分配上传带宽, 则会拒绝来自节点j的文件下载请求, 反映的是节点阻塞算法;

函数 ${\alpha _{im}}(P,{N_{{\rm{req}}}})$ 表示t时刻节点i对文件片m的请求情况;

函数 $h_m^{ij}({x_1},\cdots,{x_n},{\alpha _{im}}(P,{N_{req}}),{p_j})$ 表示t时刻节点i向节点j发出的关于文件片m的文件下载请求, 反映了节点选择算法;

函数 ${f_{ij}}({x_1},\cdots,{x_n},Q,{p_i},{c_i}) \times {k_{ij}}({x_1},\cdots,{x_n},Q)$ 表示在考虑节点阻塞算法的情况下, t时刻节点i分配给节点j的上传带宽;

函数 $\sum\limits_{j = 1,j \ne i}^N {{f_{ij}}({x_1},\cdots,{x_n},Q,{p_i},{c_i}) \times {k_{ij}}({x_1},\cdots,{x_n},Q)} $ 表示在考虑节点阻塞算法的情况下, t时刻节点i分配给系统中其它节点的总上传带宽, 是 ${x_i}(t)$ 的减少率.

函数 $\sum\limits_{m = 1}^M {\sum\limits_{j = 1,j \ne i}^N {h_m^{ij}} } ({x_1},\cdots,{x_n},{\alpha _{im}}(P,{N_{req}}),{p_j}) \times {D_m}$ 表示t时刻节点i收到的其它节点请求的下载文件量, 是状态 ${x_i}(t)$ 的增加率.

通过以上的分析, 我们得到系统动力学模型微分方程的一般形式为:

$\begin{aligned}\frac{{d{x_i}}}{{dt}} & = \sum\limits_{m = 1}^M {\sum\limits_{j = 1,j \ne i}^N {h_m^{ij}({x_1},\cdots,{x_n},{\alpha _{im}}(P,{N_{req}}){p_j}) \times {D_m}} } - \\& \quad \sum\limits_{j = 1,j \ne i}^N {{f_{ij}}({x_1},...,{x_n},Q,{p_i},{c_i}) \times {k_{ij}}({x_1},\cdots,{x_n},Q)} \end{aligned}$

(1)

通过上述方程可以知道节点的状态演变过程是由节点的带宽分配算法、节点选择算法、节点阻塞算法共同决定的. 当我们确定了这些算法的具体形式, 我们就得到了动力学方程的具体形式. 然后通过对得到的具体的动力学模型进行实验仿真, 就可以分析P2P文件系统中相关参数的演变, 验证系统模型的正确性.

2 模型分析

根据上面的讨论, 我们得到了基于在线概率的P2P网络系统动力学模型的一般形式, 下面我们将根据具体的算法, 对P2P文件共享系统进行分析, 并给出基于在线概率的改进算法.

2.1 带宽分配算法

带宽分配算法就是源节点将上传带宽按照某种策略分配给那些向它请求文件的节点.

2.1.1 基准算法

一种简单地带宽分配算法就是将源节点的上传带宽平均分配给所有向该节点发出文件请求的节点. 此时, 我们得到等概率的带宽分配算法的表达式如式(2).

${f_{ij}}({x_1},\cdots,{x_N},Q,{c_i},{p_j}) = \left\{ {\begin{array}{*{20}{c}}{\frac{{{q_{ij}}{c_i}}}{{\sum\limits_{n = 1,n \ne i}^N {{q_{in}}} }},\sum\limits_{n = 1,n \ne i}^N {{q_{in}} > 0,} }\\{0,\sum\limits_{n = 1,n \ne i}^N {{q_{in}} = 0.} }\end{array}} \right.$

(2)

其中, $\sum\limits_{n = 1,n \ne i}^N {{q_{in}}} $ 表示向源节点i发出文件请求但是还没有获取到所请求的文件片的用户节点数.

2.1.2 改进算法

我们考虑节点行为的随机性, 不同的用户节点的在线概率是不同的. 在线概率越大的用户节点应该分得更多的上传带宽. 此时, 我们得到基于在线概率的带宽分配算法的表达式如式(3).

${f_{ij}}({x_1},\cdots,{x_N},Q,{c_i},{p_j}) = \left\{ {\begin{array}{*{20}{c}}{\frac{{{q_{ij}}{p_j}{c_i}}}{{\sum\limits_{n = 1,n \ne i}^N {{q_{in}}{p_j}} }},\sum\limits_{n = 1,n \ne i}^N {{q_{in}} > 0} }\\{0,\sum\limits_{n = 1,n \ne i}^N {{q_{in}} = 0}}\end{array}} \right.$

(3)

2.2 节点阻塞算法

节点阻塞算法就是当向源节点发出文件请求的用户节点数超出源节点服务能力的时候, 源节点将按照某种策略为其中部分节点提供服务, 拒绝其它节点所发出的文件下载请求.

2.2.1 基准算法

一种简单的节点阻塞算法是每个发出请求的节点都有相同的概率获得源节点提供的服务. 此时, 我们得到等概率的节点阻塞算法的表达式如式(4).

${k_{ij}}({x_1},\cdots,{x_n},Q) = \left\{ {\begin{array}{*{20}{c}}{\frac{{{q_{ij}}{N_{\rm{cap}}}}}{{\sum\limits_{n = 1,n \ne i}^N {{q_{in}}} }},\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {{q_{in}} > {N_{\rm{cap}}}} }\\{{q_{ij,}}\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {q{}_{in} \le {N_{\rm{cap}}}} }\end{array}} \right.$

(4)

2.2.2 改进算法

我们考虑节点行为的随机性, 源节点会对那些对自己价值更大的节点也就是在线概率大的节点更加积极, 会优先满足这些节点的文件请求, 而对于那些对自己价值小的节点, 则会拒绝为其分配上传带宽. 此时, 我们得到基于在线概率的节点阻塞算法的表达式如式(5).

${k_{ij}}({x_1},\cdots,{x_n},Q) = \left\{ {\begin{array}{*{20}{c}}{\frac{{{q_{ij}}{N_{\rm{cap}}}{p_j}}}{{\sum\limits_{n = 1,n \ne i}^N {{q_{in}}{p_j}} }},\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {{q_{in}} > {N_{\rm{cap}}}} }\\{{q_{ij,}}\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {q_{in} \le {N_{\rm{cap}}}} }\end{array}} \right.$

(5)

2.3 节点选择算法

节点选择算法就是节点会根据服务器所返回的拥有所需文件片的节点列表, 按照某种策略选择源节点发出文件片下载请求.

2.3.1 基准算法

一种简单地节点选择算法就是有文件片下载需求的节点以相同的概率向返回列表中的所有节点发出文件请求. 此时, 我们得到等概率的节点选择算法的表达式如式(6).

$\begin{aligned}& h_m^{ij}({x_1},\cdots,{x_n},{\alpha _{im}}(P,{N_{\rm{req}}}),{p_j}) = \\& \qquad \left\{ {\begin{array}{*{20}{c}}{\frac{{{p_{mi}}{\alpha _{im}}(P,{N_{\rm{req}}})}}{{\sum\limits_{n = 1,n \ne i}^N {{p_{mn}}} }},\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {{p_{mn}} > 0,} }\\{0,\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {{p_{mn}} = 0.} }\end{array}} \right.\end{aligned}$

(6)

2.3.2 改进算法

节点在选择源节点时会优先选择在线概率大的节点作为文件服务的提供者, 这样可以减少因源节点在文件传输过程中退出系统而导致传输中断, 减少用户节点重新向其它节点发起文件请求所引起的网络抖动. 此时, 我们得到基于在线概率的节点选择算法的表达式如式(7).

$\begin{aligned}& h_m^{ij}({x_1},\cdots,{x_n},{\alpha _{im}}(P,{N_{\rm{req}}}),{p_j}) = \\& \qquad \left\{ {\begin{array}{*{20}{c}}{\frac{{{p_{mi}}{\alpha _{im}}(P(t),{N_{\rm{req}}}){p_i}}}{{\sum\limits_{n = 1,n \ne i}^N {{p_{mn}}} }},\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {{p_{mn}} > 0,} }\\{0,\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {{p_{mn}} = 0.} }\end{array}} \right.\end{aligned}$

(7)

根据文献[6]中提出的同ISP节点优先选择算法, 我们对上述算法做出改进, 此时, 算法的表达式如式(8).

$\begin{aligned}& h_m^{ij}({x_1},\cdots,{x_n},{\alpha _{im}}(P,{N_{\rm{req}}}),{p_j}) = \\& \quad \left\{ {\begin{array}{l}{\frac{{{p_{mj}}{\alpha _{im}}(P,{N_{\rm{req}}}){p_j}I(i,j)}}{{\sum\limits_{n = 1,n \ne i}^N {{p_{mn}}{p_i}I(i,j)} }},\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {I(i,n){p_{mn}} > 0,} }\\{\frac{{{p_{mj}}{p_j}{\alpha _{im}}(P,{N_{\rm{req}}})}}{{\sum\limits_{n = 1,n \ne i}^N {{p_{mn}}{p_j}} }},\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {I(i,n){p_{mn}} = 0,\sum\limits_{n = 1,n \ne i}^N {{p_{mn}} \ne 0,} } }\\[3pt]{0,\;\;\;\;\sum\limits_{n = 1,n \ne i}^N {I(i,n){p_{mn}} = 0,\sum\limits_{n = 1,n \ne i}^N {{p_{mn}} = 0.} } }\end{array}} \right.\end{aligned}$

(8)

其中, $I(i,j) = 1$ 表示两节点处于同一个ISP网络中, $I(i,j) = 0$ 表示两个节点不处于同一个ISP网络中.

3 实验及分析

本节通过两组仿真对基于节点在线概率的动力学模型进行分析. 首先对采用等概率算法的动力学模型和在线概率算法的动力学模型进行仿真, 通过对比节点状态演化曲线来验证基于在线概率的动力学模型正确性. 然后对在线概率服从不同正态分布的系统动力学模型进行仿真, 分析在线概率变化对系统演化过程的影响.

3.1 模型验证

假设系统拥有10个节点, 分别用PN1,…, PN10来表示; 系统中有30个文件片, 我们把这30个文件片均存储在PN1上; 文件片的大小为20 KB; 节点的上传带宽均为100 KB/s; 我们规定, 每个节点每时刻只能向其它节点请求2个文件片. 实验一中采用等概率的算法, 实验二中采用基于在线概率的算法, 并且节点的在线概率服从正态分布N(0, 0.81), 实验中采用的算法如表1所示.

如图1所示, 实验一中PN1的文件传输过程在16 s之前就已经结束了, 其余节点的文件传输也均在16 s之前完成(见图2及图3). 从图4至图6中可以看出, 在基于在线概率算法的动力学模型中, 节点PN1的文件传输过程一直持续到仿真结束. 节点PN2在仿真时间内没有完成文件的传输. 因为实验一中各节点是一直处于在线状态的, 也就是节点的在线概率均为1, 而实验二中各节点的在线概率是满足正态分布的随机数, 均小于1. 所以, 与实验一相比, 实验二中的节点完成文件传输所需的时间更长. 对比实验一和实验二中对应状态的演化曲线, 可以看出与实验一相比, 实验二中相应节点的状态演化曲线抖动更厉害. 这是由于实验二是基于在线概率的算法进行文件传输的, 当系统中某一节点的在线概率较小时, 该节点在线的时间就比较短, 在该节点在线状态结束后, 向其发出文件片请求的节点需要

重新寻找新的节点发起文件请求, 这导致基于在线概率的动力学模型中各节点的状态演化曲线抖动更厉害, 从而我们验证了基于在线概率动力学模型的正确性.

3.2 在线概率对系统演化的影响

在上面仿真的基础上, 我们通过对系统中节点在线概率服从不同正态分布所对应的动力学模型进行仿真, 得到文件传输过程中各节点的状态演化曲线, 通过对比得到的节点状态演化曲线, 分析在线概率大小对系统文件传输过程的影响.

假设实验三中系统节点的在线概率服从正态分布N(0, 0.64), 其余参数同实验二. 仿真结果如图7至图9所示. 从图7至图9中可以看出, 实验三中节点PN1, PN2, PN3, 在仿真时间内均没有完成文件的传输. 对比实验二和实验三中对应节点的状态演化曲线, 可以看出实验二中曲线的抖动频次更大, 因为实验二和实验三相比, 系统中节点的在线概率更小, 节点的在线时长更短, 系统中节点重新向其它节点发起文件请求的频率更高, 系统中文件传输过程持续的时间更长.

在文件传输的过程中, 节点在线概率越小, 那么向这个节点发出文件请求的节点需要更换源节点的概率越大, 对应的节点状态演化曲线的抖动越厉害, 完成文件传输所需的时间越长.

4 结语

本文将P2P文件共享系统中用户行为的统计规律和系统的结构结合起来分析, 并引入在线概率, 建立了基于在线概率的动力学模型. 该模型很好的刻画了系统中节点行为的随机性, 对实际环境的描述更加准确, 更加接近实际系统. 本文对系统的节点选择算法、带宽分配算法以及节点阻塞算法进行研究, 并提出了基于在线概率的节点选择算法、带宽分配算法以及节点阻塞算法. 最后通过仿真实验, 验证了基于在线概率动力学模型的正确性, 并对比分析了在线概率大小对系统演化过程的影响. 该模型为研究P2P系统提供了一个更为有效的方法.