《武汉工程大学学报》 2012年12期
62-65
出版日期：2013-01-11
ISSN:1674-2869
CN:42-1779/TQ
比特洪流协议网络通信的主机分块优化算法
0引言端到端的应用(Peer to Peer, P2P) 正在逐步占据互联网业务中重要的位置.BitTorrent简称BT，是由美国软件工程师BramCohen用Python语言编写的源代码公开的P2P 软件，用于文件的分发\[14\].BT由如下几个部分组成：.torrent文件、种子提供站点、目录服务器和内容发布者/下载者.BT的基本工作原理是：首先上传者把一个文件分成若干个部分（以下用A、B、C等英文字母表示），甲在服务器随机下载了第A部分，乙在服务器随机下载了第B部分，这样甲的BT就会根据情况到乙的电脑上去取乙已经下载好的B分，乙的BT就会根据情况到甲的电脑上去取甲已经下载好的A部分，交换文件的每个计算机都可以分摊文件传输的负荷，这样不但减轻了服务器的负荷，而且加快了用户的下载速度，提高了效率\[56\].1虚拟主机的定义现实中的网络错综复杂，无论是几台计算机之间形成的小型的网络，还是各种类型的网络之间组合而形成的大型网络，BT系统总是尽可能的使种子文件的所有片段均匀的发布到网络中去\[7\]，所以在进行BT下载时就要考虑到最佳虚拟主机的查找\[5\].任何一个广域网都是由许多局域网构成的，根据局域网原理，处于同一网段下的电脑之间传输数据不仅速度快，而且不会占用主干的带宽，可以选择局域网中的一台计算机为节点作为逻辑上的唯一与外部网络连接的计算机，就可以把这台计算机称作为虚拟主机.也可以就把整个局域网看作是由虚拟主机分支出来的网络，其它的计算机只能通过虚拟主机上网\[8\].例如要从外部网络下载一个文件，可以先用虚拟主机下载，然后别的计算机再从虚拟主机上下载，这样下载的效率就会较高.所以首先要找出一台最适合做虚拟主机的计算机.同样，假设某个比较小的局域网，它们都只有一台主机与服务器相连，需要找出那台主机.例如某局域网有7台计算机，它们的连接如图1如示.图1网络连接图
Fig.1Network connection diagram2最佳虚拟主机查找从图1可以看出,3号计算机连接计算机数目最多，所以3号计算机是最佳虚拟主机.从连接矩阵上也可以清楚的识别出哪台计算机最适合做虚拟主机.图1对应的连接矩阵如下:0110000
1001000
1000111
0100000
0010000
0010000
0010000现在定义一个2维数组A\[m\]\[n\]，遍历矩阵的每一行（列），统计出每一行（列）的1的个数，个数最多的那一行（列）即为虚拟主机代表的行（列）. 第12期高峰，等：比特洪流协议网络通信的主机分块优化算法
武汉工程大学学报第34卷
算法描述如下：算法1 FindOptimumVirtualMachine输入：网络连接矩阵A\[M\]\[M\]输出：最佳虚拟主机编号步骤：（1） 定义整形数组B\[M\]存放各虚拟主机的连接数（2） 定义n记录最佳虚拟主机编号（3） 定义max记录最大连接数（4） For each element in B do（5） element = 0;（6） End for（7） For each row in A do（8） For each col in A do（9） B\[row\] = B\[row\] + A\[row\]\[col\];（10） End for（11） End for（12） n = 0;（13） max = B\[n\];（14） For each element in B do（15） if element > max then（16） max = element;（17） n = index of element;（18） End if（19） End for（20） Output n; 把上述矩阵输入进去，输出结果为3，则计算机3连接的计算机最多，所以计算机3最适合做虚拟主机.先用计算机3下载文件，然后再通过计算机3把文件传到其它计算机上,这无疑也是最快最有效的一种方法.2.1连接矩阵分块的实现与比较在大型网络中虚拟主机（对等节点）的查找和定位比较复杂，历时久，使整个网络变慢，并且随着网络规模的扩大，通过广播方式定位对等节点的方法将造成网络流量急剧增加，从而导致网络拥塞，把网络分解成若干个小型网络是一种可行的办法\[9\].约定连接计算机台数大于3的计算机为虚拟主机，和虚拟主机相连的计算机如果不是其它分块的虚拟主机那么就肯定和这台虚拟主机在同一分块内，如果是其它分块的虚拟主机就划入到其它分块，这样就能保证分块之间不会有重复。下面介绍算法： (1)通过2个循环遍历连接矩阵A\[M\]，找出那些1的个数大于3的行的下标放在一个数组\[M\]上. (2)只遍历这些以C\[i\]为行标的行，如果在这一行中的某一个元素为1，则遍历这一列元素，计算这一列的1的个数，存放在数组E\[M\]中. (3)判断数组E\[M\]的每一个元素，如果小于等于3，则相应元素能划入以上的分块.网络简化图如图2所示.图2大型网络简化图
Fig.2Large network simplified diagram图2相应的连接矩阵如下：000010000
000010000
000010000
000010000
111101000
000010111
000001000
000001000
000001000算法描叙如下：算法2 Partition输入：网络连接矩阵A\[M\]\[M\]输出：网络分块步骤：（1） 定义整形数组B\[M\]存放各虚拟主机的连接数（2） 定义整形数组E\[M\]\[M\]存放分块（3） 定义整形变量count记录每列1的个数，初始值为0（4） For each element in B do（5） element = 0;（6） End for（7） For each row in A do（8） For each col in A do（9） B\[row\] = B\[row\] + A\[row\]\[col\];（10） End for（11） End for（12） For each element in B do（13） if element > 2 then（14） 定义i = index of element（15） For each e in A\[i\] do（16） if e = 1 then（17） 定义j = column of e;（18） For each row in A do（19） Count += A\[row\]\[j\];（20） End for（21） if count < 3 then（22） E\[i\]\[j\] = 1;（23） End if（24） End if （25） End for（26） End if（27） End for（28） Output E把上述矩阵输入，输出结果如下：4：0 1 2 35：6 7 8结果表示矩阵分为两块，第一块有0，1，2，3，4，其中4为虚拟主机；第2块有5，6，7，8，其中5为虚拟主机.与预期的结果相符. 以上程序只能找到虚拟主机以及与虚拟主机相连的计算机，即第一种子，在有些情况下可能会导致分块不全，或者有的块无法分入.例子如图3所示.图3较复杂的大型网络连接图
Fig.3Complex large network simplified diagram把图3相应的连接矩阵输入得到的结果为:4：0 1 2 35：6 7 8 结果与图2的结果一样，但是图3中的9号计算机就会“落空”，不属于任何分块，把这样的计算机叫做第2种子.找到第2种子的方法为遍历每个分块矩阵的第1种子，把那些不属于其它分块的计算机划入这个分块以内，就像图3中可以把9号计算机加入5号机为虚拟主机的分块中.就可以找到第2种子，然后依此循环则能找到第3种子，第4种子…… 这样一直将全部的计算机遍历完毕，直到所有的计算机都有自己的分块.整个网络全部被划分为小的局域网.2.2算法测试测试算法：算法3 Test输入：网络连接矩阵A\[M\]\[M\]输出：最佳虚拟主机编号与邻接主机步骤：（1） 定义一个邻接链表，存放各虚拟主机之间的邻接关系（2） 将矩阵A\[M\]\[M\]转换成邻接链表表示List\[N\]，其中Link中存放了虚拟主机与其它主机之间的邻接关系.List\[N\].Link.Num表示连接主机个数.（3） 定义max记录最大连接数（4） 定义n保存最佳虚拟主机编号（5） For each element in list do（6） If List\[N\] .Link.Num > max then（7） Max=List\[N\].Link.Num（8） n=N（9） End if （10） Output List\[N\]（11） For each element in List\[N\].Link do（12） Output element（13） End for通过测试，证明算法是可行的.通过对BT网络的分块选择策略的分析，虚拟主机在网络中分布的越均匀网络性能就越好，文献\[5\]中的片段选择算法和文献\[7\]中的基于Seed的内容分发算法也是基于同样的目的提出了改进的选择算法.3结语在对BitTorrent的虚拟主机算法进行了分析后，发现虚拟主机在网络节点中分布不均，影响了下载的效率.采用主机分块算法，该算法的选择策略可以让虚拟主机在网络中较为均匀分布.并从节点的物理位置分布和平均下载时间等几个方面进行了仿真测试，结果证明加入主机分块算法的系统降低了下载时间，提供了下载的整体效率.