一种基于价格机制的P2P文件共享网络中流量控制方法

摘要

本发明涉及一种基于价格机制的P2P文件共享网络中流量控制方法，所述方法如下：资源提供者的上传链路和资源请求者的下载链路各自初始化收取的价格；根据途经该链路的总流量调整其下一时刻的价格；资源提供者为每个资源请求者初始化下载速率；资源请求者根据其获得的总流量得到其应支付的价格；资源提供者根据资源请求者支付的价格、资源请求者的下载链路收取的价格以及资源提供者的上传链路收取的价格，调整其下一时刻为资源请求者分配的速率；链路端和用户端根据上述步骤迭代直至达到最优点，即各个用户的最优流量分配策略。本发明具有流量分配合理、算法简单准确等优点。

说明书

技术领域

本发明涉及计算机网络技术领域，尤其涉及一种对等网络P2P中文件共享网络的 流量控制方法。

背景技术

近些年，P2P网络应用获得了飞速发展，一方面丰富了互联网的内容，另一方面其 流量的爆发式增长以及对带宽不加限制的占用，给互联网基础设施带来了巨大冲击。据统 计，P2P应用业务共占所有宽带数据吞吐量的80％以上，而这其中又以P2P内容共享系统占 用网络带宽情况更为严重，常见的P2P内容共享系统包括文件下载系统Bittorrent、 eDonkey、Gnutella、搜索和检索Bearshare、内容分发、网络存储和对等广播Peercasting 等。

这些P2P内容共享系统迅猛普及和发展，它们无限制地消耗着网络带宽，占用着网 络资源，已经成为网络资源的最大消耗者，很大程度上超过了Web、E-mail、FTP等的数据流 量而成为网络的主要负担，甚至会引起网络拥塞，从而降低和影响其它业务的性能。因此， 必须对P2P网络流量进行有效的控制管理，从而实现P2P网络流量的可控和可管，改善P2P流 量带来的网络拥塞问题。

目前，在P2P流量控制方面主要还是采用基于“堵”的传统控制方式，包括限速、区 分服务、阻塞等策略，虽然一定程度上能够保障企业网内的一些关键的应用业务，节省了一 定的网络资源，但这些策略降低了P2P应用的服务质量，使得用户满意度下降，影响了一些 合理的P2P应用。为了解决上述问题，需要对流量控制技术提出新的流量控制策略，将P2P通 信流量尽量控制在内网内，从而降低运营商骨干网络的压力，在保障网络用户的满意度的 同时，提高网络性能。

发明内容

本发明目的在于提供一种流量分配合理、方法简单有效的基于价格机制的P2P文 件共享网络中流量控制方法。

为实现上述目的，采用了以下技术方案：本发明方法主要包括对等网络P2P、资源 请求者s以及资源提供者p。

在对等网络P2P中，对每个用户的接入链路进行定价，根据链路上的流量情况动态 调整链路价格，而资源提供者p在为资源请求者s提供文件下载服务时，根据资源请求者s提 供的价格和接入链路收取的价格，动态调整流量在各个资源请求者之间的合理分配，最终 实现网络的最优分配与控制；

所述控制方法的步骤如下：

步骤1，在对等网络P2P的文件共享系统中，资源提供者p的上传链路初始化收取的 价格μ_p(t)，资源请求者s的下载链路初始化收取的价格v_s(t)，资源提供者p为每一个资源请 求者s初始化下载速率x_sp(t)；

步骤2，资源请求者s根据其获得的总流量y_s(t)得到其支付的价格λ_s(t)，并通过网 络通告给其文件提供者；

步骤3，资源提供者p根据资源请求者s支付的价格λ_s(t)、资源请求者s的下载链路 初始化收取的价格v_s(t)以及资源提供者p的上传链路初始化收取的价格μ_p(t)，调整其为资 源请求者s分配的速率x_sp(t+1)；

步骤4，资源提供者p的上传链路更新其新的收取价格μ_p(t+1)；同时，资源请求者s 的下载链路更新其新的收取价格v_s(t+1)；

步骤5，资源提供者p和资源请求者s根据上述步骤迭代直至达到最优点，即各个资 源请求者s的最优流量分配策略；

步骤6，如果有新的资源提供者或资源请求者加入或者原有的资源提供者或资源 请求者退出，那么上述迭代过程重新进行以达到新的最优点。

在步骤2中，资源请求者s根据其获得的总流量y_s(t)得到其支付的价格λ_s(t)，

${\lambda }_s\left(t\right)=\frac{w_s}{max\{\xi ,y_s^{\alpha }\left(t\right)\}},y_s\left(t\right)=\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{sp}\left(t\right)$

式中，p是资源提供者；s是资源请求者；P是资源提供者集合；S是资源请求者集合； y_s(t)是资源请求者s获得的总流量；ξ是一个大于零的正数，目的是确保当总流量y_s(t)过小 时，价格λ_s(t)不至于过大；x_sp(t)是资源提供者p为每一个资源请求者s初始化的下载速率； w_s是资源请求者s愿意支付的费用；P(s)是为资源请求者s提供文件下载服务的资源提供者 集合；参数α>0是公平性指标，如若α＝1，则实现用户之间资源分配的比例公平性，若α＝2， 则实现用户之间资源分配的调和平均公平性，若α→∞，则实现用户之间资源分配的最大最 小公平性。

在步骤3中，资源提供者p调整资源请求者s分配速率x_sp(t+1)的算法如下：

$x_{sp}(t+1)={\left(\right(1-\theta \left)x_{sp}\right(t)+\theta {\tilde{x}}_{sp}(t)+{\mathrm{\kappa x}}_{sp}(t\left)\right({\lambda }_s\left(t\right)-v_s\left(t\right)-{\mu }_p\left(t\right)\left)\right)}_{x_{sp}\left(t\right)}^{+},$

${\tilde{x}}_{sp}(t+1)=(1-\theta ){\tilde{x}}_{sp}\left(t\right)+{\mathrm{\theta x}}_{sp}\left(t\right)$

式中，x_sp(t)是资源提供者p为每一个资源请求者s初始化的下载速率；θ是低通滤 波因子，且0<θ<1，能够有效消除最优点不唯一而引起的算法波动问题；是对当前速率 x_sp(t)的估值；是对资源提供者p为资源请求者s分配的速率x_sp(t+1)的估值；κ是 算法迭代步长，且κ>0；λ_s(t)是资源请求者s根据其获得的总流量y_s(t)得到其支付的价格； v_s(t)是资源请求者s的下载链路初始化收取的价格；μ_p(t)是资源提供者p的上传链路初始 化收取的价格；

$x_{sp}(t+1)={\left(\right(1-\theta \left)x_{sp}\right(t)+\theta {\tilde{x}}_{sp}(t)+{\mathrm{\kappa x}}_{sp}(t\left)\right({\lambda }_s\left(t\right)-v_s\left(t\right)-{\mu }_p\left(t\right)\left)\right)}_{x_{sp}\left(t\right)}^{+}$意味着，

若x_sp(t)>0，则$x_{sp}(t+1)=(1-\theta )x_{sp}\left(t\right)+\theta {\tilde{x}}_{sp}\left(t\right)+{\mathrm{\kappa x}}_{sp}\left(t\right)\left({\lambda }_s\right(t)-v_s(t)-{\mu }_p(t\left)\right)$

若x_sp(t)＝0，则$x_{sp}(t+1)=max\{0,(1-\theta )x_{sp}\left(t\right)+\theta {\tilde{x}}_{sp}\left(t\right)+{\mathrm{\kappa x}}_{sp}\left(t\right)\left({\lambda }_s\right(t)-v_s(t)-{\mu }_p(t\left)\right)\}.$

在步骤4中，资源提供者p的上传链路利用下述算法更新其新的收取的价格μ_p(t+ 1)

${\mu }_p(t+1)={\left({\mu }_p\right(t)+\tau (z_p\left(t\right)-C_p^u\left)\right)}_{{\mu }_p\left(t\right)}^{+},z_p\left(t\right)=\underset{s:s\in S\left(p\right)}{\Sigma }{x}_{sp}\left(t\right)$

式中，p是资源提供者；s是资源请求者；P是资源提供者集合；S是资源请求者集合； μ_p(t)是资源提供者p的上传链路初始化收取的价格；x_sp(t)是资源提供者p为每一个资源请 求者s初始化的下载速率；S(p)是接受资源提供者p提供文件下载服务的资源请求者集合； 是资源提供者p的上传链路带宽；z_p(t)是资源提供者p的上传链路为资源请求者初始化 的总上传速率；τ是算法迭代步长，且τ>0；

${\mu }_p(t+1)={\left({\mu }_p\right(t)+\tau (z_p\left(t\right)-C_p^u\left)\right)}_{{\mu }_p\left(t\right)}^{+}$意味着，

若μ_p(t)>0，则${\mu }_p(t+1)={\mu }_p\left(t\right)+\tau \left(z_p\right(t)-C_p^u)$

若μ_p(t)＝0，则${\mu }_p(t+1)=max\{0,{\mu }_p\left(t\right)+\tau \left(z_p\right(t)-C_p^u)\}.$

资源请求者s的下载链路利用下述算法更新其新的收取的价格v_s(t+1)

$v_s(t+1)={\left(v_s\right(t)+\tau (y_s\left(t\right)-C_s^d\left)\right)}_{v_s\left(t\right)}^{+},y_s\left(t\right)=\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{sp}\left(t\right)$

式中，p是资源提供者；s是资源请求者；P是资源提供者集合；S是资源请求者集合； x_sp(t)是资源提供者p为每一个资源请求者s初始化的下载速率；v_s(t)是资源请求者s的下 载链路初始化收取的价格；y_s(t)是资源请求者s获得的总流量；P(s)是为资源请求者s提供 文件下载服务的资源提供者集合；是资源请求者s的下载链路带宽；

$v_s(t+1)={\left(v_s\right(t)+\tau (y_s\left(t\right)-C_s^d\left)\right)}_{v_s\left(t\right)}^{+}$意味着，

若v_s(t)>0，则$v_s(t+1)=v_s\left(t\right)+\tau \left(y_s\right(t)-C_s^d)$

若v_s(t)＝0，则$v_s(t+1)=max\{0,v_s\left(t\right)+\tau \left(y_s\right(t)-C_s^d)\}.$

在步骤5和6中，算法迭代到达的最优点就是流量控制优化模型的全局最优点，即 对等网络中资源提供者p为每个资源请求者s分配的最优流量。

与现有技术相比，本发明具有如下优点：将流量分配与控制问题归纳为网络效用 最优化问题，通过将网络中资源提供者的上传带宽在资源请求者之间的合理分配，在保障 网络服务请求者的满意度的同时，实现网络用户之间流量的合理分配与最优控制，最终降 低运营商骨干网络的压力，保证网络的健康运行，改善P2P网络性能。

附图说明

图1是本发明方法的6个用户网络拓扑结构图。

图2是图1中资源请求者S1获得的最优流量图。

图3是图1中资源请求者S2获得的最优流量图。

图4是图1中资源请求者S3获得的最优流量图。

图5是图1中资源请求者S4获得的最优流量图。

图6是图1中各资源请求者的效用值及网络聚合效用值。

图7是图1中各资源请求者的抖动情况示意图。

图8是图1中网络波动情形下资源请求者S1获得的最优流量图。

图9是图1中网络波动情形下资源请求者S2获得的最优流量图。

图10是图1中网络波动情形下资源请求者S3获得的最优流量图。

图11是图1中网络波动情形下资源请求者S4获得的最优流量图。

附图标号：p1是资源提供者1、p2是资源提供者2、s1是资源请求者1、s2是资源请求 者2、s3是资源请求者3、s4是资源请求者4。

具体实施方式

本发明根据网络用户获得服务时的满意度选取效用函数，然后建立P2P文件共享 网络中流量控制最优化模型，即将P2P文件共享网络的流量控制问题归结为P2P文件共享网 络效用最优化模型。本发明设计一种基于价格机制的流量控制算法，该算法能够有效地收 敛到流量控制模型的最优点，即网络用户的最优流量分配。

流量控制问题描述：

P2P网络中，每个用户均是通过接入链路连接到互联网。现有互联网由于骨干网络 采取光纤通信等技术，一般认为不容易发生大规模拥塞现象，那么用户的接入链路就成了 影响用户带宽的瓶颈，也是网络流量分配与控制的关键。目前，很多用户接入互联网时采取 的是上传链路和下载链路相分离的情形，如ADSL，而一个用户在提供文件下载服务时，其上 传带宽对于其他网络用户来讲就是资源，因此用户之间对该资源的竞争就会产生。

为了区分文件共享网络中文件的提供者和请求者，引入资源提供者集合P和资源 请求者集合S。只要一个用户提供文件下载服务，那么该用户就属于P。而一个用户既可以属 于P，也可以属于S，这取决于该用户是否提供文件服务或请求文件服务。定义为资源请求者 s∈S提供文件下载服务的资源提供者集合为P(s)；资源提供者p∈P提供下载服务的所有资 源请求者集合为S(p)。注意到p∈P(s)当且仅当s∈S(p)。

若资源提供者p为资源请求者s提供的下载速率为x_sp，则由于一个用户可以从多个 资源提供者处下载同一文件，因此资源请求者s获得的总速率为而且不应 该超过该用户的下载带宽即同时，一个资源提供者还可以同时为多个用户提 供下载服务，因此该资源提供者p的上传送速率为而且不超过该用户的上 传带宽即

用户效用函数：

用户在获得服务时的满意度可以用效用函数来描述，为此选择下述效用函数，

$U_s\left(y_s\right)=\left(\begin{array}{c}{w}_s\log y_s,\alpha =1\\ w_s\frac{y_s^{1-\alpha }}{1-\alpha },\alpha \ne 1\end{array}\right)$

其中，w_s描述了资源请求者s愿意支付的费用，而参数α≥0描述了公平性指标，如 若α＝1，则实现用户之间资源分配的比例公平性，若α＝2，则实现用户之间资源分配的调和 平均公平性，若α→∞，则实现用户之间资源分配的最大最小公平性。

流量控制模型：

P2P文件共享网络的流量控制问题可以归结为如下的网络效用最优化问题

利用非线性规划理论，该效用优化问题是凸优化问题，对变量y_s是严格凹函数，存 在全局最优解而且是唯一的，但该问题对变量x_sp却不是严格的凹函数，因此 最优解并不唯一。也就是说，每个资源请求者获得的总速率是唯一的， 但是由于存在多个资源提供者，所以会存在多种具体的流量分配形式。

建立上述优化问题的拉格朗日函数

$\left(\begin{array}{c}L(x,y;\lambda ,\mu )=\underset{s:s\in S}{\Sigma }\left(U_s\right(y_s)+{\lambda }_s(\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{sp}-y_s)+v_s(C_s^d-\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{sp}-{\delta }_s^2))\\ +\underset{p:p\in P}{\Sigma }{\mu }_p(C_p^u-\underset{s:s\in S\left(p\right)}{\Sigma }{x}_{sp}-{ϵ}_p^2)\end{array}\right)$

其中λ_s≥0是资源请求者s支付的单位带宽的价格，v_s≥0是资源请求者s的下载链 路收取的单位带宽的价格，μ_p≥0是资源提供者p的上传链路收取的单位带宽的价格，和 是松弛变量，分别代表了资源请求者s的下载链路和资源提供者p的上传链路的剩余带 宽。

本发明方法主要包括对等网络P2P、资源请求者r以及资源提供者p，在对等网络 P2P中，对每个用户的接入链路进行定价，根据链路上的流量情况动态调整链路价格，而资 源提供者p在为资源请求者s提供文件下载服务时，根据资源请求者s提供的价格和接入链 路收取的价格，动态调整流量在各个资源请求者之间的合理分配，最终实现网络的最优分 配与控制；

所述控制方法的步骤如下：

步骤1，在对等网络P2P的文件共享系统中，资源提供者p的上传链路初始化收取的 价格μ_p(t)，资源请求者s的下载链路初始化收取的价格v_s(t)，资源提供者p为每一个资源请 求者s初始化下载速率x_sp(t)；

步骤2，资源请求者s根据其获得的总流量y_s(t)得到其支付的价格λ_s(t)，并通过网 络通告给其文件提供者；

${\lambda }_s\left(t\right)=\frac{w_s}{max\{\xi ,y_s^{\alpha }\left(t\right)\}},y_s\left(t\right)=\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{sp}\left(t\right)$

式中，p是资源提供者；s是资源请求者；P是资源提供者集合；S是资源请求者集合； y_s(t)是资源请求者s获得的总流量；ξ是一个大于零的正数，目的是确保当总流量y_s(t)过小 时，价格λ_s(t)不至于过大；x_sp(t)是资源提供者p为每一个资源请求者s初始化的下载速率； w_s是愿意支付的费用；P(s)是为资源请求者s提供文件下载服务的资源提供者集合；参数α> 0是公平性指标，如若α＝1，则实现用户之间资源分配的比例公平性，若α＝2，则实现用户之 间资源分配的调和平均公平性，若α→∞，则实现用户之间资源分配的最大最小公平性。

步骤3，资源提供者p根据资源请求者s支付的价格λ_s(t)、资源请求者s的下载链路 初始化收取的价格v_s(t)以及资源提供者p的上传链路初始化收取的价格μ_p(t)，调整其为资 源请求者s分配的速率x_sp(t+1)；

$\begin{array}{c}{x}_{sp}(t+1)={\left(\right(1-\theta \left)x_{sp}\right(t)+\theta {\tilde{x}}_{sp}(t)+{\mathrm{\kappa x}}_{sp}(t\left)\right({\lambda }_s\left(t\right)-v_s\left(t\right)-{\mu }_p\left(t\right)\left)\right)}_{x_{sp}\left(t\right)}^{+}\\ {\tilde{x}}_{sp}\left(t+1\right)=(1-\theta ){\tilde{x}}_{sp}\left(t\right)+{\mathrm{\theta x}}_{sp}\left(t\right)\end{array},$

式中，x_sp(t)是资源提供者p为每一个资源请求者s初始化的下载速率；θ是低通滤 波因子，且0<θ<1，能够有效消除最优点不唯一而引起的算法波动问题；是对当前速率 x_sp(t)的估值；是对资源提供者p为资源请求者s分配的速率x_sp(t+1)的估值；κ是算 法迭代步长，且κ>0；λ_s(t)是资源请求者s根据其获得的总流量y_s(t)得到其支付的价格；v_s(t)是资源请求者s的下载链路初始化收取的价格；μ_p(t)是资源提供者p的上传链路初始化 收取的价格；

$x_{sp}(t+1)={\left(\right(1-\theta \left)x_{sp}\right(t)+\theta {\tilde{x}}_{sp}(t)+{\mathrm{\kappa x}}_{sp}(t\left)\right({\lambda }_s\left(t\right)-v_s\left(t\right)-{\mu }_p\left(t\right)\left)\right)}_{x_{sp}\left(t\right)}^{+}$意味着，

若x_sp(t)>0，则$x_{sp}(t+1)=(1-\theta )x_{sp}\left(t\right)+\theta {\tilde{x}}_{sp}\left(t\right)+{\mathrm{\kappa x}}_{sp}\left(t\right)\left({\lambda }_s\right(t)-{\nu }_s\left(t\right)-{\mu }_p\left(t\right))$

若x_sp(t)＝0，则$x_{sp}(t+1)=max\{0,(1-\theta )x_{sp}\left(t\right)+\theta {\tilde{x}}_{sp}\left(t\right)+{\mathrm{\kappa x}}_{sp}\left(t\right)\left({\lambda }_s\right(t)-v_s(t)-{\mu }_p(t\left)\right)\}.$

步骤4，资源提供者p的上传链路更新其新的收取价格μ_p(t+1)；

${\mu }_p(t+1)={\left({\mu }_p\right(t)+\tau (z_p\left(t\right)-C_p^u\left)\right)}_{{\mu }_p\left(t\right)}^{+},z_p\left(t\right)=\underset{s:s\in S\left(p\right)}{\Sigma }{x}_{sp}\left(t\right)$

式中，p是资源提供者；s是资源请求者；P是资源提供者集合；S是资源请求者集合； μ_p(t)是资源提供者p的上传链路初始化收取的价格；x_sp(t)是资源提供者p为每一个资源请 求者s初始化的下载速率；S(p)是接受资源提供者p提供文件下载服务的资源请求者集合； 是资源提供者p的上传链路带宽；z_p(t)是资源提供者p的上传链路为资源请求者初始化 的总上传速率；τ是算法迭代步长，且τ>0；

${\mu }_p(t+1)={\left({\mu }_p\right(t)+\tau (z_p\left(t\right)-C_p^u\left)\right)}_{{\mu }_p\left(t\right)}^{+}$意味着，

若μ_p(t)>0，则${\mu }_p(t+1)={\mu }_p\left(t\right)+\tau \left(z_p\right(t)-C_p^u)$

若μ_p(t)＝0，则${\mu }_p(t+1)=max\{0,{\mu }_p\left(t\right)+\tau \left(z_p\right(t)-C_p^u)\}.$

资源请求者s的下载链路利用下述算法更新其新的收取的价格v_s(t+1)

$v_s(t+1)={\left(v_s\right(t)+\tau (y_s\left(t\right)-C_s^d\left)\right)}_{v_s\left(t\right)}^{+},y_s\left(t\right)=\underset{p:p\in P\left(s\right)}{\Sigma }{x}_{sp}\left(t\right)$

式中，p是资源提供者；s是资源请求者；P是资源提供者集合；S是资源请求者集合； x_sp(t)是资源提供者p为每一个资源请求者s初始化的下载速率；v_s(t)是资源请求者s的下 载链路初始化收取的价格；y_s(t)是资源请求者s获得的总流量；P(s)是为资源请求者s提供 文件下载服务的资源提供者集合；是资源请求者s的下载链路带宽；

$v_s(t+1)={\left(v_s\right(t)+\tau (y_s\left(t\right)-C_s^d\left)\right)}_{v_s\left(t\right)}^{+}$意味着，

若v_s(t)>0，则$v_s(t+1)=v_s\left(t\right)+\tau \left(y_s\right(t)-C_s^d)$

若v_s(t)＝0，则$v_s(t+1)=max\{0,v_s\left(t\right)+\tau \left(y_s\right(t)-C_s^d)\}.$

步骤5，资源提供者p和资源请求者s根据上述步骤迭代直至达到最优点，即各个资 源请求者s的最优流量分配策略；

步骤6，如果有新的资源提供者或资源请求者加入或者原有的资源提供者或资源 请求者退出，那么上述迭代过程重新进行以达到新的最优点。

收敛性分析：

收敛性是衡量算法性能的重要指标。本发明考虑了2个文件服务提供者，4个文件 服务请求者的情形，如图1所示。其中，资源提供者的上传链路带宽为 $C^u=(C_1^u,C_2^u)=(12,20)Mbps,$资源请求者的下载链路带宽为$C^d=(C_1^d,C_2^d,C_3^d,C_4^d)=(15,$$10,8,6)Mbps.$本发明分析了资源提供者的上传带宽在资源请求者之间的比例公平分配 (即α＝1)，各仿真结果如图2、3、4、5、6所示，如图2所示，资源请求者1从资源提供者处得到 的最优流量为因此，算法能够在有限的迭代次数内有效 的收敛到流量控制模型的最优点，实现流量在各个用户之间的合理分配与控制。本发明同 时考虑了P2P网络抖动(Churn)对算法的影响，抖动情况如图7所示。仿真结果如图8、9、10、 11所示，如图8所示，阶段1：t＝0→400，网络中资源请求者仅有用户1，其得到的最优流量为 阶段2：t＝401→800，资源请求者有用户1，2和3，此时资 源请求者1得到的最优流量为阶段3：t＝801→1200，资 源请求者有用户1，3和4，此时资源请求者1得到的最优流量为 不难看出即使是存在波动情况算法仍能够有效的收 敛到模型的最优点。

以上所述的实施例仅仅是对本发明的优选实施方式进行描述，并非对本发明的范 围进行限定，在不脱离本发明设计精神的前提下，本领域普通技术人员对本发明的技术方 案做出的各种变形和改进，均应落入本发明权利要求书确定的保护范围内。