基于图多层K路划分的仿真节点映射策略

为了提高网络仿真系统中,多物理服务器情况下,服务器资源的利用率,提出一种基于图多层K路划分的仿真节点映射策略。首先对仿真网络拓扑图进行多层K路划分,将节点映射问题转化为图划分问题,然后依据划分结果将仿真节点映射到物理服务器。经过试验表明,相对于随机映射策略,该策略在保证物理服务器负载均衡的同时,可以有效减少物理服务器资源的消耗。     

Blockchain Based Consensus Algorithm and Trustworthy Evaluation of Authenticated Subgraph Queries

Over the past era, subgraph mining from a large collection of graph database is a crucial problem. In addition, scalability is another big problem due to insufficient storage. There are several security challenges associated with subgraph mining in today’s on-demand system. To address this downside, our proposed work introduces a Blockchain-based Consensus algorithm for Authenticated query search in the Large-Scale Dynamic Graphs (BCCA-LSDG). The two-fold process is handled in the proposed BCCA-LSDG: graph indexing and authenticated query search (query processing). A blockchain-based reputation system is meant to maintain the trust blockchain and cloud server of the proposed architecture. To resolve the issues and provide safe big data transmission, the proposed technique also combines blockchain with a consensus algorithm architecture. Security of the big data is ensured by dividing the BC network into distinct networks, each with a restricted number of allowed entities, data kept in the cloud gate server, and data analysis in the blockchain. The consensus algorithm is crucial for maintaining the speed, performance and security of the blockchain. Then Dual Similarity based MapReduce helps in mapping and reducing the relevant subgraphs with the use of optimal feature sets. Finally, the graph index refinement process is undertaken to improve the query results. Concerning query error, fuzzy logic is used to refine the index of the graph dynamically. The proposed technique outperforms advanced methodologies in both blockchain and non-blockchain systems, and the combination of blockchain and subgraph provides a secure communication platform, according to the findings.     

Single-Row Transformation of Complete Graphs

A complete graph is a fully-connected graph where every node is adjacent to all other nodes in the graph. Very often, many applications in science and engineering are reducible to this type of graph. Hence, a simplified form of a complete graph contributes in providing the solutions to these problems. In this paper, we present a technique for transforming a complete graph into a single-row routing problem. Single-row routing is a classical technique in the VLSI design that is known to be NP-complete. We solved this problem earlier using a method called ESSR, and, the same technique is applied to the present work to transform a complete graph into its single-row routing representation. A parallel computing model is proposed which contributes in making the problem modular and scalable. We also discuss the application of this work on the channel assignment problem in the wireless cellular telephone networks.     

基于图核的异质信息网络链路预测方法

链路预测是图挖掘主要研究的问题,其研究重点是提取图的特征信息,现有研究方法大多只关注网络拓扑结构而忽略了节点属性信息.针对该问题,提出了基于图核的链路预测方法NGLP.该方法能挖掘有效、可用的元路径;基于元路径对预测对象生成带节点属性的子图,使用子图表示被预测的链路;然后利用图核方法计算子图之间的相似性;最后训练SVM得出链路预测结果.实验结果表明,提出方法与其他方法相比具有更高的精度和更强的稳定性.     

An SSL Back-End Forwarding Scheme in Cluster-Based Web Servers

State-of-the-art cluster-based data centers consisting of three tiers (Web server, application server, and database server) are being used to host complex Web services such as e-commerce applications. The application server handles dynamic and sensitive Web contents that need protection from eavesdropping, tampering, and forgery. Although the secure sockets layer (SSL) is the most popular protocol to provide a secure channel between a client and a cluster-based network server, its high overhead degrades the server performance considerably and, thus, affects the server scalability. Therefore, improving the performance of SSL-enabled network servers is critical for designing scalable and high-performance data centers. In this paper, we examine the impact of SSL offering and SSL-session-aware distribution in cluster-based network servers. We propose a back-end forwarding scheme, called ssl_with_bf, that employs a low-overhead user-level communication mechanism like virtual interface architecture (VIA) to achieve a good load balance among server nodes. We compare three distribution models for network servers, round robin (RR), ssl_with_session, and ssl_with_bf, through simulation. The experimental results with 16-node and 32-node cluster configurations show that, although the session reuse of ssl_with_session is critical to improve the performance of application servers, the proposed back-end forwarding scheme can further enhance the performance due to better load balancing. The ssl_with_bf scheme can minimize the average latency by about 40 percent and improve throughput across a variety of workloads.     

高连通子图的贪心挖掘算法

利用海量的生物网络数据发现功能模块越来越受到人们的重视,从蛋白质建模的网络图中挖掘高连通子图是其中一个很重要的问题,然而由于数据规模巨大,现有的算法在时间效率上无法胜任实际的应用需求。通过深入研究高连通图的性质定理,设计了一个高连通子图的贪心挖掘算法（HCSGM）算法,在时间复杂度上比HCS算法提高了一个数量级。实验结果表明,HCSGM算法在仿真数据上的挖掘结果优于HCS算法,并且能够从大规模网络图中快速地进行高连通子图挖掘,从而高效地从蛋白质相互作用数据库中挖掘出功能模块。     

Optimal server allocations for streaming multimedia applications on the Internet

In this paper, we address the server selection problem for streaming applications on the Internet. The architecture we consider is similar to the content distribution networks consisting of geographically dispersed servers and user populations over an interconnected set of metropolitan areas. Server selection issues for Web-based applications in such an environment have been widely addressed; the selection is mostly based on proximity measured using packet delay. Such a greedy or heuristic approach to server selection will not address the capacity planning problem evident in multimedia applications. For such applications, admission control becomes an essential part of their design to maintain Quality of Service (QoS). Our objective in providing a solution to the server selection problem is threefold: first, to direct clients to the nearest server; second, to provide multiple sources to diffuse network load; third, to match server capacity to user demand so that optimal blocking performance can be expected. We accomplish all three objectives by using a special type of Linear Programming (LP) formulation called the Transportation Problem (TP). The objective function in the TP is to minimize the cost of serving a video request from user population x using server y as measured by network distance. The optimal allocation between servers and user populations from TP results in server clusters, the aggregated capacity of each cluster designed to meet the demands of its designated user population. Within a server cluster, we propose streaming protocols for request handling that will result in a balanced load. We implement threshold-based admission control in individual servers within a cluster to enforce the fair share of the server resource to its designated user population. The blocking performance is used as a trigger to find new optimal allocations when blocking rates become unacceptable due to change in user demands. We substantiate the analytical model with an extensive simulation for analyzing the performance of the proposed clustered architecture and the protocols. The simulation results show significant difference in overall blocking performance between optimal and suboptimal allocations in as much as 15% at moderate to high workloads. We also show that the proposed cluster protocols result in lower packet loss and latencies by forcing path diversity from multiple sources for request delivery.     

基于IPv6选播路由协议的负载平衡研究

为了提高网络服务的质量,在Internet上经常采用复制的方法产生一组镜像服务器。选播是在单个发送者与一组接收者中任意一个主机之间的数据通信,选播服务可以改善网络负载分布和简化网络应用;根据路径的距离,发往某选播地址的数据包被路由到拥有该地址且最近的镜像服务器;然而,最近的镜像服务器不一定是最佳的镜像服务器。负载平衡是一种通过充分利用所提供的冗余多链路进行业务量分配的模式。基于IPv6选播路由协议,文章提出了一个新的协议模型,通过TCP连接总数确定选播地址对应的最佳服务器,有效地解决由当前选播路由协议确定的最近服务器产生网络拥塞时如何改善路由策略问题,从而实现负载平衡并提高网络的传输性能。     

一种新的服务器集群系统的设计与实现

互联网的飞速发展给我们带来极大便利的同时，也对网络服务器的性能提出了新的挑战。集群技术已成为解决服务器瓶颂问题的有效手段。本文在对服务器集群系统存在的瓶颈问题进行分析的基础上，提出了一种新的服务器集群系统解决方案。该方案通过对传统socket通讯模型进行扩展，并结合直接路由技术，有效地减轻虚拟服务器的负载；同时，通过采用主动自调度策略以解决真实服务器的瓶颈问题，对原型的测试表明该模型是可行的，且提高了服务器集群系统的性能。     

Optimal location query based on k nearest neighbours

Optimal location query in road networks is a basic operation in the location intelligence applications. Given a set of clients and servers on a road network, the purpose of optimal location query is to obtain a location for a new server, so that a certain objective function calculated based on the locations of clients and servers is optimal. Existing works assume no labels for servers and that a client only visits the nearest server. These assumptions are not realistic and it renders the existing work not useful in many cases. In this paper, we relax these assumptions and consider the k nearest neighbours (KNN) of clients. We introduce the problem of KNN-based optimal location query (KOLQ) which considers the k nearest servers of clients and labeled servers. We also introduce a variant problem called relocation KOLQ (RKOLQ) which aims at relocating an existing server to an optimal location. Two main analysis algorithms are proposed for these problems. Extensive experiments on the real road networks illustrate the efficiency of our proposed solutions.     

演变图上的连接子图演变模式挖掘

探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连 接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动 态规划算法.模拟数据集上的实验结果表明,该算法具有较低的误差率和较高的效率.真实数据集上的实验结果表 明,挖掘结果在真实应用中具有实际意义.     

线程池设计与动态优化

线程池是提高服务器程序性能的一种很好技术,已经在服务器端应用程序得到了广泛应用,比如Web服务器、数据库服务器、代理服务器和网络游戏服务器等。尤其面对海量并发连接时,线程池对能显著提高系统整体性能。该文提出了一种轻量级的、高效的线程池设计方案,在实际的网络服务器应用应用取得了非常好的效果。     

基于Nginx负载均衡的动态改进算法

随着过去几十年互联网服务的指数增长,各大网站的访问量急剧上升。海量的用户请求使得热门网站的网络请求率可能在几秒钟内大规模增加。一旦服务器承受不住这样的高并发请求,由此带来的网络拥塞和延迟会极大地影响用户体验。负载均衡是高可用网络基础架构的关键组件,通过在后端引入一个负载均衡器,将工作负载分布到多个服务器来缓解海量并发请求对服务器造成的巨大压力,提高后端服务器和数据库的性能以及可靠性。而Nginx作为一款高性能的HTTP和反向代理服务器,正越来越多地应用到实践中。文中将分析Nginx服务器负载均衡的体系架构,研究默认的加权轮询算法,并提出一种改进后的动态负载均衡算法,实时收集负载信息,重新计算并分配权值。通过实验测试,对比不同算法下的负载均衡性能,改进后的算法能有效提高服务器集群的性能。     

Access Time Minimization for Distributed Multimedia Applications

The problem of minimizing the access time of a requested multimedia (MM) document on a network based environment is addressed. A generalized version of this problem is formulated and retrieval strategies that minimize the access time of the user-requested MM document from a pool of MM servers are proposed. To this end, we design single-installment and multi-installment MM document retrieval strategies, through which the minimization of access time can be carried out. The main idea is to utilize more than one MM server in downloading the requested document. Each server assumes the responsibility of uploading a predetermined portion of the entire document in a particular order. Single- and multi-installment strategies differ in the number of disjoint document pieces each server sends to the client. We first introduce a directed flow graph (DFG) model to represent the retrieval process and generate a set of recursive equations using this DFG. Then, we derive closed-form solutions for the portions of the MM document downloaded from the various servers and the corresponding access time. We present rigorous analysis for these two strategies and show their performance under MPEG-I and MPEG-II video streams playback rates. Their behavior under different network bandwidths is also examined, revealing in-depth information about their expected performance. We also show that in the case of a multi-installment strategy, the access time can be completely controlled by fine tuning the number of installments. Since the number of installments is software tunable, the adaptive nature of the strategies to different channel bandwidths is also demonstrated. Important trade-off studies with respect to the number of servers involved in the retrieval process and the number of installments are presented. In the case of a heterogeneous network employing a single-installment strategy, we prove that the access time is independent of the server sequence used. Illustrative examples are provided for ease of understanding.     

一种高吞吐量、高可扩展数据中心网络结构

虽然以服务器为中心的数据中心网络互连结构部分程度地解决了树型结构面临的性能瓶颈和可扩展性难题,但如何使数据中心网络同时兼具高吞吐量和高可扩展能力,仍然是一个颇具挑战性的问题.为此,提出了具有高吞吐量和高可扩展能力的常量度数数据中心网络互连结构XDCent.XDCent 在各服务器网络端口个数为常量的情况下,确保数据中心网络在保持高吞吐量的前提下能够进行系统规模的无损和持续扩展.     

Cloudlet dynamic server selection policy for mobile task off-loading in mobile cloud computing using soft computing techniques

Wide acceptance of mobile phones and their resource hungry applications have highlighted resource limitations of mobile devices. In this regard, cloud computing has provided mobile phones with unlimited resources in order to help them overcome their constraints and enable them to support wider range of applications; so, mobile devices can outsource their tasks to public or local clouds. To accommodate to exponential growth of requests, user requests should be distributed to different cloudlets and then transparently and dynamically redirected to the servers according to the latest network and server status. Therefore, finding the best place to off-load is vital and crucial to both functionality and performance of the system. However, accurate and timely parameters of network and servers’ status are improbable to achieve, so the traditional algorithms cannot perform effectively and fully efficient. As a solution in this paper, an adaptive neuro-fuzzy inference system is proposed and trained to assign tasks to the servers efficiently. The trained system is robust to imprecise context information and is tolerable measurement noise and errors. We have considered improving both system performance and user quality of service parameters in this paper. Simulation results demonstrate that, compared with other server selection schemes, the proposed scheme can achieve higher resource utilization (utilization is a percentage of time that a server is busy doing something), provide better user-perceived quality of service, and efficiently deal with network dynamics. Simulation results show that our proposed algorithm excels over the compared works in terms of performance, at the best case about 30% and at the worst case about 8.93%.     

基于联合意义度量的Top-K图模式挖掘

提出了一个新的研究问题:如何挖掘Top-K图模式,联合起来使某个意义度量最大化.利用信息论的概念,给出了两个具体问题的定义MES和MIGS,并证明它们是NP-难.提出了两个高效算法Greedy-TopK和Clus-ter-TopK.Greedy-TopK先产生频繁子图,然后按增量贪心方式选择K个图模式.Cluster-TopK先挖掘频繁子图的一个代表模式集合,然后从代表模式中按增量贪心方式选择K个图模式.当意义度量满足submodular性质时,Greedy-TopK能提供近似比保证.Cluster-TopK没有近似比保证,但比Greedy-TopK更高效.实验结果显示,在结果可用性方面,文中提出的Top-K挖掘优于传统的Top-K挖掘.Cluster-TopK比Greedy-TopK快至少一个数量级.而且,在质量和可用性方面,Cluster-TopK的挖掘结果非常类似于Greedy-TopK的挖掘结果.     

Maximal Biclique Subgraphs and Closed Pattern Pairs of the Adjacency Matrix: A One-to-One Correspondence and Mining Algorithms

Maximal biclique (also known as complete bipartite) subgraphs can model many applications in Web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that 1) the number of closed patterns in the adjacency matrix of G is even, 2) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G, and 3) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a nonduplicated enumeration, in particular, for enumerating those maximal bicliques with a large size, where m and n. are the number of edges and vertices of the graph, respectively. We evaluate the high efficiency of our algorithm by comparing it to state- of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even, but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops.     

An approximation-based load-balancing algorithm with admission control for cluster web servers with dynamic workloads

The growth of web-based applications in business and e-commerce is building up demands for high performance web servers for better throughputs and lower user-perceived latency. These demands are leading to a widespread substitution of powerful single servers by robust newcomers, cluster web servers, in many enterprise companies. In this respect the load-balancing algorithms play an important role in boosting the performance of cluster servers. The previous load-balancing algorithms which were designed for the handling of static contents in web services suffer from significant performance degradation under dynamic and database-driven workloads. Regarding this, we propose an approximation-based load-balancing algorithm with admission control for cluster-based web servers in this study. Since it is difficult to accurately determine the loads of web servers through feedbacks from distributed agents in web servers, we propose an analytical model of a web server to estimate the web servers’ loads. To achieve this, the algorithm classifies requests based on their service times and track numbers of outstanding requests for each class of each web server node and also based on their resource demands to dynamically estimate the loads of each node. For the error handling of the model a proportional integral (PI) controller from control theory is used. Then the estimated available capacity of each web server is used for load balancing and admission control decisions. The implementation results with a standard benchmark confirm the effectiveness of the proposed scheme, which improves both the mean response time and the throughput of the cluster compared to rival load-balancing algorithms, and also avoids situations in which the cluster is overloaded, even when the request rates are beyond the cluster capacity.     

有向图并行计算中的多目标剖分算法

在以离散网格为基础的某些数值模拟中,网格间的数据依赖关系可以抽象为有向图．如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟并行计算的基础．剖分算法中,需要综合考虑连通性、并行度、负载平衡、通信开销四个目标．文章在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法．应用于二维非结构网格上的柱对称中子输运并行计算中,通量扫描并行算法在该区域剖分算法上获得的并行效率比原来的无向图区域剖分算法高50％以上．