一种网络gis异构集群服务器负载均衡方法
专利名称：一种网络gis异构集群服务器负载均衡方法
技术领域：
本发明属于网络空间信息服务技术领域，尤其涉及一种网络GIS异构集群服务器负载均衡方法。
背景技术：
网络GIS极大方便百姓生活的同时，也带来了巨大的访问量，如Google Earth访问量已超过I亿并与日俱增，其服务器性能成为影响其网络服务质量的关键因素之一 [1]。网络GIS中多采用异构服务器集群实现大規模网络服务，并用负载均衡技术实现多服务器之间的 负载分配，以提高网络GIS集群服务系统的整体性能[2’3]。但随着地形数据的海量增长，数据内容请求所产生的负载差异越来越大，访问局部性逐渐成为影响集群服务系统性能的另ー个重要因素[4];且地形数据具有其固有的访问流行特征，即一定时间内访问热点高度集中，访问具有爆发性，访问内容相对稳定。因而网络GIS中数据访问分布的不均衡性和异构服务器处理能力的不均衡性，是影响其集群服务系统负载不均衡的关键。如何在负载均衡策略中，综合考虑并平衡此两种不均衡因素，減少用户访问延时，加速地形数据的提取，从而提高用户在网络GIS中的漫游体验感知，是网络GIS服务质量技术中需解决的难题之一 O服务器集群及负载均衡提供了一种廉价、有效、透明的方法扩展网络系统的带宽和呑吐量。它在国内外研究已经非常广泛，基本有两类方法ー类为基于静态任务分配的负载均衡方法，如轮转方法、快速反应优先算法、目标地址散列调度和源地址散列调度算法等，该类算法只利用集群系统的平均负载信息，不考虑集群系统当前负载特征，仅适用于小规模集群系统，为静态的负载均衡；另ー类算法可合理地考虑集群系统服务器当前的负载状态并选择当前时刻最优的服务器进行请求转发，为动态负载均衡，如最少连接算法、最小负载算法及相关的变种算法。若设计合理恰当，动态负载均衡算法可以比传统的静态负载均衡算法的调度性能和效率提高30-40%左右[5]。但针对网络GIS异构集群服务系统运行行为的动态负载均衡算法研究并不多见。在此领域，Shekhar等人基于GIS中地形数据任务分割提出任务迁移的动态负载均衡算法M ;Lee等考虑了服务器的连接状态，提出基于Agent的负载分发器m ;张喜平等引入请求分配器的服务器集群技术和代理技术，实现了ー种简单动态负载均衡策略来访问访问Web GISm ;朱江等提出了基于地图内容的自适应动态反馈均衡模型，对请求的地图可视窗ロ进行分割并根据划分窗ロ的标示选择最小负载的服务器[9]。总而言之，我们观察到现有的相关工作，实质上都基于负载分配能力的提高，且都为最小负载均衡算法的优化，未考虑网络GIS中大規模用户的高度聚集访问特性和异构服务器集群的处理性能的差异。近年有研究发现，地形数据访问请求符合Zipf-Iike分布規律，即访问存在局部热点，20%的数据吸引了 80%的请求[1°’11]。现有的网络GIS服务器为了提高系统响应性能，一般缓存部分数据加速数据访问[12’13]。若基于Zipf-Iike分布规律缓存局部热点地形数据，对访问进行局部控制，在提高缓存命中率的同时考虑热点数据的访问负载均衡，可增加服务器单位时间内处理请求的数量，从而提高集群服务数据响应性能。但地形数据的访问局部性又可能导致部分服务器上负载集中，造成服务器集群系统的负载失衡。因而如何协调负载分配和访问局部性两者间的关系，使异构集群环境下每台服务器的负载尽量保持一致，获得良好的请求响应性能和较高的系统吞吐率，是理想的负载均衡策略需考虑的关键问题。文中涉及的參考文献如下[I]吴华意，章汉武.地理信息服务质量(Qo GIS):概念和研究框架[J].武汉大学学报信息科学版，2007，32 (5) =385-388.[2]喻占武，李忠民，郑胜.基于对象存储的新型网络GIS体系结构研究[J].武汉大学学报信息科学版，2008，33 (3) =285-288.[3]孟令奎，邓世军，赵春宇，等.多服务器技术在WebGIS中的应用[J].武汉大学学报信息科学版，2004，29 (9) =832-835.[4]Barish G, Obraczke K, Workd Wide Web Caching Trends and Techniques,IEEE Communications Magazine[J],2000.[5]Menasce. Trade-offs in designing web clusters[J]. IEEE InternetComputing,2002,6(5) :76-80.[6]Shekhar S,Ravada S,Chubb D,Turner G. Declustering and load-balancingmethods for parallelizinggeographic information systemslJ」· IEEE Transactionson Knowledge and Data Engineering,1998,10(4) :632-655.[7]M H Jo, Y W Jo, J S Oh, S Y Lee. Agent-Based dynamic load balancingmethod on web GIS forest fire systmLj」· Urban and Regional Information System2001,2001.[8]张喜平，汪林林.访问Web GIS服务的ー种动态负载均衡方法[J].计算机科学，2005，32 (7) :83-84.[9]朱江，张立立，曾志明，等.WebGIS服务器场的负载平衡算法设计[J]，计算机工程，2006，32 (9) :94-95.[10]王浩,潘少明，彭敏,李锐.数字地球中影像数据的Zipf-Iike访问分布及应用分析[J].武汉大学学报信息科学版，2010. 35 (3) :356-359.[ll]Fisher D. ,2007a, Hotmap Looking at geographic attention. IEEETransactions on Visualization and Computer Graphics 13(6), pp.1184-1191.[12]许卓群，汪小林，罗英伟.构件WebGIS层次模型Geo-Union空间缓存[J].计算机学报，2004，2 (2) 141.[13]李浩松，朱欣焰，李京伟，陈军.WebGIS空间数据分布式缓存技术研究[J].武汉大学学报信息科学版，2005，30 (12) =1092-1095. 138.[14] Shi L. ,Gu Z. M. ,Wei L. , Shi Y. , 2005, Quantitative Analysis of Zipf，sLaw on Web Cache[J]. Lecture Notes in Computer Science 3758:845—852.
发明内容
本发明针对网络GIS中数据访问分布和异构服务器处理能力的不均衡性所帯来集群服务系统负载不均衡的问题，提出了一种综合考虑网络GIS中访问局部性和负载分配的异构集群服务器负载均衡方法，该方法基于地形数据(瓦片)的访问符合Zipf-Iike分布规律的固有属性，能同时均衡热点数据的访问负载和异构集群服务器的负载，可有效提升网络GIS系统的服务性能，获取最优的响应时间，并提高异构集群服务系统的利用效率。为了解决上述问题，本发明采用如下的技术方案一种网络GIS异构集群服务器负载均衡方法，包括以下步骤步骤1，按访问概率高低对瓦片进行排序，并根据预设的缓存命中率，选择访问概率最高的k个瓦片，即热点瓦片，其中，k = NXh^a，N为瓦片总数；h为预设的缓存命中率；a为Zipf-Iike分布参数,0 < a≤I ;步骤2，将步骤I所得热点瓦片中访问概率高的瓦片置于异构集群服务器组S =Isi 11 ^ i 中处理能力强的服务器中，该步骤依次包括以下子步骤I)根据公式
权利要求
1.一种网络GIS异构集群服务器负载均衡方法，其特征在于，包括以下步骤 步骤1，按访问概率高低对瓦片进行排序，井根据预设的缓存命中率，选择访问概率最高的k个瓦片，即热点瓦片，其中，k = NXh171^，N为瓦片总数；h为预设的缓存命中率；α为 Zipf-Iike 分布參数，O < a ^ I ； 步骤2，将步骤I所得热点瓦片中访问概率高的瓦片置于异构集群服务器组S ={si|1≤i≤l} 中处理能力强的服务器中，该步骤依次包括以下子步骤 1)根据公式
2.根据权利要求I所述的网络GIS异构集群服务器负载均衡方法，其特征在于步骤2的子步骤3)具体为 选取异构集群服务器组S = {Si|l彡i彡L}中处理能力最強的服务器Max (Si),从标识为Tilew+1的热点瓦片开始顺次将热点瓦片及热点瓦片副本存放于服务器Max(Si)中，Tilew为最后缓存的热点瓦片标识，其初始值为Tile1，并记录当前服务器中缓存热点瓦片个数T。，确保T。彡k，至服务器Max (Si)的缓存用尽，从集群缓存服务器组中删除该服务器，循环本步骤直至异构集群缓存服务器组为空或热点瓦片及热点瓦片副本全部存放完毕。
3.根据权利要求I所述的网络GIS异构集群服务器负载均衡方法，其特征在于 步骤3的异构集群服务器负载调度模型中各服务器的服务器处理请求时间均相同，即各服务器的服务速率均相同，但采用用户请求数目为Ni来体现瓦片在服务器中所需计算资源的差异性，采用处理请求时间Ti来体现服务器对瓦片服务时间的差异。
4.根据权利要求I或3所述的网络GIS异构集群服务器负载均衡方法，其特征在于 步骤4中计算异构集群服务器的用户请求到达率均值U1, λ2，...，具体为求解异构集群服务器系统请求处理时间期望值Τ，将T描述为有约束的非线性规划数学模型，并通过罚函数法求解使T为最小值的ー组用户请求到达率均值U1, λ2，...，AJ，所述的异构集群服务器系统请求处理时间期望值
全文摘要
本发明公开一种网络GIS异构集群服务器负载均衡方法，本方法基于GIS数据访问符合Zipf分布规律的固有属性和服务器异构处理能力，从集群缓存分布上适应用户的密集访问，在提高缓存命中率的同时均衡热点数据的访问负载；从异构集群服务系统整体性能上求解数据请求服务所需的集群系统的最小处理代价，均衡异构集群服务器的负载同时最优用户访问响应时间；并基于数据请求内容进行分发处理，防止热点数据访问负载过分集中。本发明方法高度符合网络GIS中大规模用户的高度聚集访问特性，较好地协调并平衡负载分配和访问局部控制两者间的关系，保证服务效率与负载的最优化，有效地提升实际网络GIS系统的服务性能和异构集群服务系统的利用效率。
文档编号H04L29/08GK102624922SQ20121010478
公开日2012年8月1日 申请日期2012年4月11日 优先权日2012年4月11日
发明者张啸, 张银锋, 李锐 申请人:武汉大学
技术领域：
本发明属于网络空间信息服务技术领域，尤其涉及一种网络GIS异构集群服务器负载均衡方法。
背景技术：
网络GIS极大方便百姓生活的同时，也带来了巨大的访问量，如Google Earth访问量已超过I亿并与日俱增，其服务器性能成为影响其网络服务质量的关键因素之一 [1]。网络GIS中多采用异构服务器集群实现大規模网络服务，并用负载均衡技术实现多服务器之间的 负载分配，以提高网络GIS集群服务系统的整体性能[2’3]。但随着地形数据的海量增长，数据内容请求所产生的负载差异越来越大，访问局部性逐渐成为影响集群服务系统性能的另ー个重要因素[4];且地形数据具有其固有的访问流行特征，即一定时间内访问热点高度集中，访问具有爆发性，访问内容相对稳定。因而网络GIS中数据访问分布的不均衡性和异构服务器处理能力的不均衡性，是影响其集群服务系统负载不均衡的关键。如何在负载均衡策略中，综合考虑并平衡此两种不均衡因素，減少用户访问延时，加速地形数据的提取，从而提高用户在网络GIS中的漫游体验感知，是网络GIS服务质量技术中需解决的难题之一 O服务器集群及负载均衡提供了一种廉价、有效、透明的方法扩展网络系统的带宽和呑吐量。它在国内外研究已经非常广泛，基本有两类方法ー类为基于静态任务分配的负载均衡方法，如轮转方法、快速反应优先算法、目标地址散列调度和源地址散列调度算法等，该类算法只利用集群系统的平均负载信息，不考虑集群系统当前负载特征，仅适用于小规模集群系统，为静态的负载均衡；另ー类算法可合理地考虑集群系统服务器当前的负载状态并选择当前时刻最优的服务器进行请求转发，为动态负载均衡，如最少连接算法、最小负载算法及相关的变种算法。若设计合理恰当，动态负载均衡算法可以比传统的静态负载均衡算法的调度性能和效率提高30-40%左右[5]。但针对网络GIS异构集群服务系统运行行为的动态负载均衡算法研究并不多见。在此领域，Shekhar等人基于GIS中地形数据任务分割提出任务迁移的动态负载均衡算法M ;Lee等考虑了服务器的连接状态，提出基于Agent的负载分发器m ;张喜平等引入请求分配器的服务器集群技术和代理技术，实现了ー种简单动态负载均衡策略来访问访问Web GISm ;朱江等提出了基于地图内容的自适应动态反馈均衡模型，对请求的地图可视窗ロ进行分割并根据划分窗ロ的标示选择最小负载的服务器[9]。总而言之，我们观察到现有的相关工作，实质上都基于负载分配能力的提高，且都为最小负载均衡算法的优化，未考虑网络GIS中大規模用户的高度聚集访问特性和异构服务器集群的处理性能的差异。近年有研究发现，地形数据访问请求符合Zipf-Iike分布規律，即访问存在局部热点，20%的数据吸引了 80%的请求[1°’11]。现有的网络GIS服务器为了提高系统响应性能，一般缓存部分数据加速数据访问[12’13]。若基于Zipf-Iike分布规律缓存局部热点地形数据，对访问进行局部控制，在提高缓存命中率的同时考虑热点数据的访问负载均衡，可增加服务器单位时间内处理请求的数量，从而提高集群服务数据响应性能。但地形数据的访问局部性又可能导致部分服务器上负载集中，造成服务器集群系统的负载失衡。因而如何协调负载分配和访问局部性两者间的关系，使异构集群环境下每台服务器的负载尽量保持一致，获得良好的请求响应性能和较高的系统吞吐率，是理想的负载均衡策略需考虑的关键问题。文中涉及的參考文献如下[I]吴华意，章汉武.地理信息服务质量(Qo GIS):概念和研究框架[J].武汉大学学报信息科学版，2007，32 (5) =385-388.[2]喻占武，李忠民，郑胜.基于对象存储的新型网络GIS体系结构研究[J].武汉大学学报信息科学版，2008，33 (3) =285-288.[3]孟令奎，邓世军，赵春宇，等.多服务器技术在WebGIS中的应用[J].武汉大学学报信息科学版，2004，29 (9) =832-835.[4]Barish G, Obraczke K, Workd Wide Web Caching Trends and Techniques,IEEE Communications Magazine[J],2000.[5]Menasce. Trade-offs in designing web clusters[J]. IEEE InternetComputing,2002,6(5) :76-80.[6]Shekhar S,Ravada S,Chubb D,Turner G. Declustering and load-balancingmethods for parallelizinggeographic information systemslJ」· IEEE Transactionson Knowledge and Data Engineering,1998,10(4) :632-655.[7]M H Jo, Y W Jo, J S Oh, S Y Lee. Agent-Based dynamic load balancingmethod on web GIS forest fire systmLj」· Urban and Regional Information System2001,2001.[8]张喜平，汪林林.访问Web GIS服务的ー种动态负载均衡方法[J].计算机科学，2005，32 (7) :83-84.[9]朱江，张立立，曾志明，等.WebGIS服务器场的负载平衡算法设计[J]，计算机工程，2006，32 (9) :94-95.[10]王浩,潘少明，彭敏,李锐.数字地球中影像数据的Zipf-Iike访问分布及应用分析[J].武汉大学学报信息科学版，2010. 35 (3) :356-359.[ll]Fisher D. ,2007a, Hotmap Looking at geographic attention. IEEETransactions on Visualization and Computer Graphics 13(6), pp.1184-1191.[12]许卓群，汪小林，罗英伟.构件WebGIS层次模型Geo-Union空间缓存[J].计算机学报，2004，2 (2) 141.[13]李浩松，朱欣焰，李京伟，陈军.WebGIS空间数据分布式缓存技术研究[J].武汉大学学报信息科学版，2005，30 (12) =1092-1095. 138.[14] Shi L. ,Gu Z. M. ,Wei L. , Shi Y. , 2005, Quantitative Analysis of Zipf，sLaw on Web Cache[J]. Lecture Notes in Computer Science 3758:845—852.
发明内容
本发明针对网络GIS中数据访问分布和异构服务器处理能力的不均衡性所帯来集群服务系统负载不均衡的问题，提出了一种综合考虑网络GIS中访问局部性和负载分配的异构集群服务器负载均衡方法，该方法基于地形数据(瓦片)的访问符合Zipf-Iike分布规律的固有属性，能同时均衡热点数据的访问负载和异构集群服务器的负载，可有效提升网络GIS系统的服务性能，获取最优的响应时间，并提高异构集群服务系统的利用效率。为了解决上述问题，本发明采用如下的技术方案一种网络GIS异构集群服务器负载均衡方法，包括以下步骤步骤1，按访问概率高低对瓦片进行排序，并根据预设的缓存命中率，选择访问概率最高的k个瓦片，即热点瓦片，其中，k = NXh^a，N为瓦片总数；h为预设的缓存命中率；a为Zipf-Iike分布参数,0 < a≤I ;步骤2，将步骤I所得热点瓦片中访问概率高的瓦片置于异构集群服务器组S =Isi 11 ^ i 中处理能力强的服务器中，该步骤依次包括以下子步骤I)根据公式
权利要求
1.一种网络GIS异构集群服务器负载均衡方法，其特征在于，包括以下步骤 步骤1，按访问概率高低对瓦片进行排序，井根据预设的缓存命中率，选择访问概率最高的k个瓦片，即热点瓦片，其中，k = NXh171^，N为瓦片总数；h为预设的缓存命中率；α为 Zipf-Iike 分布參数，O < a ^ I ； 步骤2，将步骤I所得热点瓦片中访问概率高的瓦片置于异构集群服务器组S ={si|1≤i≤l} 中处理能力强的服务器中，该步骤依次包括以下子步骤 1)根据公式
2.根据权利要求I所述的网络GIS异构集群服务器负载均衡方法，其特征在于步骤2的子步骤3)具体为 选取异构集群服务器组S = {Si|l彡i彡L}中处理能力最強的服务器Max (Si),从标识为Tilew+1的热点瓦片开始顺次将热点瓦片及热点瓦片副本存放于服务器Max(Si)中，Tilew为最后缓存的热点瓦片标识，其初始值为Tile1，并记录当前服务器中缓存热点瓦片个数T。，确保T。彡k，至服务器Max (Si)的缓存用尽，从集群缓存服务器组中删除该服务器，循环本步骤直至异构集群缓存服务器组为空或热点瓦片及热点瓦片副本全部存放完毕。
3.根据权利要求I所述的网络GIS异构集群服务器负载均衡方法，其特征在于 步骤3的异构集群服务器负载调度模型中各服务器的服务器处理请求时间均相同，即各服务器的服务速率均相同，但采用用户请求数目为Ni来体现瓦片在服务器中所需计算资源的差异性，采用处理请求时间Ti来体现服务器对瓦片服务时间的差异。
4.根据权利要求I或3所述的网络GIS异构集群服务器负载均衡方法，其特征在于 步骤4中计算异构集群服务器的用户请求到达率均值U1, λ2，...，具体为求解异构集群服务器系统请求处理时间期望值Τ，将T描述为有约束的非线性规划数学模型，并通过罚函数法求解使T为最小值的ー组用户请求到达率均值U1, λ2，...，AJ，所述的异构集群服务器系统请求处理时间期望值
全文摘要
本发明公开一种网络GIS异构集群服务器负载均衡方法，本方法基于GIS数据访问符合Zipf分布规律的固有属性和服务器异构处理能力，从集群缓存分布上适应用户的密集访问，在提高缓存命中率的同时均衡热点数据的访问负载；从异构集群服务系统整体性能上求解数据请求服务所需的集群系统的最小处理代价，均衡异构集群服务器的负载同时最优用户访问响应时间；并基于数据请求内容进行分发处理，防止热点数据访问负载过分集中。本发明方法高度符合网络GIS中大规模用户的高度聚集访问特性，较好地协调并平衡负载分配和访问局部控制两者间的关系，保证服务效率与负载的最优化，有效地提升实际网络GIS系统的服务性能和异构集群服务系统的利用效率。
文档编号H04L29/08GK102624922SQ20121010478
公开日2012年8月1日 申请日期2012年4月11日 优先权日2012年4月11日
发明者张啸, 张银锋, 李锐 申请人:武汉大学
最新回复(0)