1、Algorithms for Self-Organization and Adaptive Service Placement in Dynamic Distributed Systems,Artur Andrzejak, Sven Graupner,Vadim Kotov, Holger Trinks Internet Systems and Storage Laboratory HP Laboratories Palo Alto HPL-2002-259 September 17th , 2002,15/11/2004,2,Intruduction,Grid Computing Dynam
2、ic Grid Computing Open Grid Service Architecture (OGSA)Suitable placement of services or applicationsSelf-organization and Fault-tolerance,15/11/2004,3,Management of Dynamic Distributed Systems(1/4),Problem Domain Balancing Demand and Supply Centralized versus Distributed management Dynamic Distribu
3、ted Systems Self-organization, Fault-tolerance and Adaptation Paradigms for Mobile Computing and ubiquitous computing Basic Assumptions,15/11/2004,4,Management of Dynamic Distributed Systems(2/4),Responsiveness and Solution Quality,15/11/2004,5,Management of Dynamic Distributed Systems(3/4),Control
4、Objectives and the Partial Objective Function (POF) (1/2) General control objectives Balancing the server load such that the utilization of each server is in a desired range. Placing services in such a way that communication demand among them does not exceed the capacity of the links between the hos
5、ting server environments. Minimizing the overall network traffic aiming to place services with high traffic close to each other on nearby servers (nearby in the sense of a low number of communication hops across nodes).,15/11/2004,6,Management of Dynamic Distributed Systems(4/4),Control Objectives a
6、nd the Partial Objective Function (POF) (1/2),15/11/2004,7,Ant-Based Control Algorithm(1/4),Classical Ant Colony Optimization1. The ant must “remember” the whole path it has taken; this information might become very large. 2. The ant must visit all objects on its tour. In a large and dynamic system,
7、 this is a serious drawback.3. Finally, each solution (path) must be evaluated against others. This requires central knowledge.Ants , Service Managers and Server Managers Three Entities A service manager Ms of a service S An ant representing s a server manager which executes the ant code, and mainta
8、ins and updates the pheromone table of its server.,15/11/2004,8,Ant-Based Control Algorithm(2/4),Functionality of the System Components Service Managers Watch the performance of its service Evaluate current assignment POF Spawns Ants Ants Created by a service manager Travel from one server manager t
9、o the next Server Managers Environment where ants are executed Lets Ants update pheromone table Maintains pheromone table Sends periodically the pheromone table to its neighbors,15/11/2004,9,Ant-Based Control Algorithm(3/4),Placement Scores and the pheromone table Choosing Next Server Initial placem
10、ent of the Ants,15/11/2004,10,Ant-Based Control Algorithm(4/4),Conclusions for Self-Organization and Fault Tolerance Servers and resources added to the network do not need to inform any central instance of their existenceIf the majority of the servers in the system are unavailable or unreachable wil
11、l not be prevented to work correctly in the remaining part of the system The service manager is a single point of failure; if it disappear the service or a group of them might not recover without human intervention,15/11/2004,11,BLE-Based Control Algorithms (1/2),Decision Cycle in a cluster 1. Each
12、server broadcasts the list of services it hosts with all new arrived services and simultaneously updates its list of all services in the cluster2. Each server evaluates its own suitability to host each service and sorts the list according to the computed score. The evaluation is done by using the PO
13、F, In addition, a service already deployed on a server highly increases the score. 3. Each server broadcasts a list, ordered by scores, of those services the server can host simultaneously without exceeding its capacity. 4. When a server receives a score list from a peer, it compares this score with
14、 its own score for a service. As a consequence, each server knows whether it is the most eligible one for hosting a particular service. 5. The changes in the service placement are executed. Notice that each server knows already whether it has to install new or remove current services. In addition, t
15、he cluster head compares the initial list of services with those, which will be hosted at the end of this decision cycle. The remaining services are passed on to the next hierarchy level as explained below.,15/11/2004,12,BLE-Based Control Algorithms (2/2),Gossiping Algorithms Scalability by a cluste
16、r hierarchy Conclusion: Self-Organization and Fault-Tolerance Advantages Simple Automatic Recovery of Services The cluster size parameterizes the algorithms responsiveness Disadvantages The cluster head can become overloaded or even a single point of failure The hierarchy of the clusters must be cre
17、ated externally,15/11/2004,13,Agents in Overlay Networks(1/2),Service Groups and Agents Service Group Clusters of Independent entities which do not rely on services outside the cluster Group Agents Each group agent has the task to walk around in the resource network and evaluate the current server a
18、nd its neighborhood in regard to placement of the services in the service group; however, one agent stays on one of the servers which host members of the service group, and evaluates only the current placement. A further assignment of a group agent is to provide the fault-tolerance to the optimizati
19、on infrastructure P2P-Based Overlay Networks Servers are connected in a P2P-manner to achieve fault-tolerance and self-organizing properties We are mostly interested in server processing capacity, server storage capacity and the density values of these attributes.,15/11/2004,14,Agents in Overlay Net
20、works(2/2),Lessons Learned for Self-Organization and Fault-Tolerance Advantages Opposed to the ACO-approach, the above algorithms provides full fault-tolerance Another positive aspect is exploiting the self-organization properties of the underlying P2P-network Disadvantages Each agent is a complex e
21、ntity, which might bind more resources than e.g. in case of the Ant Colony Optimization-based algorithm,15/11/2004,15,Two Simple Algorithms,Random / Round Robin (R3) Load Distribution Algorithm Pushes load from an overloaded server to a randomly or in a round robin fashion chosen neighbor that may a
22、bsorb that load if it has the capacity, or pushes the load further on to another server chosen in the same fashion. Advantages Its simplicity and statelessness Disadvantages Unpredictability and insufficient (random) convergence on the chance for thrashing Simple Greedy Algorithm A simple greedy alg
23、orithm just pushes load on to the least loaded neighbor Greedy algorithms make use of locally available information The algorithms R3 and Greedy make good use of locality by placing load on the closest server they can find. Over a longer period, both algorithms achieve good load balancing. However, fast responsiveness is not guaranteed.,15/11/2004,16,Conclusions,
