论文部分内容阅读
摘要：为提高网络浏览器缓存系统性能，降低用户等待时间，提出了一种基于性能约束的P2P Web Cache模型。理论分析和模拟测试表明，该模型能够减少连接时间和传输时间。
关键词：缓存系统；性能约束；P2P Web Cache；可升级；存取时间
0 引言
随着网络存取数量的飞速增长，如何提高网络的服务质量已成为研究的热点。传统的基于服务器代理的技术如Squid和Netcache，虽然易于管理和定位节点，但其集中控制性难于解决单个节点的失效或故障问题。此外，该结构忽略了在该代理中请求未果的内容是否能在其他客户端找到。本文提出了一种基于性能约束的可升级的P2P Web Cache模型。与现有的模型结构相比，该模型是可升级的，易于管理节点，最重要的是有效地降低了用户的存取时间。
1 系统拓扑结构和原理分析
1．1系统结构
系统结构包括两类节点：胖节点和瘦节点，参见图1。胖节点类似于依赖式Web Cache方法中的服务器，不过它不处理整个网络中所有节点的相关信息，而只是处理某一区域内所有节点的信息。胖节点上保存着该区域内所有节点的地址列表和节点所共享的缓存内容的索引。此外，一些常见查询的缓存内容也保存在胖节点中，这样可以加快查找速度，降低网络通信量。瘦节点类似于纯分散式网络方法中的对等点，可以和区域内的所有节点直接进行通信。当某区域内的胖节点失效时，各个瘦节点，找到离自己最近的胖节点，重新注册自己的信息到该胖节点上。这种方法可以避免单点失效。
图1 混合式Web Cache结构
胖节点可以是原有的代理服务器，或者是通过瘦节点选举产生：一种是静态产生，另一种是动态生成。所谓静态产生是指当系统中的节点增加到某一固定值时，系统指定新加入的节点为胖节点。动态生成是指，系统根据整个域内各个机器的CPU速率，内存容量及硬盘容量，推选出性能最好的机器为胖节点。动态生成的胖节点处理效率比较高。
胖节点之间的信息共享通过P2P Login Server实现，P2PLogin Server保存着整个P2P网络中所有的节点以及他们访问的所有历史网页。历史网页采用基于url的快表方式存储，查找方便高效。
1．2基本流程和模块
基本流程如下：
(1)客户节点向本区域内胖节点注册自己的信息。这些信息包括IP地址和自己的当前状态等等。
(2)客户节点发起一个请求，如果没有在本地命中，请求被转发到本区域内胖节点，胖节点搜索缓存列表，同时把请求送到P2P Login Server。
(3)如果请求命中胖节点，胖节点直接把缓存内容返回给客户节点；同时胖节点通知P2P Login Server该客户节点访问的页面。
(4)如果没有命中胖节点，而在P2P Login Server命中，P2P Login Server将命中的用户返回给客户节点。客户同时向多个节点发送请求，从响应最快的节点获取内容；或者从中挑选一个距离最近的(同一个局域网内)节点发送请求，以保证响应时间最短。同时P2P Login Server把请求该网页的用户加入到快表中。
(5)如果都没有命中，请求直接转发给server。同时P2PLogin Server在快表里增加一项以该url为键值的表项。
主要模块如下：
在瘦节点上主要运行Login、Browser Proxy和Listener两个进程，而在胖节点上主要运行一个Fat Peer进程，它在该区域内扮演服务器的角色。P2P Login Server主要运行一个server进程。
各个进程的主要功能如下：
Login：它是瘦节点和整个系统交互的接口。当瘦节点加入系统时，负责查找本区域内的Fat Peer，注册该节点的IP地址、当前状态和本地缓存内容；当瘦节点离开系统时，向Fat Peer发送请求把该节点变为离线状态。
Listener：它负责监听客户端发给它的请求，提供相应的下载服务，同时还负责向Fat Peer发送定时更新请求。
Browser Proxy：它充当传统的代理服务器，不过它运行在本地机上。当用户请求某个页面时，它截获用户的HTTP请求，首先在本地缓存里查找，命中则直接返回内容。否则同时向本区域内Fat Peer和P2P Login Server发送请求，如果在FatPeer中命中，胖节点直接把缓存内容返回给客户节点；如果在P2P Login Server命中，server把命中的节点信息(地点，主机，存在时间，类型)发送给客户端。如果都没有命中，请求被转发到源端服务器。在本地或在其他节点命中的内容应保持常新鲜度限制。此外，它还负责缓存的替换，当缓存内容发生变化时，会通知本区域内的Fat Peer更新目录。
Fat Peer：它主要负责保存当前活动节点的地址和状态，以及某些常查询的缓存内容。当某个用户查找某对象时，由于网络通信量被事先保存，因此，当缓存内容发生变化时通过Browser Proxy来更新并保存在本地节点中，Fat Peer会直接将缓存内容返回。这样可以加快查找速度，降低网络通信量。
Server：它主要负责实现胖节点之间的信息共享，构建以url为键值的快表，提供高效的查找服务，同时根据客户返回的消息，对每个url的所有用户按照优先级进行排序，提供更有效的信息。
通信管理：通信管理提供一个对网络的统一接口，提供额外的功能来保持和其他主机的持久连接，减少创建连接、拆除连接的开销，减小过多的HTTP请求引起的速度下降。它支持TCP和UDP两种通信方式。新节点加入系统时采用UDP发送组播数据查找区域内胖节点，因为UDP比TCP的速度快，且开销较低；在传输更新和缓存内容时，采用TCP通信，因为这时需要较高的可靠性。
1．3网络模型描述
为方便分析，我们把底层拓扑图描述成一个树形模型，如图2所示。用D表示胖节点和login server之间的距离，y表示login server和源端服务器之间的距离。胖节点和瘦节点之间的距离是1。
图2 缓存的存放位置
2 延迟分析
我们对混合式Web Cache系统中的延迟建立模型。总共延迟T包括三部分：To、Tc和Tt，其中To是定位时间，表示从节点发出请求到命中的节点信息或者热点缓存对象被返回的时间间隔；Tc是连接时间，表示从文档被请求到第一个数据包被返回的时间间隔；Tt表示从命中的节点或者从源端服务器到请求节点的传送时间。因此，平均延迟E[T]可表示为E[T]=E[To] +E[Tc+E[Tt]。
2．1定位时间
定位时间取决于请求节点到命中的索引服务器的距离。令t代表一跳的延迟，L代表请求节点和命中的索引服务器之间的距离，P是每个胖节点负责的瘦节点个数，Od代表在每个层次的定位时间，则E[To]可以表示为：E[To]= P(L=d)Od。两个节点之间的通信是基于TCP的，通信时间包括三次握手的延迟，搜索时间和第一个数据包的传输时间。第一个数据包可能是缓存对象的数据信息，也可能是命中的节点信息。如果请求在热点缓存对象中命中，搜索时间可以忽略不计，在胖节点和P2P login server中的搜索时间和节点成对数关系。Od可以表示为：
从这个公式可以看出，如果两个节点的缓存是完全相同的，缓存相似度为l。对于节点i来说，请求在胖节点的索引中命中的概率是Max(CacheSim(pi,pj))，l≤j≤P，j≠i。假设请求平均分布在同一区域内，那么P(L=1)=∑pMax(CacheSim(pi,pj))／P。P(L=D+1)表示请求在胖节点中的概率，因为所有没有在胖节点的热点对象和索引中命中的请求都会转发给P2P login server，P(L=D+1)可以表示为l—P(L=0)一P(L=1)。
2．2 连接时间
当节点收到响应时，如果请求在热点缓存对象中命中，它不需要连接其他节点，连接时间是0；如果它在胖节点中命中，它将会连接同一区域内的节点，距离是2。如果它在P2P loginserver中命中，它将会连接不同区域内的节点，最短的距离是4；否则它将会连接源端服务器。平均的连接时间可以表示为：(CacheSim(pi,pj))／P。P(L=D+1)表示在P2P login server中的概率，和胖节点类似，它可以用组相似度来表示：
2．3传输时间
如果请求是在热点缓存对象中命中，传输时间取决于缓存大小和线路传输率；否则请求是在胖节点索引中命中，传输时间取决于命中节点和请求节点之间的距离，他们可能在同一个区域内，也可能在不同的区域内，或者在源端服务器。平均传输时间E[Tt]可以表示为：
我们假设：(1)每一个路由器的处理能力是相同的，延迟为tr。每一个路由器采用最短路径优先策略。(2)在Intranet中每一条线路的传输延迟是相同的，我们用u1表示；在Intranet和源端服务器的线路传输速率为u2。(3)存文件的平均大小为S，而且在P2P网络中的每一个节点都不会成为瓶颈，等待时间可以忽略不计。
3 性能约束分析与模拟测试
系统采用日志驱动的模拟测试。日志总共有475685个请求，根据日志里的IP地址共有435个节点。系统是基于性能约束的，它应该满足一个重要的限制：在SPCM中的定位时间(t0)和对象获取时问(t1)之和小于直接从源端服务器获取文件的时间(t)，即t0+t1 从上面的时间模型中，可以看出t0≈7．0029+8．508log2n，其中n代表系统中所有的索引数。t1≤2．5489x+15．418，t≈23．69x+317．81，x表示文件大小单位是KB。
t0+t1＜t
(1)
7．0029+8．508log2n+2．5489x+15．418<23．69x+317．81(2)
假设x是平均缓存大小为8KB，由(2)得出，响应时间最多可以减少约471．5ms。当整个P2P系统中有235节点时，公式(1)才会成为等式。
图3显示了该模型分别在网络I／O最快(6am)、最慢(9pm)、较快及较慢情况下的降低延迟情况。图4显示了本模型与直接访问服务器相比所降低的延迟情况。通过理论分析和模拟试验，我们可以得出如下结论：该模型中定位时间和存取时间总和小于直接从原服务器访问的时间。
图4 不同情况下的延迟降低情况
4 结束语
本文提出了基于性能约束的P2P Web Cache模型，分析了这种混合式的Web Cache的性能，它所需的连接时间和传输时间比直接从源端服务器获取所需时间少。尽管这种混合式的结构会增加额外的定位时间，但这对整个延迟的影响并不大。不管是理论分析还是模拟测试都表明系统可以减少连接时间和传输时间。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：缓存系统；性能约束；P2P Web Cache；可升级；存取时间
0 引言
随着网络存取数量的飞速增长，如何提高网络的服务质量已成为研究的热点。传统的基于服务器代理的技术如Squid和Netcache，虽然易于管理和定位节点，但其集中控制性难于解决单个节点的失效或故障问题。此外，该结构忽略了在该代理中请求未果的内容是否能在其他客户端找到。本文提出了一种基于性能约束的可升级的P2P Web Cache模型。与现有的模型结构相比，该模型是可升级的，易于管理节点，最重要的是有效地降低了用户的存取时间。
1 系统拓扑结构和原理分析
1．1系统结构
系统结构包括两类节点：胖节点和瘦节点，参见图1。胖节点类似于依赖式Web Cache方法中的服务器，不过它不处理整个网络中所有节点的相关信息，而只是处理某一区域内所有节点的信息。胖节点上保存着该区域内所有节点的地址列表和节点所共享的缓存内容的索引。此外，一些常见查询的缓存内容也保存在胖节点中，这样可以加快查找速度，降低网络通信量。瘦节点类似于纯分散式网络方法中的对等点，可以和区域内的所有节点直接进行通信。当某区域内的胖节点失效时，各个瘦节点，找到离自己最近的胖节点，重新注册自己的信息到该胖节点上。这种方法可以避免单点失效。
图1 混合式Web Cache结构
胖节点可以是原有的代理服务器，或者是通过瘦节点选举产生：一种是静态产生，另一种是动态生成。所谓静态产生是指当系统中的节点增加到某一固定值时，系统指定新加入的节点为胖节点。动态生成是指，系统根据整个域内各个机器的CPU速率，内存容量及硬盘容量，推选出性能最好的机器为胖节点。动态生成的胖节点处理效率比较高。
胖节点之间的信息共享通过P2P Login Server实现，P2PLogin Server保存着整个P2P网络中所有的节点以及他们访问的所有历史网页。历史网页采用基于url的快表方式存储，查找方便高效。
1．2基本流程和模块
基本流程如下：
(1)客户节点向本区域内胖节点注册自己的信息。这些信息包括IP地址和自己的当前状态等等。
(2)客户节点发起一个请求，如果没有在本地命中，请求被转发到本区域内胖节点，胖节点搜索缓存列表，同时把请求送到P2P Login Server。
(3)如果请求命中胖节点，胖节点直接把缓存内容返回给客户节点；同时胖节点通知P2P Login Server该客户节点访问的页面。
(4)如果没有命中胖节点，而在P2P Login Server命中，P2P Login Server将命中的用户返回给客户节点。客户同时向多个节点发送请求，从响应最快的节点获取内容；或者从中挑选一个距离最近的(同一个局域网内)节点发送请求，以保证响应时间最短。同时P2P Login Server把请求该网页的用户加入到快表中。
(5)如果都没有命中，请求直接转发给server。同时P2PLogin Server在快表里增加一项以该url为键值的表项。
主要模块如下：
在瘦节点上主要运行Login、Browser Proxy和Listener两个进程，而在胖节点上主要运行一个Fat Peer进程，它在该区域内扮演服务器的角色。P2P Login Server主要运行一个server进程。
各个进程的主要功能如下：
Login：它是瘦节点和整个系统交互的接口。当瘦节点加入系统时，负责查找本区域内的Fat Peer，注册该节点的IP地址、当前状态和本地缓存内容；当瘦节点离开系统时，向Fat Peer发送请求把该节点变为离线状态。
Listener：它负责监听客户端发给它的请求，提供相应的下载服务，同时还负责向Fat Peer发送定时更新请求。
Browser Proxy：它充当传统的代理服务器，不过它运行在本地机上。当用户请求某个页面时，它截获用户的HTTP请求，首先在本地缓存里查找，命中则直接返回内容。否则同时向本区域内Fat Peer和P2P Login Server发送请求，如果在FatPeer中命中，胖节点直接把缓存内容返回给客户节点；如果在P2P Login Server命中，server把命中的节点信息(地点，主机，存在时间，类型)发送给客户端。如果都没有命中，请求被转发到源端服务器。在本地或在其他节点命中的内容应保持常新鲜度限制。此外，它还负责缓存的替换，当缓存内容发生变化时，会通知本区域内的Fat Peer更新目录。
Fat Peer：它主要负责保存当前活动节点的地址和状态，以及某些常查询的缓存内容。当某个用户查找某对象时，由于网络通信量被事先保存，因此，当缓存内容发生变化时通过Browser Proxy来更新并保存在本地节点中，Fat Peer会直接将缓存内容返回。这样可以加快查找速度，降低网络通信量。
Server：它主要负责实现胖节点之间的信息共享，构建以url为键值的快表，提供高效的查找服务，同时根据客户返回的消息，对每个url的所有用户按照优先级进行排序，提供更有效的信息。
通信管理：通信管理提供一个对网络的统一接口，提供额外的功能来保持和其他主机的持久连接，减少创建连接、拆除连接的开销，减小过多的HTTP请求引起的速度下降。它支持TCP和UDP两种通信方式。新节点加入系统时采用UDP发送组播数据查找区域内胖节点，因为UDP比TCP的速度快，且开销较低；在传输更新和缓存内容时，采用TCP通信，因为这时需要较高的可靠性。
1．3网络模型描述
为方便分析，我们把底层拓扑图描述成一个树形模型，如图2所示。用D表示胖节点和login server之间的距离，y表示login server和源端服务器之间的距离。胖节点和瘦节点之间的距离是1。
图2 缓存的存放位置
2 延迟分析
我们对混合式Web Cache系统中的延迟建立模型。总共延迟T包括三部分：To、Tc和Tt，其中To是定位时间，表示从节点发出请求到命中的节点信息或者热点缓存对象被返回的时间间隔；Tc是连接时间，表示从文档被请求到第一个数据包被返回的时间间隔；Tt表示从命中的节点或者从源端服务器到请求节点的传送时间。因此，平均延迟E[T]可表示为E[T]=E[To] +E[Tc+E[Tt]。
2．1定位时间
定位时间取决于请求节点到命中的索引服务器的距离。令t代表一跳的延迟，L代表请求节点和命中的索引服务器之间的距离，P是每个胖节点负责的瘦节点个数，Od代表在每个层次的定位时间，则E[To]可以表示为：E[To]= P(L=d)Od。两个节点之间的通信是基于TCP的，通信时间包括三次握手的延迟，搜索时间和第一个数据包的传输时间。第一个数据包可能是缓存对象的数据信息，也可能是命中的节点信息。如果请求在热点缓存对象中命中，搜索时间可以忽略不计，在胖节点和P2P login server中的搜索时间和节点成对数关系。Od可以表示为：
从这个公式可以看出，如果两个节点的缓存是完全相同的，缓存相似度为l。对于节点i来说，请求在胖节点的索引中命中的概率是Max(CacheSim(pi,pj))，l≤j≤P，j≠i。假设请求平均分布在同一区域内，那么P(L=1)=∑pMax(CacheSim(pi,pj))／P。P(L=D+1)表示请求在胖节点中的概率，因为所有没有在胖节点的热点对象和索引中命中的请求都会转发给P2P login server，P(L=D+1)可以表示为l—P(L=0)一P(L=1)。
2．2 连接时间
当节点收到响应时，如果请求在热点缓存对象中命中，它不需要连接其他节点，连接时间是0；如果它在胖节点中命中，它将会连接同一区域内的节点，距离是2。如果它在P2P loginserver中命中，它将会连接不同区域内的节点，最短的距离是4；否则它将会连接源端服务器。平均的连接时间可以表示为：(CacheSim(pi,pj))／P。P(L=D+1)表示在P2P login server中的概率，和胖节点类似，它可以用组相似度来表示：
2．3传输时间
如果请求是在热点缓存对象中命中，传输时间取决于缓存大小和线路传输率；否则请求是在胖节点索引中命中，传输时间取决于命中节点和请求节点之间的距离，他们可能在同一个区域内，也可能在不同的区域内，或者在源端服务器。平均传输时间E[Tt]可以表示为：
我们假设：(1)每一个路由器的处理能力是相同的，延迟为tr。每一个路由器采用最短路径优先策略。(2)在Intranet中每一条线路的传输延迟是相同的，我们用u1表示；在Intranet和源端服务器的线路传输速率为u2。(3)存文件的平均大小为S，而且在P2P网络中的每一个节点都不会成为瓶颈，等待时间可以忽略不计。
3 性能约束分析与模拟测试
系统采用日志驱动的模拟测试。日志总共有475685个请求，根据日志里的IP地址共有435个节点。系统是基于性能约束的，它应该满足一个重要的限制：在SPCM中的定位时间(t0)和对象获取时问(t1)之和小于直接从源端服务器获取文件的时间(t)，即t0+t1
t0+t1＜t
(1)
7．0029+8．508log2n+2．5489x+15．418<23．69x+317．81(2)
假设x是平均缓存大小为8KB，由(2)得出，响应时间最多可以减少约471．5ms。当整个P2P系统中有235节点时，公式(1)才会成为等式。
图3显示了该模型分别在网络I／O最快(6am)、最慢(9pm)、较快及较慢情况下的降低延迟情况。图4显示了本模型与直接访问服务器相比所降低的延迟情况。通过理论分析和模拟试验，我们可以得出如下结论：该模型中定位时间和存取时间总和小于直接从原服务器访问的时间。
图4 不同情况下的延迟降低情况
4 结束语
本文提出了基于性能约束的P2P Web Cache模型，分析了这种混合式的Web Cache的性能，它所需的连接时间和传输时间比直接从源端服务器获取所需时间少。尽管这种混合式的结构会增加额外的定位时间，但这对整个延迟的影响并不大。不管是理论分析还是模拟测试都表明系统可以减少连接时间和传输时间。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。