Research On Efficient Overlay Construction In Virtual Computing Environment

Internet-based Virtual Computing Environment (iVCE) is a novel networkcomputing platform. iVCE is based on the autonomisation of Internet resources andfocuses on resource sharing and collaborative working over the open networkinfrastructure, with the key mechanism of on-demand aggregation and autonomiccollaboration. The characteristics of growing, autonomy and diversity of Internetresources bring great challenges to the resource aggregation in iVCE. StructuredPeer-to-Peer overlay(shortlystructured overlay) technique has various advantages suchas high scalability, low latency, and desirable availability, thus being an importantapproach to organizing dynamic Internet resources, addressing the challenges andrealizing on-demand aggregation. Topology construction is a key technique ofstructuredoverlays that realizes basicoverlayfunctions includingdynamicmaintenanceand message routing. Towards the demands of iVCE resource aggregation, this thesismakesanin-depthstudyontheefficientconstructionof structuredoverlays.iVCE applications have various demands on the underlying overlay topologies,such as low routing latency, high fault tolerance, and balanced load distribution.According to the different demands, most proposed structured overlays have theirunique topology construction mechanisms specific to the regular graphs on which theyare based. The designs of these mechanisms are usually complicated and repeated. Inthis thesis we propose Distributed Line Graph (DLG) transition, a universal topologyconstruction technique for building overlays based on arbitrary d-regular graphs. Wepropose a series of novel mechanisms and algorithms including universal naming,distributed line (DL) iteration, logical nodes mergence/split, and efficient routing.Theoretical analysis shows that DLG-enabled overlays have desirable properties. In aDLG-enabled, N-node overlay, the out-degree isconstant d, the in-degree is between 1and 2d, the average in-degree is d, the network diameter is less than2(logdN?logdN0+D0+1), the maintenance cost of node join/departure isO(logdN),and atmost 3d nodes need to update their routing tables for each join/departure, where d, D0and N0 represent the degree, diameter and number of nodes of the initial graph,respectively.Compared with other static graphs such as hypercube, d-torus, and de Bruijngraphs, Kautz graphs have many desirable properties such as optimal diameter andmaximum connectivity. Due to the complexity in dynamic maintenance, however, bynow there have been no effective overlays that are built based on Kautz graphsK ( d , D) . To address this problem, in this thesis we apply the DLG technique andpropose DLG-Kautz (DK), an effective structured overlay that can be built based onarbitrary Kautz graphs. According to the characteristics of Kautz graphs, we propose a series of algorithms for resource naming, resource-node mapping,fault-tolerant routing,andresourcereallocationduringdynamicnodejoin/departure..Theoretical analysisandextensive simulations show that given the average out-degree ( d ?2 ), DK has theminimum diameter among all the existing structured overlays. We implement theprototypeofDKusingCandJavarespectively.The routing algorithm in DK provides the ability of exact-match queries. As theInternet technique evolves, however, more and more upper-layer applications requirethe underlyingoverlays to provide the abilities of complex queries. Efficient distributedindexes are a key technique for realizing low-latency, low-cost and load-balancedcomplex queries. Based on the DK overlays, in this paper we present balanced Kautz(BK) tree, a distributed indexing technique that supports efficient complex queryprocessing. The BK tree addresses a number of difficulties, such as mapping themulti-dimensional recourse space onto the node space based on Z-curve, and realizingefficient resource information indexing based on the PHT technique. Based on the BKtree, we further propose a dynamic load-balanced and delay-bounded range queryprocessing algorithm called ERQ. ERQ can return the query result in a bounded delaylog d N (2log d log dN?1 ), irrespective the queried range or the number of resourceattributes. This provesthe efficiencyof ourBK tree design. We also simply discuss theBK tree-based methods for processing other complex queries such as Skyline andaggregationqueries.By now most structured overlays are proposed as flat structures: all nodes areassumedtobehomogeneous,andallmessages areroutedusingacommonalgorithm.Inpractice, however, nodes in large-scale systems might beheterogeneous with respect totheir capabilities, reputations,affiliations of administrative domains, and so on. The flatstructures of traditional overlays cannot adapt to the diversityof Internet resources. Toaddress this problem, this thesis presents a novel overlay construction technique thatsupports organizing nodes into groups. Our technique allows applications to groupnodesintermsoftheircharacteristics,and supportsflexibleroutingcontrolpolicies,e.g.,select a group of nodes with fast CPUs to provide computation-intensive services, orselect a group of trusted nodes as intermediate nodes during the routing. Based on thegrouped overlayswe further propose a technique for hierarchical overlay construction,which allows hierarchical relationship between different groups such as the treestructures of Internet administrative domains. Compared with traditional overlays,grouped/hierarchical overlays provide the ability of controlling the routing path andconstraining the routing destination, and further provide great benefit to large-scaledistributedapplicationsinperformance,availabilityandsecurity.