. .r r: a» 1.5.. .fl .. . 3:... 5.3; , V: a. 33.5 Lh..ipwl. 3 «57...,» 5:: “sixth! Is! a“. “u Wt I .LIBRARY ‘ Michigan State University This is to certify that the thesis entitled DESIGN PATTERNS FOR DEVELOPING DYNAMICALLY ADAPTIVE SYSTEMS presented by ANDRES J. RAMIREZ has been accepted towards fulfillment of the requirements for the MS. degree in COMPUTER SCIENCE M JNCL/Lw; - V / Major Professor@ Signature IZ/H/Og Date MSU is an Affinnative Action/Equal Opportunity Employer PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 5/08 K IProjIAcc&Pres/CIRC/DaIeDue Indd DESIGN PATTERNS FOR DEVELOPING DYNAMICALLY ADAPTIVE SYSTEMS By ANDRES J. RAMIREZ A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Computer Science 2008 ABSTRACT DESIGN PATTERNS FOR DEVELOPING DYNAMICALLY ADAPTIVE SYSTEMS By ANDRES J. RAMIREZ As applications grow in size and complexity, and computing infrastructure con- tinues to evolve, it becomes increasingly difficult to build a system that satisfies all requirements and constraints that might arise during its lifetime. As a result, there is an increasing need for the software to adapt to new requirements and environmen- tal conditions after the software has been deployed. Due to their high complexity, adaptive programs are generally difficult to specify, design, verify, and validate. In addition, the current lack of reusable design expertise that can be leveraged from one adaptive system to another further exacerbates the problem. To address this prob- lem, we have developed adaptation-focused design patterns to support monitoring. decision—making, and reconfiguration of adaptive systems where the patterns facili- tate the separate development of the functional logic and the adaptive logic. We have also extended the template used by Gamma et al. [26] for describing design pat- terns with Behavioral and Constraints fields to uniformly present and capture each adaptation design pattern. In addition, the Related Pattern. section is also used to indicate which adaptation design patterns are commonly used together in adaptive systems. We present these patterns in the context of a modeling—based development process, where we focus on supporting the design of adaptive systems. Furthermore, we provide support for specifying invariant properties of adaptive systems. This the- sis describes each design pattern and illustrates how they can be used to construct adaptive and autonomic computing systems. We demonstrate this approach by re- engineering an adaptive news web server from scratch with our design patterns. Copyright by ANDRES J. RAMIREZ 2008 To my family, who has always supported me in every possible way. iv Acknowledgments First, I would like to thank my l\Iaster’s advisor, Dr. Betty H.C. Cheng, for her guidance, support, and expertise. This thesis would not be complete today without her support and feedback. I would like to take this opportunity to express my gratitude to my committee members: Dr. Betty H.C. Cheng (chairperson). Dr. Philip K. l\ refinement E: non-adaptive functional logic ----- -> transition 5 requnrement. or constraint that _________ p satisfies must be satisfied Figure 2.2: Model-based Development Process. The model-based development process comprises six key steps (Figure 2.2): 1. Specify global properties, INV, using a high-level specification language such as temporal logic. 12 ‘2. Identify the different domains, D,, or envirom‘nental conditions under which a program with requirements R.- will execute. 3. Using a high—level specification language. specify local properties, (1),, for each domain identified in step (‘2). 4. Build state-based models (111,» and NJ) of the non-adaptive programs in each domain. Simulations and verifications can be applied to verify and validate the models against both the local ((1),. (DJ) and global properties (INV) prev10usly specified. 5. Identify the possible. scenarios in which dynamic changes may occur. Build adaptive models. M211 and AIM, to safely transfer execution from a source pro— gram to a target program. Specify transitional properties, (bid and (DJ-‘1', to indicate the properties that must be satisfied during the adaptation process. As with step (4) simulations and verifications can be applied to verify and validate the adaptive models against global and transitional properties. 6. The state-based models can be used to either generate rapid prototypes or to guide the development of a(la[_)tive programs [85]. 2.3 Design Patterns Overview A design pattern is a general and reusable solution to a commonly recurring problem in design [26]. Although Christopher Alexander proposed the idea of design patterns for buildings and towns [2] Gamma et al. were able to extend those prin- ciples and apply them to the design of object-oriented software. A software design pattern is not a finished design in the sense that it does not provide code nor can it be directly transformed into code. Instead, a design pattern names, abstracts, and 13 identifies the key aspects of a common design structure that make it useful for creat- ing a reusable object-oriented design ['26]. It is important to note that the purpose of a design pattern is to facilitate the reuse of successful designs among developers, not to propose new and innovative approaches that have not been applied in practice. As a result. the main contribution from Gamma ct al. was capturing proven designs in a new and accessible format. as a catalog of design patterns having a consistent format. Although Gamma et al. did not include any dornain-sl.)ecific design patterns in their pattern catalog [‘26]. they anticipated the need for domain—specific designs that could be reused. Each domain tends to be characterized by specific contexts and requirements, most of Which are learned through experience. Domain—specific design patterns can leverage and reuse the experience gained from designing and building similar applications. In recent years. researchers have cataloged design patterns for a wide range of domains including software architectures [11], resource management [53], concurrent and distributed systems [10]. embedded systems [55]. and so forth. 2.3.1 Template Description A design pattern has four essential elen'lcnts [26]. First. a pattern. name is a handle that can be used to describe a design pattern, its solutions, and consequences. The pattern name should be as descriptive as possible and ideally limited to one or two words. Second. the problem describes when to apply the pattern. It provides a detailed description of the design problem being addressed and its context. Third, the solution describes the elements that make up the design, their relationships, responsibilities, and collaborations. The solution should be sufficiently abstract to be applicable to different situations. Fourth, the consequcmres are the results and tradeoffs of applying the design pattern. This field is essential for evaluating design alternatives and determining whether it is beneficial to apply the. design pattern 14 or not. The design pattern template fields will contain and organize the relevant information to describe each of these four essential elements. The original design pattern template proposed by Gamma et alcomprises four- teen different fields given below with brief descriptions of each field: 10. 11. . Pattern Name: Serves as a unique handle to identify the design pattern. Classification: Facilitates the organization of design patterns based on their level of abstraction and purpose. Some possible classifications include struc- tural, l)()ll‘d\'l01“dl, and creational. . Intent: Provides a brief description of what the design pattern does. . Also Known As: Other well-known name identifiers for the pattern. . Motivation: Presents a scenario that illustrates a design problem and how the class and object structures in the design pattern solve the problem. . Applicability: Defines the context under which the design pattern can be applied. Structure: Provides a graphical representation of the classes and their rela- tionships in the design pattern. . Participants: Describes the responsibilities for each class and object. Collaborations: Presents how the participants collaborate to accomplish their responsibilities. Consequences: Lists the known advantages and disadvantages of applying the design pattern. Implementation: Indicates any known pitfalls, hints, or techniques that a developer should be aware of when instantiating the design pattern. 15 12. Sample Code: Presents code fragments to illustrate how the design pattern might be implemented. 13. Known Uses: Lists examples of the design pattern found in real systems. 14. Related Patterns: Lists other design patterns that are closely related, as well as other design patterns that should be used in conjunction with the current pattern. 16 Chapter 3 Related Work This chapter presents work that is related to building adaptive systems. First, we describe some of the earliest approaches and attempts to build adaptive systems. Second, we present some of the efforts by the system’s community at creating mid- dleware to facilitate the design and construction of adaptive systems. Third, we overview several software engineering efforts to efficiently build and manage adap- tive systems. Some of these approaches include architectural description languages, adaptation frameworks, and aspect-oriented techniques. Finally, we present a few language-based approaches that support the construction of adaptive systems. 3. 1 Early Approaches Adaptive computing systems have steadily gained attention throughout the past several years. Nonetheless, the concept of dynamic reconfiguration has existed since the earliest days of computing. Some of the first attempts at self-modifying code sup- ported run-time program optimization and explicit management of physical memory [6‘2]. These programs were frequently complex and diffith to understand because developers lacked the proper support to abstract the low-level details of dealing with adaptation. New approaches and techniques for building adaptive systems eventually 17 began to emerge. For instance, developers began applying error detection and error handling capabilities to render systems self-adaptive [32]. While these types of ap- proaches helped demonstrate that adaptation was both possible and powerful, they were tightly coupled with source code, application-specific, and typically applied in an ad 1106 fashion. As a result, the first generation of adaptive programs were considered difficult to write, debug. and maintain. 3.2 Systems Approach The first generation of techniques and tools created to enable both static and dy- namic adaptive behavior in applications mostly focused on the implementation level. This strategy proved particularly problematic for adaptive systems in terms of devel- opment and maintenance. For example, with these approaches, building an adaptive system required identifying all the corresponding places where a system might need to reconfigure and manually introducing the changes. Likewise, correcting errors en- tailed identifying where the problem occurred, what caused it, which changes were required, and where modifications needed to be performed. These first-generation ad hoc approaches were not well-suited for efficiently building and maintaining complex adaptive systems. As a result, research on adaptive systems gradually shifted towards developing more efficient adaptation schemes that reduced the burden on developers. 3.2.1 Middleware Recent research by the systems community has focused on extending middleware approaches to provide adaptation services [18, 64, 36]. Middleware refers to the var- ious layers of services that separate applications from operating systems and network protocols [62]. Schmidt [74] decomposed middleware into four layers comprising a host-infrastructure layer, a distribution layer, a. common layer, and a domain-specific 18 layer. In its most basic form, the different service layers of adaptive middleware serve as a level of indirection by intercepting and modifying messages as needed. One ben- efit of middleware—based adaptation is that it shields developers from dealing with resource distribution and platform heterogeneity, thus alleviating tasks previously rel- egated to developers. However, middleware tends to be highly dornain-specific, and as a result, may not be readily available for many application domains. The Mobility and ADaptability enAbling I\=‘Iiddleware (MADAM) [31, 64] project provides a. general component model and middleware infrastructure that supports various adaptation styles for mobile applications. Adaptation occurs seamlessly and without user intervention in reaction to context changes. The MADAM middleware infrastructure supports three types of functionalities. First, it monitors, detects, and reasons about context changes. Second, it decides which adaptation to perform in response through a utility theory approach. Third, it implements the adaptation choices through dynamic composition. To support these functionalities, MADAM operates on an architectural model of the application at run time. This provides the adaptation middleware information about the application structure, its constraints, and the various context and resource dependencies that exist. Sadjadi et (1.1. developed the Adaptive CORBA Template (ACT) to enable run- time improvements to CORBA applications in response to changing requirements and environmental conditions [72]. ACT transparently weaves adaptive code into an object request broker (ORB) at run time. The woven code intercepts and modifies the requests, replies, and exceptions that pass through the ORBs. One of the benefits of ACT is that it is language and ORB independent. Thus, developers can use ACT to build an ob ject-oriented framework in any language that supports dynamic loading of code. Although the ACT infrastructure introduced a slight overhead, experimental results showed it was insignificant when compared to the highly flexible adaptations it offered. 19 3.3 Software Engineering-Based Approaches As developers gained experience with these initial approaches they realized that building adaptive systems from scratch was impractical. The second generation of tools and techniques for building adaptive systems would have to address the follow- ing requirements. First, the specifics of adapting a system should be as transparmlt as possible to developers. Second, adaptation mechanisms should be reused whenever possible. Third. the adaptive logic should be minimally invasive upon the functional logic. Finally, these approaches should be. applicable to both new systems, as well as legacy systems. Ideally, developers would be able to create efficient adaptive ap- plications without explicitly implementing all the required adaptation mechanisms. Based on these requirements, researchers provided arcl'iitectures, frameworks, and lamguage-based support for systematically building adaptive systems. 3.3.1 Architectural-based Techniques Separating the adaptive logic from the functional logic simplified the development and maintenance of adaptive systems while promoting software reuse. Researchers presented several architectures for cleanly separating concerns in adaptive systems [6, 27, 42, 67]. In particular, Oreizy [67] proposed an infrastructure that supported two simultaneous processes in self-adaptive software. While the first process dealt with the evolution of the system, the second process dealt with the cycle of detecting changing circumstances and plamiing responsive modifications. Meanwhile, other researchers [22, 30, 32] explored the tasks of monitoring and decision-making and how they interacted within adaptive systems. Garlan and Shaw [27, 75] further subdivided the architecture of adaptive. systems by applying control theory approaches to adaptive systems. More recently, new approaches [6] have further extended these architectures by decentralizing each process across distributed infrastructures. As 20 a result, the most common architecture found in adaptive systems today comprises monitoring, decision—making, and reconfiguration processes. Another area of software engineering adaptive research has focused on using ar- chitectural description languages (ADL) to capture and manage system evolution and system adaptation. Architecture-based approaches for self-adaptive software usually view systems as networks of concurrent components bound together by connectors [67]. Architectural-based representations of a system shift focus away from source code to coarse-grained components and their interconnections. In these representa- tions. a component is responsible for implementing application behavior and main- taining state information. Connectors, on the other hand, offer transport and routing services for messages or objects. In architectural—based approaches, dynamic recon— figuration involves not only adding, removing, or modifying components and their connections, but also managing the evolution of the system and the consistency of the component-connector representations. Recently, Kramer and Magee proposed a three—layer architecture-based model for self-adaptive systems [58]. The lowest layer, the component control layer, is responsible for the creation, interconnection, and deletion of components. The change management layer comprises a predefined set of reconfiguration plans that can be applied to repair the application at run time. The highest layer, the goal management layer, creates new change management plans as needed, thus facilitating the overall evolution of the system and its reconfiguration mechanisms. Three examples of architectural-based approaches at self-adaptive software in- clude Taylor et al.‘s C2 [67], Gorlick’s Weave [35], and Garlan et al.’s Rainbow [29]. C2 [67] composes systems as a hierarchy of concurrent components bound to- gether by connectors such that a component within the hierarchy can only be aware of components residing at the same level or beneath it. VVeaves, on the other hand, is a dynamic, object—flow-centric architecture targeted towards applications with large 21 volumes of data flow and real-time constraints [35]. One interesting characteristic of Weaves is that no component in a network knows the sources of its input objects or the destination of its output objects. While this approach provides a large de- gree of flexibility. it is also susceptible to security risks. For instance, a component may not be able to authenticate the origins of a particular message if it does not know the source of its inputs. Lastly, Rainbow [29] is an adaptation framework that uses models not only to represent the systems architecture, but also to select which reconfiguration will yield the desired behavior. 3.3.2 Frameworks Adaptive software research has also focused on creating and using frameworks for building adaptive systems [12, 27, 49]. A framework is a set of cooperating classes that make up a reusable design for a specific class of software [26]. Among other things, the framework dictates the overall architecture of the application and its thread of control. This often leads to an inversion of control in which developers write code that gets called by the framework. One of the major benefits of frameworks is that it provides large amounts of reusable code, thereby enabling developers to build applications faster. Nevertheless, some creative freedom is lost because many design decisions have already been made by the framework developers [26]. Additionally, framework-based applications are sensitive to changes in the framework’s interface. Garlan et al.’s Rainbow is an architecture-based self-adaptation framework with reusable infrastructure [27]. Their approach uses external adaptation mechanisms for two reasons. First, it facilitates the application of their reusable infrastructure to legacy applications without being invasive upon the functional logic. Second, it allows developers to specify and reuse adaptation strategies for multiple system concerns. Rainbow supports distributed component monitoring, probe and gauge deployment, architectural-based system representation and adaptation strategies, and effectors to 22 reconfigure the system. Rainbow’s adaptation infrastructure incorporates control theory concepts [75]. First, probes monitor the system and report values to gauges and gauge consmners. These values are then related to properties of the architectural model. Each time an architecture property is updated, the architecture is analyzed to ensure no constraint is violated. If a constraint has been violated, then the architecture must be recon- figured. Rainbow uses utility theory—based approaches to select a reconfiguration plan. Finally, through Rainbow’s infrastructure and effectors, the reconfiguration is executed on the system’s architecture. 3.3.3 Aspect-oriented Programming Another interesting approach for building adaptive systems is based on the aspect-oriented programming (AOP) paradigm introduced by Kiczales [51]. AOP provides abstraction techniques and language constructs to manage crosscutting con- cerns [62]. AOP defines an aspect as code that implements a crosscutting concern. Using an aspect weaver, AOP inserts aspects into specific code locations, called point- cuts, during compilation. As a result, not only does AOP decouple crosscutting con- cerns from the functional logic, it also localizes them. This separation facilitates the consistent maintenance of an application as it evolves. Dynamic recomposition can exploit the AOP paradigm because most adapta- tions are crosscutting in nature. Yang et al. [82] introduced a systematic two-step process that defined where, when, and how adaptations would be incorporated into an application. First, aspects are used to extend a program with an adaptation infras- tructure and entry points into the adaptation kernel. Then the adaptation kernel uses a rule—based engine to determine if an adaptation should be performed and executes the corresponding actions if necessary. 23 3.3.4 Software Reconfiguration Design Patterns Gomaa et al. proposed several design patterns for reconfiguring software ar- chitectures at runtime [34]. The four design patterns they introduced specify the behavior required to dynamically reconfigure specific types of architectures. In par- ticular, the design patterns describe the reconfiguration of master / slave, centralized, server/ client, and decentralized architectures. For each design pattern, Gomaa et al. identify when it is safe to perform a reconfiguration and provide hierarchical UML state diagrams illustrating the necessary behavior. Although these reconfiguration design patterns are helpful to developers implementing dynamically adaptive systems from scratch, their contents are not organized in template format and they do not address safety and assurance. 3.4 Language-based Approach Sadjadi et al. proposed a transparent reflective aspect programming (TRAP) technique for enabling adaptive behavior on legacy applications [73]. TRAP was designed around the four techniques of aspect-oriented programming, behavioral re— flection, component-based design, and adaptive middleware. Briefly, TRAP works as follows. First, developers identify potential points of adaptation (hook points.) Adaptive infrastructure is then woven into the legacy system at the corresponding hook points. The hook points are then monitored for adaptation conditions. If a condition that requires an adaptation arises, then a rule-based decision-making pro- cess determines the appropriate code to swap in or out. As a result, TRAP could be used to enhance legacy code with adaptive behavior without explicitly altering the functional logic. TRAP / J was a specific incarnation of TRAP based on the Adaptive Java Language [48]. 24 Chapter 4 Process Used for Developing Design Patterns This chapter introduces the research methods designed to harvest, evaluate, and refine the adaptation design patterns presented throughout this thesis. First, we motivate why it is important to have a methodology that is able to systematically select, analyze, and abstract recurring solutions as design patterns. Second, we state the goals for this methodology and how they relate to the thesis statement. Third, we present the sequence of steps that were used to develop each adaptation design pattern. We describe and each of the key steps in this iterative process, and, if applicable, we also indicate any limitations they may have. 4. 1 Motivation The survey conducted on background and related work indicate two particular trends in the software engineering community with respect to adaptive and autonomic systems. F irst. the software engineering community has begun to address adapta- tion concerns by providing frameworks [27], middleware [64], and language—based support [73] for enabling applications with adaptive. and autonomic behavior. The 25 majority of these approaches deal with adaptation at the implementation phase, thus making the assumption that the requirements, designs, and constraints are already understood. Second, with the exception of a few projects [10, 34], little attention has been given to reusing adaptation expertise at the modeling level through the use of design patterns. Compared to other approaches, design patterns promote creative freedom by imposing fewer initial constraints on design decisions [26]. This thesis combines the key ideas of specializing design patterns [34] and orga- nizing their contents through templates [10, 26]. First, the design patterns presented by Gomaa [34] are focused solely on reconfiguring different types of software archi- tectures at run time. Instead of providing design patterns for general problems in reconfiguration. their design patterns address very specific problems that arise dur- ing reconfiguration. Second, the design patterns presented in [10, 26] make explicit use of a design pattern template for structuring and presenting relevant information. Synthesizing concepts from both approaches, this thesis proposes to harvest design patterns that are specific to recurring problems encountered in adaptive applications and structuring their contents with the use of a template. As a result, these design patterns may be combined according to specific requirements and constraints in order to yield customized adaptive applications. Harvesting design patterns is a difficult and subjective process because there is no existing set of metrics that quantify the quality of a design pattern. Those who harvest design patterns, for instance, must address many subjective questions while generalizing solutions to a recurring problem. For instance, exactly when does a problem get classified as being recurrent in a given domain? Which data sources should be used to find the desired design patterns? Are the solution models sufli— ciently abstract to be applicable to a wide range of systems yet, at the same time, specific enough to guide developers throughout the implementation phase? Since the answers to these questions will vary between developers, it is important to have an 26 iterative process that documents and justifies each decision taken while harvesting design patterns. The feedback loop will enable the refinement of both the results and the process itself. 4.2 Goals Recall that the objective of this thesis is to investigate recurring problems en- countered in adaptive and autonomic systems and promote the reuse of successful solutions. In order to make progress towards this objective and produce design pat- terns that are valuable to both experienced and inexperienced developers working with adaptive and autonomic systems, the process used for harvesting design pat- terns must: 0 Look for good solutions and attempt to generalize them. 0 Incorporate the use of a template to organize the information contained in the design pattern. 0 Produce specific design patterns for monitoring, decision-making, and reconfig- uration. o Analyze interactions between monitoring, decision-making, and reconfiguration design patterns. 0 Evaluate and gradually refine the resulting collection of design patterns. 0 Facilitate the use of formal analysis tools for determining whether a solution model satisfies certain properties. 27 4.3 Harvesting Process A data flow diagram of the iterative process used to harvest and refine the adap- tation design patterns is shown in Figure 4.1. This data flow diagram illustrates how information is gradually processed and transformed into an adaptation design pat— tern. To start the process, developers must. identify and define a recurring problem that is related to adaptation. One possible way to identify recurrent problems is to analyze research publications with common topics related to monitoring, decision- making, and reconfiguration. Based on the recurrent problem identified, developers must also determine what is the intent, context, and motivation for addressing the problem. A clear definition of these fields will narrow the search for existing solutions to the recurring problem. Next. developers need to select the relevemt data sources that will be analyzed and. generalized into design patterns. Three types of data sources are available for this task: commercial applications, open-source implementations, and research projects. In general, some data sources are better suited than others for harvesting design pat- terns. F or instance, commercial applications typically incur problems related to high costs and proprietary rights. Likewise, open—source implementations typically have little, if any, documentation. Research publications on the other hand are accessible, well documented, and peer reviewed for quality purposes. As a result, the solutions gathered from research publications typically bear more weight in the overall adap— tation design patterns than commercial and open-source projects do. Many research areas in computer science address issues related to monitoring, decision-making, and reconfiguration. For example, monitoring is frequently en- countered in distributed systems and safety critical research communities. Likewise, decision-making techniques are practically ubiquitous throughout the artificial intel- ligence field. Additionally, reconfiguration techniques are now starting to emerge in new research communities that focus on safely adapting applications at run time. 28 Recurrent Research Open Source Problems Publications Implementations Define ocuses . Problem Developer relevant definition resolve intent Selected Sources _ best candidates . set of models, code, Generalize . documentation ““‘fied Elicit class interac- , diagram tions behavroral diagrams generalized bl solution new pro ems v solution pairs I [Hap 5, [ion Desrgn refined solution feedback ' Refinement < Validation Figure 4.1: Harvesting process data flow diagram. 29 Although this approach manually selects data sources, it is conceivable to automate some parts of this process by incorporating techniques from domains such as data mining. Generalize Solutions. The process of abstracting and unifying different solutions into one representative design pattern is similar to the process of model fitting found in mathematics. Specifically, given a set of points, a mathematician derives a line that will best represent those points and, at the same time, predict where future points may lie with some degree of certainty. Similarly, recurring instances of the solution are scattered throughout different research projects and implementations. Design patterns are meant to generalize these instances while simultaneously guiding the development of future instances. As with model fitting in mathematics, some points may be of more interest than others. This results in two complimentary approaches for abstracting and unifying different solutions into a design pattern. The conceptual difference between the two approaches can be seen in Figure 4.2. The first approach exploits the discovery of a particularly good solution to the problem being addressed. Specifically, a developer creates a preliminary draft of a design pattern based on a good solution 1 and then refines it as further instances are found. As a result, that solution bears more weight on the finalized design pattern than the other solutions do. The second approach, on the other hand, considers a suite of solutions all at once. Thus, While the first approach is biased towards one particular solution instance, the second approach weighs every solution more equally. Regardless of which conceptual approach is undertaken, several steps must be performed to abstract and unify various solutions into a design pattern. First, devel- opers must determine the similarities and differences between the different solutions being abstracted. That is, both structural and behavioral diagrams need to be an- alyzed to discover important classes, the types of associations between them, their 1We consider a good solution to be one that. has been applied several times with positive results. 30 Refined Design Pattern Design Pattern Design Pattern 000d Sol ution. Solution Solutioni Solution Solution ' n n Approach 1 Approach 2 Figure 4.2: Abstraction Process Diagram multiplicity, their responsibilities, how they interact, and what the constraints are. If these diagrams are not available, then developers can either manually derive them by studying the code or automatically generate them by applying reverse engineer- ing techniques. The similarities and differences between these diagrams will help developers determine when to add or remove details in the design pattern. Validation. Two forms of validation are used to estimate the quality of the resulting design patterns. The first form of validation consists of searching for additional instances of the design pattern in previously unexamined data sources. This validation is performed in the early stages of design pattern development. Each new instance encountered strengthens the validity of the solution as well as provides additional information for refining the design pattern. The second form of validation consists of applying matured design patterns to a case study application. As the design patterns are instantiated, the resulting models can be formally analyzed through tools such as Hydra [63] and the Spin model checker [47]. If errors are found, then the design pattern can be revised accordingly. 31 Lastly, the analysis gathered from the two forms of validation can be used to refine the process for harvesting design patterns. To facilitate the fine-tuning of this methodology and improve its results, there are three feedback points within the process. First, if the respective designs cannot be generalized to a common solution, it might indicate that the problem definition is too broad. As such, it may need to be narrowed towards a more specific recurring problem instead. Second, other research disciplines could be explored while searching for solutions. For instance, instead of focusing solely on intelligent systems, the scope of resources used to harvest a decision- making design pattern could be broadened to include biologically-inspired systems as well. Finally, case studies can refine the observations gathered with respect to how a set of design patterns interact with one another. 32 Chapter 5 Adaptation Design Patterns This chapter introduces the template used to describe adaptation design patterns, enumerates the list of patterns, and presents a criteria for organizing, classifying, and using the patterns. In addition, this chapter contains the complete description of all adaptation design patterns identified thus far. 5.1 Adaptation Design Pattern Template This thesis uses a template similar in style to that used by Gamma et al. [26] in order to facilitate the understanding and application of the adaptation design patterns. We have modified the original design pattern template in a few aspects to address the needs of adaptive systems. Table 5.1 overviews the adaptation design pat- tern template. First, the Known As, Implementation, and Sample Code sections have been removed. The Known As section is irrelevant as, to the best of our knowledge, the majority of the design patterns presented in this thesis have not been previously documented. The Implementation and Sample Code sections are too specific for the design patterns presented in this thesis. Second, the template has been extended with a Behavior and Constraints sections. The Behavior section presents either sequence and/ or state diagrams that illustrate sample behavior. The Constraints section uses 33 Linear Temporal Logic (LTL) and A-LTL [84] and textual descriptions to specify properties that must be satisfied by the instantiated design patterns. Note that in some instances the LTL and A-LTL formula contain specific function invocations as “boolean operators”. When these operators are referenced, they implicitly encode an predicate assertion that returns a boolean value corresponding to whether the function has been invoked or not. Lastly, although Gamma et al. used the Object Modeling Technique (OMT) [69] to represent structural and behavioral diagrams, we used the Unified Modeling Language (UML) to give structural and behavioral infor- mation about each design pattern. Specifically, structural diagrams are represented through UML class diagrams (for monitoring and decision-making patterns) and UML component diagrams (for reconfiguration patterns). Likewise, UML statecharts are used depict a pattern’s behavior. 5.2 Adaptation Design Patterns Catalogue Overview Table 5.2 gives an enumeration of the twelve adaptation design patterns har- vested thus far along with their intentions. These design patterns have been identi- fied from analyzing several adaptive systems and related projects. It is important to consider the following when evaluating these design patterns. First, these patterns capture only a fraction of what an adaptation expert might know. Other areas related to monitoring, decision-making, and reconfiguration could use design patterns as well. Second, this thesis includes only designs that have been applied more than once in different systems. Third, although most of the design patterns are applicable to a wide range of adaptive systems, some are applicable only to a specific set of adaptive systems. The Intent section can be used to determine the applicability of each design pattern. In addition, the Related Pattern section can be used to determine which 34 Pattern Name The pattern name uniquely identifies and describes the pattern. Classification: The classification facilitates the organization of pat- terns based on the purpose of the pattern. Intent: A brief description of the problem(s) that the pattern addresses. Context: Describe the conditions and context in which the pat- tern may be applied. Motivation: A description of sample goals and objectives of a sys- tem that motivate the use of the pattern. Use-cases and use-case—diagrams describe goals of the pattern application. Structure: A representation of the classes and their relationships depicted in terms of UML class diagrams (for moni- toring and decision-making patterns) and UML com— ponent diagrams (for reconfiguration patterns). Participants: Itemizes the classes and objects that are included in the adaptation design pattern and lists their respon— sibilities. Behavior: Provides an illustrative representation of scenarios for class and object interaction. Also gives a description of the behavior of the pattern by using sample or high- level, abstract UML state and sequence diagrams. Consequences: Describes how objectives are supported by a given pat- tern and gives the trade-offs and outcomes of the pat- tern application. Constraints: Contains LTL templates and a prose description of constraints that must be satisfied by a given design pattern implementation. Related Patterns: Additional design patterns that are celmnonly used in conjunction. Known Uses: Lists the sources where the design pattern was har- vested from. Table 5.1: Adaptation Design Pattern Template 35 design patterns are commonly used t(;)gether. More details for each design pattern is provided in Section 5.5. Name Description Sensor-Factory (41): Deploy sensors across a distributed i11- frastructure and probe components. Reflective Monitoring (50): Perform introspection on a component and dynamically alter a sensor’s behav- 101'. Content-based Routing (59): Route monitoring information based on the content of the message. Case-based Reasoning ( 68): Rule-based approach to selecting a re— configuration plan. Divide and Conquer (‘78): Systematically decompose a complex re- configuration plan into simpler reconfig— uration plans. Adaptation Detector ( 88): Interpret monitoring data and deter- mine when an adaptation is required. Architecture-Based (97): Provide an architecture-based approach for selecting reconfiguration plans. TradeQfi-Based (106): Systematically select a reconfiguration plan that best balances multiple objec- tives. Component Insertion (115): Safely insert and initialize a component at run time. Component Removal (125): Safely remove a component at run time. Server Reconfiguration (135): Safely reconfigure a server - client com- ponent architecture at run time. Decentralized Reconfiguration Safely insert and remove components (145): from a decentralized component archi- tecture at run time. Table 5.2: Current list of adaptation design patterns 5.3 Classifying Adaptation Design Patterns It is important to classify and organize design patterns in order to facilitate their use. Our adaptation design patterns can be classified using two orthogonal classification S(‘.ll(‘.II1(.‘,S. The first option is to classify the patterns according to their 36 purpose: creational, structural, or behavioral [26]. Creational patterns focus on object creation. Structural. patterns focus on describing the composition of classes or objects. Behavioral patterns depict the method of interaction and distribute the responsibility of classes or objects. Thus far, we have only identified structural and behavioral adaptation design patterns. The second option is to classify the patterns according to their adaptation func- tions: monitoring. decision-making, and reconfiguration. l\‘lonitoring patterns focus on probing con‘iponents and distributing the information across a network to inter— ested clients. Decision—making patterns focus on identifying when a reconfiguration is needed and selecting a reconfiguration plan that will yield the desired behavior. Reconfiguration patterns focus on safely adding, removing, or modifying components at run time to adapt a program. Thus far. we have identified several design patterns for each area. Monitoring and decision-making patterns are what we consider to be adaptation- enabling design patterns. These design patterns provide the necessary infrastructure to perform introspection and intercession. Although monitoring and decision-making design patterns do not reconfigure an application, without these, a developer would have to manually perform these tasks at run time. Therefore, reconfiguration patterns depend upon monitoring and decision-making design patterns. These. design patterns can also be used to aid in the design and construction of autonomic computing systems comprising some number of autonomous elements. Each autonomous element is instrumented with monitoring, decision-making, and reconfiguration processes (see Figure 5.1.) To build an autonomic element, at least one design pattern from each category must be applied. 37 Monitoring L Decision Making _ Reconfigur— ation Functional Logic ‘ Autonomous Element J Monitoring Decision Making Reconfigur- ation Monitoring Decision Making Reconfi gur. ation Functional Logic Functional Logic ,4 Monitori n g Decision Making Reconfi gur -ation Functional Logic Autonomic Computing System Figure 5.1: Applying Patterns to Self—Adaptive and Autonomic Systems 38 5.4 Adaptation Design Pattern Roadmap In order to develop an adaptive system using our approach, developers must carefully integrate several of the design patterns presented in this thesis. We have observed how different patterns interact together while harvesting the individual de- sign patterns. Based on these observations, we recommend certain sets of design patterns to be used together. To determine which design patterns work well together, developers can refer to either the Related Patterns section of each design pattern or to Figure 5.2. For instance, all monitoring and decision-making design patterns use the Adaptation Detector ( 88 ) pattern to interpret the data and determine when a reconfiguration is warranted. Likewise, every decision-making design pattern can use any of the reconfiguration design patterns presented in this thesis. 5.5 Adaptation Design Pattern Repository This section gives a detailed description of the adaptation design patterns dis- covered thus far. The names of the design patterns are denoted in italics, and the fields of each design pattern are given in a san serif font. Method names and messages are denoted in italics. 39 Distributed publish results Reflective retrieve Monitoring _ Content—based Routing attributes l l non-distributed publishr results dlStl’l bUlCd \ monitoring retrieve attributes . published Adaptation values Detector A t: ggeran trigger an tgzggerian a aptauon adaptation a ptation Case-based Architecture-based Trade-Off-based Reasoning Reconfiguration Reconfiguration Sigphfy , simplify recon guration reconfiguration plan v plan Divide & Conquer Server Decentralized Figure 5.2: Adaptation Design Patterns Commonly Used Together. Reconfiguration Reconfiguration insert remove , component componen Component Component Insertion Removal 4O 5.5.1 Sensor-Factory (41) Pattern Classification: Structural - Monitoring. Intent: Systematically deploy software sensors across a network to probe distributed components. Context: The Sensor-Factory (41) Pattern may be used when: 0 the components to be monitored are distributed. 0 each component provides an interface that can be probed for the required in- formation. Motivation: External adaptation mechanisms must effectively collect information about the running system to properly evaluate a system’s operational status [30]. The ob- jective of the Sensor-Factory (41) design pattern is to manage distributed sensors across a networked environment such that they may probe distributed components. The Sensor-Factory (41) design pattern captures the structural relationship between sensors, clients, and components. By decoupling sensors from clients and components, the monitoring infrastructure is flexible and more amenable to change. Figure 5.3 shows a use-case diagram of the Sensor-Factory (41) Pattern. Two goals of this pattern are to deploy a software sensor across a network and to probe a distributed component. Use-Case: Request sensor Actors: Client Description: A client requests a sensor to monitor some component. Includes: Search registry, Add sensor 41 Clie Register usage / \ Request sensor \ \ \ I \ D \ \ <1ncl udes> ‘ \ I \ I’ \\ \\ I \ \ l \ \ \ I \ \ I \ \ I W sensor Poll sensor Figure 5.3: UML use-case diagram of the Sensor-Factory (41) Pattern Use-Case: Search registry Actors: - Description: Determine whether any deployed sensor already provides the needed information. Includes: Register usage, Check resources Use-Case: Check resources Actors: - Description: The system determines if an existing sensor can be shared between more than one client or whether a new sensor can be deployed across the network without violating any QoS constraint. Includes: - 42 Use-Case: Register usage Actors: - Description: Records the relationship between a sensor. the component it is monitoring. and the clients it is servicing. Includes: - Use-Case: Add sensor Actors: - Description: Creates a new instance of a sensor in the network. Both a client and a component are assigned to this sensor. Includes: Register usage. Check resources. Use-Case: Start sensor Actors: Client Description: A sensor is initialized and activated before it begins transmitting data. Includes: - Use-Case: Receive data Actors: Client Description: A client. receives data from the sensor. This service supports both push and pull actions on a sensor. Includes: - Structure: A UML class diagram for the Sensor-Factory (41) Pattern can be found in Figure There are two different types of sensors that can be found in this design pattern. Simple Sensors can handle booleans, integers, and real data types. Complex Sensors, on the other hand, are capable of either reporting more complex data types or of aggregating the outputs of a Simple Sensor. Regardless of their specific type, Simple Sensor and Complex Sensor both inherit the interface from the Abstract-Sensor abstract class. As a result, they should provide an interface with basic functionalities such as 43 pushing and polling for data. Participants: 0 Abstract-Sensor: Simple Sensor and Complex Sensor both inherit from this ab- stract class. As a result, these sensors share an interface to common operations such as pushing and pulling data. 0 Client: This class is used to represent any component that needs to perform either internal or external monitoring. 0 Complex-Sensor: This type of sensor contains greater computing resources on- board than a Simple Sensor does. As a result, a Complex Sensor is capable of reporting complex data types, aggregating various Simple Sensor data feeds, and performing on-board computations. 0 Registry: This class is responsible for tracking deployed sensors across the net— work. Each entry should at least record the sensor name, the sensor type, the Client it is providing data to, and the component it is monitoring. Additionally, this class provides a search functionality based on the available fields. 0 ResourceManager: This class has two responsibilities. First, it determines if an existing sensor can be shared with one or more clients. A sensor can be shared as long as it does not violate any existing constraint. Second, it determines if the system has enough resources to deploy a new sensor across the network. 0 Sensor—Factory: Clients must interact with this class in order to gain access to a sensor. It regulates the dynamic access and management of sensors across a network. 0 Simple-Sensor: The most basic sensor available. It is capable of reporting boolean, integer, and real data types. Additionally, it can be configured to 44 0000090030000 _ " AAO~..000VV 4 0:00 0.3:00 H 0.020300%. 0.3:00 H 03.09% 0.3:00 ” 0330 03:00 a 3000 20> a 00.06 20> ” ©0030 20> n 33:00 US$398 20> “ 33:00 3.030300% *2 Emu—COL “ DGOQHO: mesa H 2 300:0 AA0~=000VV A: uuuuuuuuuu 0.3:00 ” x030 wibm N 30303 wibm H 300:0 0.3:00 H 03.00 00m00m0.0E.m 0.3:00 a .0520. *..o > 000009000036. 0.3.000 . 20> ” Amibm ”2.0>0E00 20> U Amibm ”20000.30 20> n 200030.905 ”$0030.30 20> ” €0000m0.m.E.m H mv0>0E00 20> ” 300:0 5.3.6.00 000.003 ” 300% ”3300000 b32w0m /\_ 000.003 ” 900.5000 0053.00 000.003 ” C00000m000 0.3:00 U .0303. E *zo 3003000 000.003 H 0300:0000 000.003 0 C00m00m000 b0300n.¢0m=0m 00030 W— 000.003 H 0330503030 howwca—ZuULSOwON— Figure 5.4: UML class diagram of the Sensor-Factory (41) Pattern 45 poll a component at different intervals and periods. Behavior: Figure 5.5 shows a UML sequence diagram for an example of the Sensor-Factory (.41) Pattern in a distributed monitoring system. The Client requests a Simple Sensor (an active networked sensor) from the Sensor-Factory. The Sensor-Factory first deter- mines whether an existing Simple Sensor is already providing the desired information. If not, then Sensor-Factory checks the Resource Manager to determine if another Simple Sensor can be deployed across the network without breaking any quality of service constraints. If so, then Sensor-Factory creates a new instance of Simple Sensor and initializes it to some default sensor setting. Sensor-Factory then notifies the Client that the Simple Sensor is ready for use. Client polls the Simple Sensor until it is done monitoring. Consequences: 1. This design pattern reuses the provided functionality and interface of a dis- tributed component to extract the desired attributes. However, if a component’s interface is excessively polled, then it could interfere and alter the component’s behavior. 2. Different types of sensors can be systematically deployed at run time while providing a flexible monitoring infrastructure that is amenable to adaptation. 3. This design pattern ensures system integrity by accessing a component’s at- tributes through its interface. 4. The Registry and Resource Manager share existing sensors whenever possible. This avoids wasting resources in the form of duplicated sensors. 46 . . . . . _ .l _ _ - .2508: 223. . . . n . .t . _ - llllllllllllllll rllllllllllllllll—IIIIIIIIIIIIIIIIIIIlIlLlllllllllllllln'. " u u A . 008. u .. r .i . . _ _ _ _ . _ _ . u u _ u C 300.53.87.00 “ m m _ u u “ AA030000vv 4. u 3.. ................. . u u . A2 m0.0mr0um.w00 . . an ............. .n .................... y . _ p . C00000m000 . . . uuuuuuuuuuuuuuuuuuu I u at n _ Am $053808 .4 . . 4 00850200 . . . r1 . _ _ . . . . _ . u u . Hug: n n _ al.75003— _ 33m _ _ Mails “.00000m J 0&8le Figure 5.5: UML sequence diagram example of the Sensor-Factory (41) Pattern 47 Cf! This design pattern introduces a management layer between a Client and a sensor. This additional overhead may degrade performance. 6. hrIonitoring is only supported for those components with an interface to the required attributes. Constraints: 0 Property 1: Globally, it is always the case that if Resource Manager denies a Client request for a sensor, then Sensor-Factory does not create a sensor for the Client. El ((ResourceManager.deny(Client) —> -: Sensor-Factory. createSensor (Client) ) This safety property ensures that Sensor Factory obeys the recommendations provided by the Resource Manager. Otherwise, if the system’s resources are not properly maintained, then the entire application may suffer as a result. 0 Property 2: Globally, it is always the case that if Client requests a sensor to Sensor-Factory, then Sensor-Factory will eventually grant access to a sensor. El ( (Client . request (sensor) ) —+ 0 (Sensor- Factory . grant (Client) ) This liveness property guarantees that a Client will eventually get access to a SCHSOI‘. Related Design Patterns: 48 o Adapter Design Pattern [26]: This pattern can enable the interaction between a Client and a sensor whenever their interfaces are incompatible. o Reflective Monitoring (50) Design Patterns: This pattern can be used wl‘ienever a component does not provide an interface to the required attributes. Such values may be accessible through Introspection. o Adaptation Detector (88) Design Pattern: This pattern is responsible for interpreting the results provided by a sensor and determining when an adaptation is required. Known Uses: REsource MOnitoring for network—aware applications [20]. Rainbow Adaptation Framework [27. 30]. o A Distributed Monitoring Service Architecture (MonALISA) - via SNMP [66]. SNMP4J—Agent [24]. 49 5.5.2 Reflective Monitoring ( 50) Pattern Classification: Structural - Monitoring. Intent: Provide mechanisms to observe the internal state of a component and to change the monitoring scheme dynamically. Context: The Reflective A'Ionitoring (50) Pattern may be used when: 0 a component needs to be monitored and it does not provide an interface to the desired attributes. o monitoring schemes need to be dynamically altered. Motivation: An external adaptation mechanism must be able to observe a component’s in- ternal state to properly evaluate its operational status [30]. Observing the internal state of a component may be difficult due to visibility constraints imposed by en- capsulation techniques. Specifically, the only way to access private attributes in a component is through a predefined interface. The Reflective Monitoring (50) design pattern instruments components with introspection capabilities such that monitoring processes can probe a component’s internal attributes. In addition, through the use of proxies and indirection, the Reflective Monitoring (50) design pattern facilitates the dynamic reconfiguration of monitoring schemes transparently. Figure 5.6 shows a use-case diagram of the Reflective Monitoring (50) Pattern. Two goals of this pattern are to observe the internal state of a component and to dynamically reconfigure the monitoring scheme. 50 System Create proxy ’ <> Cl>/ <> I I lntrospect Client Add proxy Register proxy - ' <> - / / / I > Remove proxy Figure 5.6: UML use-case diagram of the Reflective Monitoring (50) Pattern Use-Case: Submit Component Actors: Client Description: A client notifies the system it wants to monitor a specific component. Includes: Create proxy. Use-Case: Create proxy Actors: - Description: Creates a proxy object that supports the interface and functionality of the specified component and returns it to the Client transparently. This proxy also supports probing for internal attributes. Includes: Register proxy. 51 Use-Case: Int respect Actors: Client Description: A client probes the proxy through its interface. Includes: - Use-Case: Register proxy Actors: - Description: Registers and tracks proxies across the system. Includes: - Use-Case: Add proxy Actors: Client Description: Adds a monitoring proxy to a specified proxy chain in the system. Specifically, it augments monitoring functionality. Includes: Register proxy. Use-Case: Remove proxy Actors: Client Description: Removes a proxy from the system. Includes: Register proxy. Structure: A UML class diagram for the Reflective Monitoring (50) Pattern can be found in Figure 5.7. A reflective monitoring approach must overcome encapsulation techniques that hide private attributes from external entities. Two important constructs are required for reflective monitoring. First, the monitoring process must have access to a meta- data construct that provides structural and behavioral information about a particular object. Second, the monitoring process must have a transparent mechanism to in- tercede during an object’s normal behavior and introduce additional behavior. The Reflective Monitoring (50) Design Pattern achieves reflective behavior through the Metaobject and Proxy constructs. A Proxy can be created to supersede a Target object through the information contained in a Metaobject. The Proxy will provide the same, functionality and interface to a Client as the Target did. In addition, the Proxy will provide trapping mechanisms such that additional behavior can be introduced at run time without affecting a Client. Note, many programming languages now provide support for meta-objects and proxies [19]. Typically. these constructs will facilitate reflective programming. It is inmortant, however. to check any constraints that might be imposed by such con- structs. Participants: 0 Client: This class is used to represent any component that needs to perform either internal or external monitoring. 0 InvocationHandler: This i1‘1terface must be supported by the Proxy object. This enables a Proxy to perform computations before and after a specific method is invoked 011 the Target object without affecting the functional logic. 0 Manager: Creates a Proxy object in response to a Client’s request to monitor a Target object. It is responsible for adjusting the necessary permissions so that the Proxy is able to retrieve a Target’s attributes. o Meta-object: Provides information about a particular type of object such as its structure, attributes, modifiers, and interfaces. The Meta-object must be regularly updated to reflect the most recent information. 0 Monitor: This class represents different monitoring schemes that can be invoked on a particular Target by a Proxy. For instance, a more complex monitoring scheme might include a chain of Proxy objects that first retrieve the attribute. 53 m0: .0> 8.8000 20> M 900.30 “0.30 .chm ”00030.0 585 “300.90. 0200050000090. AA00000030.VV D. AAm0N_.00._VV b-----— _ < 0:26 0.... “000.003.0000 . 8002.000 .385 ” 0&0... ”3002002300300 20> ” 0385 ”3.0852055 20> ” 3085 ”300850.030 20> ” 0085 358580.00 .985 H 3&0? ”31085030000 *zfi . 30. N 0502800 30. . 300000 3.8003 . . .. . . . * . .23 3000030. A 30. . @005 $0308 A 82003. . .085 . . 0.... 0030000 0003.333 30: . 20> ” Co3ia0oo<30m . 30. ” 3.000.200 chm ” Caxtow *z. . 30. H 03:30:30 \ . . wEbm a 000.0530w Al Ems... 3:030 0.3000. 0030000 30030030.). 00w0002 Figure 5.7: UML class diagram of the Reflective Monitoring (50) Pattern 54 encrypts the information, adds signal noise (covert monitoring), and then re- ports the value. 0 Proxy: This class supports the Target object’s functionality and interface. It is instrumented to introspect a Target’s attributes but not to alter them. In addition, the Proxy object also supports probing information so the desired attributes can be retrieved transparently. 0 Target: This is the object that will be monitored by a Client. It does not provide an interfar'e to the desired attributes. Behavior: Figure 5.8 shows a UML sequence diagram for an example of the Reflective Monitoring (50/ Pattern in a covert monitoring system. Specifically, Target does not provide any interface to the attribute that Client wishes to observe. A Monitoring Proxy object that supports the same interface as Target uses introspection to periodically check whether the attribute has changed or not. If the attribute has changed, then Monitoring Proxy invokes another proxy, Covert Proxy to add signal noise. This inserts random values into the channel to disguise possibly valuable information. After noise has been sent, the Monitoring Proxy returns the attribute value to the Client. Consequences: 1. Dynamic proxies can be used to monitor components, even those that might not have been known during design and compile—time. 2. Proxies can be chained together at run time to compose new monitoring behav- ior without intruding upon the functional logic. 3. Many programming languages (C++, Java, Lisp, Prolog, Python, Smalltalk) 55 ]--_--__--__ :f a- 9 E i V €002.28 —--—-lP---------- IIIIIIIIIIIIIIIII '. _--—----—---— waited... A :30. :3 h—_--- l.. €00 ”30.05.0305 . _ . . . x805 wl0.00..0_l0$. _ __ c. 0. a. Figure 5.8: UML sequence diagram example of the Reflective Monitoring ( 50 ) Pattern already support reflection mechanisms, thereby reducing the amount of effort required to implement reflective monitoring [19]. 4. Dynamic proxies incur a performance penalty for the extra level of indirection. Constraints: 0 Property 1: Globally, it is always the case that if Client requests to monitor a Target, then eventually Manager returns a Proxy object. [:1 ((Client.requestMonitor(Target)) —+ 0 Manager. createProxy (Target) ) This liveness property ensures that if a Client requests a proxy, then eventually one will be returned by the Manager object. Property 2: Globally, it is never the case that Proxy modifies an attribute value. Cl ((Proxy. serviceP(attr) —> O Target.serviceT(attr’)) —> attr == attr’ ) This safety property ensures that at no moment does a Proxy alter a value in Target. The Reflective Monitoring (50) pattern is not allowed to perform intercession upon the component it is monitoring. Related Design Patterns: 0 Sensor-Factory (41) Design Pattern: This design pattern can enable the monitoring of distributed components across a network. o Content-based Routing (59) Design pattern: This design pattern can submit the monitoring information to a conunon repos- itory where interested cmnponents can retrieve such information. o Indicator Design Pattern: This pattern is responsible for interpreting the results provided by a sensor and determining when a. reconfiguration is required. Known Uses: Reflection Design Pattern [11]. o InsECTJ (A generic instrumentation framework for collecting dynamic infor- mation) [15]. 0 Adaptive Exception Monitor [19]. 0 Java Reflection In Action [25]. 58 5.5.3 Content-based Routing ( 59) Pattern Classification: Structural - Monitoring. Intent: Route messages across a distributed monitoring infrastructure based on the con- tent of the message. Context: The Content-based Routing (59) Pattern may be used when: 0 Multiple clients need access to the same monitoring information. o The predominant monitoring scheme is passive monitoring (notifications are sent when a change occurs.) Motivation: Adaptive systems may contain heavily monitored components. If multiple mon- itors are requesting the same information from a given component, then a significant overhead may be incurred at the component. To decrease this impact, a single monitor can be deployed to observe a component and then submit the gathered information to a repository that is accessible to multiple clients. This approach reduces the mon- itoring burden placed on any given component while ensuring that clients still gain access to the required information. Figure 5.9 shows a use-case diagram of the Content-based Routing (59) Pattern. The goal of this pattern is to publish the monitoring information into a repository that can be accessed by different clients. Use-Case: Probe data Actors: Monitor Description: A monitor retrieves information from a given component. Includes: Publish data 59 System Probe data Monitor Publish data /@ Figure 5.9: UML use-case diagram of the Content-based Routing {59) Pattern Use-Case: Publish data Actors: Monitor Description: Submits the monitoring data to a repository that is accessible to clients. Includes: - Use-Case: Subscribe Actors: Client Description: A client submits a request to be notified when new monitoring information is available about a particular component. Includes: - 60 Use-Case: Unsubscribe Actors: Client Description: A client submits a request to disable further notifications when new monitoring information becomes available for a particular component. Includes: - Use-Case: Retrieve data Actors: Client Description: A client pulls the published data from the repository once it has been notified of its availability. Includes: - Structure: A UML class diagram for the Content-based Routing (59) Pattern can be found in Figure 5.10. The Content—based Routing (59) design pattern adds a level of indirection be— tween a Client and a Monitor. As a Monitor gathers information about a specific component, it sends it to a Server that is accessible to Clients. Each time new infor- mation is published by a Monitor, a Notification is generated to inform Clients that data is available. A Client retrieves the desired information from the EventService instead of continuously polling the monitored component. Participants: 0 Client: This class represents any component that needs to perform monitoring on some other component. 0 Entry: This class holds a unique identifier and the address of the Monitor that published the data. EventService can use this information to authenticate the validity of an entry. 61 20> H 30.5 H 0030.000 20> ” 2:805 a. .chm ”0:03.000330: w0Em n E0000 Al. 00030000 _ 20> N 300005 a 5005 ”000300033 l E0005 . 300:0 R wEhm H 800 0050000 00:000. 000000: . 000000002 . <.....o 20> H C302. 20> H 30.05 ”£00000: *5 20> H €05”— ¢ @0th ”03000003000: was Us l 0.9 ” 32.8002 ”5:233 05.000 H 6M” A 00.00 use A 0.9 H 02.0 0 .0500 “00002200 5:5. *..0 0.00.3 _ 003:5 _ _ wEbm “0200 *z. 83.00.). .0... 000000 20> ” C0338 . < . O chm 2000 20> H 300:0 ”035000 .925 a 330m. ”805.000 . 0305. w0.000>>8n. . 20> ” 30005 d .wEbm ”0603.000330: L 20> a 30.0mm ”$00.03 ~\*... 20> H 20:5 ”5 .mEhm ”230003800: 20> ” C0000 fi. 20> ” £00005 a. .mEbm 233.833 20> ” C>000 . _ 20> H 300000002 ”530.32. w0Em L000 20> ” €005 “5.0.0.05 ”0:02:33 00>00m 00.809005. Figure 5.10: UML class diagram of the Content-based Routing ( 59) Pattern 62 EventService: Mediates the comnumication between Monitors and Clients. Specifically. it manages the service by notifying a Client when a Monitor has published new information. Filter: Clients submit a Filter that indicates specific Monitors they want to ob- serve. The Filter is applied to different patterns and those that match contain the monitoring information desired. Forwarding Table: Holds a listing of every Client in the system and the monitoring feeds to which they are subscribed. The EventService uses the Forwarding Table to send notifications when new monitoring information has been gathered. Monitor: Represents any simple or complex sensor that is currently probing a component. Notification: A Monitor sends a Notification to the EventService whenever it publishes any new information. Likewise, a Notification is forwarded to a Client when new information is published on the Server. Pattern: Represents a signature that can be used to associate data with a par- ticular Sensor. The EventService applies Filters to Patterns to determine which data is of interest to a Client. Server: This class comprises a Forwarding Table and various Entry objects. Es— sentially, a Server holds the monitoring information for Clients to retrieve. Behavior: Figure 5.11 shows a UML sequence diagram for an example of the Content-based Routing (59) Pattern in a monitoring system. The Client object first sends a subscrip- tion notice to the Event Service. This subscription indicates which monitoring feed the Client is interested in receiving. Meanwhile, the Monitor gathers observations and 63 publishes them to the Event Service. To make the information available to Clients, the Event Service writes the monitoring i1’1formation to an Entry on the Server. Once the information is stored. the Event Service creates a Notification and it alerts interested Clients that new infm'mation from Monitor is available. The Client then informs the Event Service to pull the relevant information from the Server. Finally, the Event Service returns the requested information to the Client. Consequences: 1. Clients and the components being monitored are decoupled from each other. This separation facilitates the evolution of the monitoring infrastructure without affecting the functional logic. 2. The number of clients can change dynamically without affecting the component being monitored. 3. Network transparency enables various monitoring protocols to be incorporated. 4. Scalability issues may arise. Specifically, the repository where monitoring in- formation is placed can become a bottleneck. 5. Security concerns may need to be addressed. For instance, authentication might need to be performed on the content on the message rather than on its origins. Constraints: 0 Property 1: If a Monitor publishes data of interest to a Client, then the Client should even- tually be notified. Cl (( Monitor.publish(Notification) /\ Client.subscribe(id,Monitor)) 64 65 UML sequence diagram example of the Content-based Routing (59) . _ u u " ii uuuuuuuuuuuu .V . IIIIIIIIIIIIII 1 IIIIIIIIIIII V . . _ . . _ . _ . . . _ u . 8005.000 " A . . u m " AOV0>0E00 _ _ . _ . . u u uuuuuuuuuuuu .V _ . iilluilii" uuuuuuuuuuuuuuu n uuuuuuuuuuuuu Y _ _ _ . n _ 0l00000002 " . _ AA000000VV . . _ _ _ uuuuuuuuuuuuuu + ............ V _ _ . . u ‘ $303.03 " n . _ . Dlfiafifialv K . . .1 3.003533 . . . . . . _ _ . _ . . . _ _ _ . . . . . b I l.|lrl L _ Stow _ _ 83.005. _ _ 04ldl.l.>0 m000>m _ — 000. Figure 5.11: Pattern OEventService . not ify (Client) ) This liveness property guarantees that if a monitor publishes data and at least one client is subscribed to that monitor, then eventually a notification will be sent. Although this is a desirable property, currently it does not specify any timing constraints. 0 Property 2: Globally, it is always the case that if a Client receives a Notification, then the Client will eventually retrieve the information. D ((EventService.notify(Client)) —+ O (Client.retrieve(Entry)) This liveness property guarantees that if a client receives a notification from the event service, then it will eventually retrieve the updated information. This property ensures that a client retrieves new information whenever it is updated by a sensor. Related Design Patterns: 0 Observer Design Pattern: The Content-based Routing (59) pattern can be considered an extension of the Observer design pattern [26]. Specifically, the Observer design pattern pro— vides a one-to—many notification mechanism. The Content-based Routing ( 59) pattern, on the other hand, provides a many-to—many notification mechanism. 0 Sensor-Factory (41) Design Pattern: This design pattern can enable the monitoring of distributed components across a network. 66 o Adaptation Detector (88) Design Pattern: This pattern is responsible for interpreting the results provided by a sensor and determining when a reconfiguration is required. Known Uses: 0 Rainbow Adaptation Framework [30]. o Siena Routing [43]. o JAMM lV‘Ionitoring System [77]. o Rebeca [83]. 67 5.5.4 Case-based Reasoning (68) Pattern Classification: Structural - Decision-Making. Intent: Apply rule—based decision-making to (.letermine how to reconfigure the system. Context: The Case-based Reasoning (68) Pattern may be used when: 0 The system must determine which adaptation to perform automatically. 0 The criteria for reconfiguration is not complex and can be expressed through if-then-else statements. Motivation: Dealing with decision-n‘raking internally through constructs that trap errors at the implementation level is undesirable for two main reasons [27]. First, the overall context of what triggered the adaptation event is usually lost at such fine—grained levels. Second, evolving or correctng such a decision-making process is difficult to accomplish because the cause-effect relationships for triggers and events are tightly coupled to the functional logic. The Case-based Reasoning (68) design pattern sep- arates the decision-making logic from the functional logic of the application. Specif- ically, it. centralizes all the conditions and responses for reconfiguring a system such that. they do not crosscut the functional logic. This separation of concerns results in an external and flexible decision-making architecture that facilitates change. Figure 5.12 shows a use-case diagram of the Case-based Reasoning ( 68 ) Pattern. The main goal of the Case-based Reasoning (68) design pattern is to determine which reconfiguration to perform. 68 Figure 5.12: UML use-case diagram of the Case-based Reasoning ( 68 ) Pattern System <> ’ I Select reconfiguration Store trigger lnf re ce Engine Apply ' rules <> Select action Use-Case: Select Reconfiguration Actors: Inference Engine Description: Determine which available reconfiguration will yield the desired behavior in the system. Includes: Apply rules. Use-Case: Apply rules Actors: - Description: Determine which cause and effect relationship holds true within the set. of rules. Includes: Select action. 69 Use-Case: Select Action Actors: - Description: Chooses a reconfiguration plan based on what triggered the adaptation and the rule that describes the cause and effect. relationship. Includes: - Use-Case: Store trigger Actors: Inference Engine Description: Stores the cause of the adaptation request and the reconfiguration plan that was selected. The Inference Engine can use this information to learn new rules in the future. Includes: - Use-Case: Learn rules Actors: Inference Engine Description: Reviews previous adaptation causes and reconfiguration responses to discover new rules to apply in the future. Includes: - Structure: A UML class diagram for the Case-based Reasoning ( 68 ) Pattern can be found in Figure 5.13. The Case-based Reasoning (68) design pattern separates the decision-making logic from the monitoring, reconfiguration, and functional logic. During execution, some monitoring event (not shown in this design pattern, refer to Adaptation Detector (88) for more information) will generate a Trigger and forward it to the Inference Engine. The Inference Engine comprises a set of Fixed Rules, a Trigger Repository, and a Learner algorithm. A Trigger is applied to a Fixed Rules set, a Decision is generated, and the result is stored in a Log so the Inference Engine can learn new rules. Since the Case-based Reasoning (68) design pattern centralizes all conditions and rules 70 regarding a reconfiguration plan, a Rule can be readily added, modified, or removed. Participants: Decision: This class represents a reconfiguration plan that will yield the desired behavior in the system. Fixed Rules: This class contains a collection of Rules that guide the Inference Engine in producing a Decision. The individual Rules stored within the Fixed Rules can be changed at run time. Inference Engine: This class is responsible for applying a set of Rules to either a single Trigger or a history of Triggers and producing an action in the form of a Decision. Learner: Applies on-line and statistical-based algorithms to infer new Rules in the system. This is an optional feature of the Case-based Reasoning (68) design pattern. Log: This class is responsible for recording which reconfiguration plans have been selected during execution. Each entry is of the form Trigger-Rule-Decision. Rule: Represents a relationship between a Trigger and a Decision. A Rule eval- uates to true if an incoming Trigger matches the Trigger contained in the Rule. Trigger: This class contains relevant information about what caused the adap- tation request. A Trigger should at least provide information about the error source, the timestamp at which the error was observed, the type of error ob- served and whether it has occurred before or not. Additional information may be included as required. A Trigger is invoked by the Adaptation Detector ( 88) design pattern. 71 20> ” 207.600 6 63¢ u .watk ”two. *2 :2280 u cocoa Emma. ” omzwo 23m *.._ W _ Eo>m AAed bmaeevv 23m H Come. “83%;. won _ > €502 ocfioE _ _ 20> ” CEmo. 20> U 328% \ moxoi: .8208 H .8396 H5 _ hop—LGQJ chm n ENE Eo>m n 9.00 mo_:~_nexi :oEooQ waE. _ > *z. *..o >30 $2603 moiam 3;on _ _ _ :2280 H Ccocoml 20> u 0520 20> ” CowwE. ”otowwE mommooom 20> U Cowwch Nov—oceans U_O> H 3:3.— o:_w:m8:2£:_ o‘\ 2: H 309:3 chm u .0an bozmoaowtomwth Figure 5.13: UML class diagram of the Case-based Reasoning (68) Pattern 72 o Trigger Repository: Contains a history of Triggers. This history can be used by the Learner class to identify trends that may warrant further reconfigurations. Behavior: Figure 5.14 shows a UML sequence diagram for an example of the Case-based Reasoning (68) Pattern in a simple adaptive system. A Trigger alerts the Inference Engine that an adaptation request has been submitted (see Adaptation Detector ( 88) Pattern for more information.) The Inference Engine uses the information provided by the Trigger to decide which reconfiguration plan will yield the desired results in the system. The Inference Engine applies a set of rules stored in the Fixed Rules object until a matching rule is found. Inference Engine then creates a Decision that includes the selected reconfiguration plan. The Inference Engine then logs the resulting action in the Log. In addition, the Inference Engine also stores the Trigger in the Trigger Repository for further analysis. Consequences: 1. The decision-making logic is separate from the monitoring logic, the reconfigu- ration logic, and the functional logic, thereby facilitating the evolution of rules and actions at run time. 2. New rules can be learned dynamically to accomrncxlate new reconfiguration scenarios. 3. If many reconfiguration scenarios are possible, then scalability issues such as overlapping rules may arise. 4. Rule-based decision-making can only select reconfigurations that are known prior to the current execution point. . . u . _ . . . . I _ u _ . . _ . _ . ............. 1-----l:---L_-------------J------------V . . _ . . _ . _ . . . . _ . . . . _ F _ _ “ Engage " u n . . . _ _ u . . . . . _ _ _ ............. .r .............. 1 ............ V _ _ . . _ . _ . _ . . . . . _ . . _ _ _ . _ _ . _ n _ _ — 4 . 6 u .3w0. " _ u . _ . . _ _ . _ . _ _ IIIIIIIIIIIII 1 IIIIIIIIIIII v . _ . _ _ _ . _ _ . . _ _ . . _ _ . . _ _ . _ _ _ . _ . _ u . _ _ . . _ . _ u . _ u _ _ _ _ _ Il|.|l| _ _ u u _ 51$qu . u _ A “ 43:8va " . . . _ _ _ . . _ . IIIIIIIIIII iv _ _ _ _ _ . _ _ _ _ _ _ _ . _ _ _ _ . _ _ . . . e m can _ _ . [l . _ _ . Aorowwt. . l . _ . . .. 538$— . . . . — k - - Haww Fr. w All A _ we..__ls~_ Ice/Ml“. _ — ulfiscm eo:2&£ _ _ Pawns: H Figure 5.14: UML sequence diagram example of the Case-based Reasoning (68) Pat- 74 tern Constraints: 0 Property 1: Globally. it is always the case that if a Trigger is received. then Inference Engine eventually produces a Decision. D ( InferenceEngine.trigger O |nferenceEngine.action() ) This liveness property ensures that a decision is eventually produced by the rule-based decision making process. One way to ensure this property holds is by creating a default conditional-action pair. At the very least, this default conditional could notify the system administrator that an event occurred and no matching reconfiguration plan was found. 0 Property 2: Globally, it is always the case that if Inference Engine produces a Decision, then Log will eventually record the events. El ( lnferenceEngine.action() —> O Log.log(Trigger, Rule, Decision) ) This liveness property ensures that every reconfiguration selected by the rule- based decision-making process is eventually logged. This property is desirable because it would enable developers to keep track of how the system is executing at run time in response to changing requirements and environmental conditions. Related Design Patterns: 0 Adaptation Detector (88) Design Pattern: 75 This design pattern can be used to interpret monitoring information and deter— mine when a reconfiguration is required. The notification can be used by the Inference Engine to select a reconfiguration plan. 0 Component Insertion (115) Design Pattern: This design pattern can be used to safely insert a component at run time ac- cording to the reconfiguration plan selected by the rule-based decision-making process. 0 Component Removal (125) Design Pattern: This design pattern can be used to safely remove a component at run time according to the reconfiguration plan selected by the rule-based decision-making process. a Server Reconfiguration (135) Design Pattern: This design pattern can be used to safely reconfigure a server architecture at run time. The specific reconfiguration plan to enact those changes can be selected by the rule-based decision-making process. 0 Decentralized Reconfiguration (145) Design Pattern: This design pattern can be used to safely reconfigure a decentralized architecture at run time. The specific reconfiguration plan to be enacted by a particular component can be selected by the rule—based decision-making process. Known Uses: a Decentralized self-adaptive component-based system [6]. 0 Rainbow Adaptation Framework [27]. 0 Architectural Approach to Autonomic Computing [41]. 76 0 Earth Management Application (Ontology-based mobile agents) [71]. o Kinesthetics eXtreme (KX) Framework [79]. 77 5.5.5 Divide and Conquer ( 78) Pattern Classification: Structural - Decisitm—h’laking. Intent: Systematically decompose a complex reconfiguration plan into simpler reconfig- uration plans. Context: The Divide and Conquer ( 78) Pattern may be used when: 0 multiple reconfiguration plans need to be applied to achieve the desired behav— ior. o a reconfiguration plan involves dependencies between distributed components. Motivation: Adaptive systems often comprise distributed components. Each component im- plements a part of the desired behavior of the system. Some of these components may include fragments, or parts of the component that are associated with different pro- cesses in the distributed system [8]. While adding or removing components, not all fragments of a component are added or removed simultaneously. This asynchronous behavior may lead to situations in which some processes have added/removed the component fragments while some have yet to do so [9]. To avoid problems, depen- dency relationships among the fragments should be handled correctly While adding and removing fragments. In other situations, multiple reconfigurations need to be per- formed in succession to achieve the overall desired behavior. To avoid these problems, dependency relationships between the different reconfiguration plans must be handled carefully. The Divide and Conquer ( 78) design pattern first determines dependency relations between different component fragments and then creates an ordering that will safely reconfigure the system by preserving the dependency relationships. 78 Figure 5.15 shows a use-case diagram of the Divide and Conquer ( 78) Pattern. The main goal of this design pattern is to decompose a complex reconfigtu‘ation plan into simpler reconfiguration plans that can be applied by the adaptive system. System Interpret task <> D eterrnine reconfiguration o Ian \ \\ <> \ \\ Calculate \\ dependencies Decision , \l d making <> \ process \ \ Select \ goal \ Order reconfiguration Figure 5.15: UML use-case diagram of the Divide and Conquer ( 78) Pattern Use-Case: Determine reconfiguration plan Actors: Decision-making process Description: Find a sequence of reconfigurations that will yield the desired behavior. The reconfiguration plan must specify the sequencing of each step. Includes: Interpret task, Calculate dependencies, Order reconfiguration 79 Use-Case: Interpret task A UML class diagram for the Divide and Conquer ( 78) Pattern can be found in Figure 5.16. The Divide and Conquer ( 78) design pattern provides an approach for systematically decomposing tasks. of reconfigurations to determine the specific sequence of reconfiguration steps that will safely yield the desired behavior in the application. The overall approach is split into two main tasks. First, various sets of existing reconfiguration plans are searched and analyzed to determine if they can be combined to reconfigure the system as needed. Second, if a combination of existing reconfiguration plans satisfy the adaptation requirements, then any dependencies between the reconfiguration plans Actors: - Description: Analyze the reconfiguration plan goal, its constraints, and requirements. Includes: - Use-Case: Calculate dependencies Actors: - Description: Determine if there are any specific dependencies between reconfiguration plans. Includes: - Use-Case: Order reconfiguration Actors: - Description: Creates a sequence of steps that will safely reconfigure the system in order to provide the desired behavior. Includes: - Use-Case: Select goal Actors: Decision-making process Description: Choose a reconfiguration plan to analyze. Includes: - Structure: 80 This design pattern analyzes combinations are determined. The reconfiguration plans are then combined in a specific sequence of reconfiguration steps to yield the overall system adaptation. Participants: 0 Dependency Analysis: Determines which Tasks are dependent upon other Tasks. This information can be used by the Planner to generate a sequence of Tasks that will accomplish the main Goal. 0 Goal: This represents the adaptation requirements that must be satisfied by applying a set of recorrfigurations. o Inference Engine: The Inference Engine is responsible for resolving how a given Goal can be decomposed into a set of Tasks that satisfy the adaptation require— ments. This class makes use of the Knowledge Base (KnowledgeBase) and Rule Base (RuleBase) to perform either Informed or Uninformed forms of resolution and searching. o Informed: A set of informed heuristics that can guide the resolution process carried out by the Inference Engine. 0 KnowledgeBase: The Knowledge Base represents axioms known to the system. These axioms are used by the Rule Base to perform resolution tasks. 0 Lexer: This optional class is responsible for convertng data into a sequence of tokens. Specifically, both adaptation requirements and reconfiguration plans are stored in the system in various formats such as text, models, and so forth. The Lexer converts otherwise meaningless data into tokens recognizable by the system. 0 Parser: This optional class analyzes the sequence of tokens produced by the Lexer. It is responsible for transforming Goals into data that can be directly 81 20> n Ccouwomz 20> U 0:033 Us”. H 382“mb Sam 0 £08 32:8:— eoEOchD emwmownflsocx 20> ” Ewan—L ”SomcomEOUou 20> n CowuoE * a @382 * _ 2:”. H Cmo_=m8w 2am H 8:: ommmo_=m V" xmfl. ” C0382 oiwcmfiocoaflfi >_ _ 20> ” Cozom 0x02: 20> “ 32¢. “523028 .8208 H Qmfl. 56:33 .— 29 U came Heroes ll mom: SEEK 82605 '— 8a“. AAoa bfimeVV 23m AAoabfiaevv 58.009 ” Qmfl. uroxooauéfimcg 0.8... n 38,—: ”cone—=28 flmbmc<>ocoecomofl _ moficwwuo * _ 52009 U 852;. momomEOoee 20> H 93.3 .5208 H 00.02? 58mm Exes— *2 z: ” 8:268 58.08 H coHoEEoo xmfl. *.._ *:_ 52009 H upBEEOo .moo Figure 5.16: UML class diagram of the Divide and Conquer (78) Pattern 82 used by Solver and Inference Engine. Planner: Takes a set of dependencies between Tasks and applies an ordering that will safely solve the Goal without violating dependencies. RuleBase: Represents conditionals and actions known by the system that can be used to evaluate and select Tasks to solve a Goal. Note, this class is not related to the set of rules in Case-based Reasoning (68). Solver: This class is responsible for organizing the overall task decomposition process. It invokes the Lexer and Parser classes to interpret Goals. It also invokes the Inference Engine and fine-tunes the search procedure until a sequence of Tasks that solve the Goal is found. Task: This class is used to represent a reconfiguration plan. Ideally, by applying a series of Tasks the Goal will be satisfied. Uninformed: A set of uninformed approaches that exhaustively search the solu- tion space. These approaches do not exploit any particular knowledge that may optimize the search. Behavior: Figure 5.17 shows a UML sequence diagram for an example of the Divide and Conquer ( 78) Pattern. The Solver coordinates the process of task decomposition by first invoking the Inference Engine. The Inference Engine proceeds to retrieve known facts about Goals and Tasks from the Knowledge Base (KB). In addition, the Inference Engine also retrieves a set of rules from the Rule Base (RB). The Inference Engine then proceeds to resolve the known facts with the available rules. Once a set of Tasks have been identified, the Inference Engine invokes the Dependency Calculator to determine an ordering. The Dependency Calculator uses the Planner object to create a sequence of steps in which the Tasks must be solved. 83 Consequences: 1. CW More complex adaptation requirements can be satisfied by reusing and compos- ing multiple reconfiguration plans. Reconfiguration plans that are not dependent upon each other can be paral- lelized to enhance performance. Dependencies among the reconfiguration plans will not be violated by the gen- erated sequence. . It may not be possible to satisfy all adaptation requirements by decomposing them into sequences of reconfiguration plans. There is an increased overhead in determining how to reconfigure the system. Constraints: 0 Property 1: Globally, it is always the case that a proposed set of Tasks satisfies the Goal. El ((DependencyCalculator. constraintChecker (Tasks) = ’ True ’) —> 0 (Goal . completed= ’ True ’ )) A set of reconfiguration plans must correctly reconfigure the system without violating any dependencies. If such a plan is found, then eventually the goal should be satisfied. Related Design Patterns: 0 Architecture-Based (.97) Design Pattern: This design pattern can be used to represent a system and its reconfiguration plans as architectural models. Models that satisfy the adaptation requirements indicate how the system should be reconfigured. 84 .. Essences .. 8.56:8“. _ _ . . . _ _ _ _ _ . . LI b all: .85 IIIII '. fi---- 9 Saute—:0 A ll . . . _ _ . _ _ _ . . . . . . . . _ _ . . _ _ _ _ . - an .2». “GER fl ll'l||""l"l C xmmtoaiofio -------—---—_----------------—-T-—-—-----. 39:08.. /. )2 CSoEEw A [Mi 3809:0020 L . l—l _ _ . . H _ M3 cm 8.5.8.:— _ .o>_0m _ Figure 5.17: UML sequence diagram example of the Divide and Conquer (78) Pattern 85 TradeOfi-Based (106) Design Pattern: This design pattern can be used to select a reconfigm'ation plan that best bal- ances multiple objectives. Complex reconfiguration plans can be decomposed by the Divide and Conquer (78) pattern. Component Insertion ( 115) Design Pattern: This design pattern can be used to safely insert a component at run time. Component Removal (125) Design Pattern: This design pattern can be used to safely remove a component at run time. Server Reconfiguration (135) Design Pattern: This design pattern can be used to safely reconfigure a server architecture at run time. If the reconfiguration plan is complex, it can be decomposed by the Divide and Conquer (78) pattern. Decentralized Reconfiguration (145) Design Pattern: This design pattern can be used to safely reconfigure a decentralized architecture at run time. Any component can decompose a complex reconfiguration plan through the use of the Divide and Conquer (78) pattern. Known Uses: Task Decomposition [1]. Rainbow Adaptation Framework [27, 29]. Care-O-Bot II (uses metric-FF) [40, 45]. An Architectural Approach to Autonomic Computing [41]. Simple Hierarchical Ordered Planner (SHOP‘Z) [65]. 86 o Pro-(wtive Control, Monitoring and lVIaintenance (PCMM) lV’Iodules for Au- tonomous Systems [78]. 0 Task Control Architecture (TAG) for Mobile Robots [76]. 87 5.5.6 Adaptation Detector ( 88) Pattern Classification: Structural - Decision-Making. Intent: Interpret monitm'ing data and determine when an adaptation is required. Context: The Adaptation Detector ( 88 ) Pattern may be used when: 0 A11 adaptive system must automatically determine when an adaptation is re- quired. Motivation: Adaptive systems need to determine when an adaptation is required. Usually, adaptive systems employ monitors to observe both the system’s internal behavior as well as its environment. Simple sensors typically provide raw data feeds that must be interpreted by the system to be of any use. Once interpreted, this information can be used to identify situations where observed behavior deviates from expected behavior. If the Components are distributed across a network, accomplishing this task becomes increasingly difficult because the system must track where the problem originated [30]. The Adaptation Detector ( 88 ) design pattern retrieves and analyzes relevant data from one or more sensors and generates a health indicator value. The health indicator value is determined by comparing the observed behavior versus the expected behavior. As soon as a deviation is identified, the decision-making process is notified with all the relevant information available so it may determine which reconfiguration plan to apply. Figure 5.18 shows a use-case diagram of the Adaptation. Detector ( 88) Pattern. The main goal of this design pattern is to determine when an adaptation is required. 88 System Pull information / ’ <> Interpret information <> \ \ Assess situation Listen for Decrsron information making process Figure 5.18: UML use-case diagram of the Adaptation Detector ( 88) Pattern Use-Case: Interpret information Actors: Decision-making process Description: Assign meaning to almonitoring feed. Includes: Pull information, Listen for information Use-Case: Pull information Actors: - Description: Actively retrieve the monitoring information from a passive sensor. Includes: - 89 Use-Case: Listen for information Actors: - Description: Passively wait for a notification that an event has occurred. Includes: - Use-Case: Assess situation Actors: Decision-making process Description: Evaluates the monitored values against certain thresholds. If the values exceed those thresholds, then an adaptation is required. Includes: - Use-Case: Send trigger Actors: Decision-making process Description: Notify the decision-making process that an adaptation is required. The trigger should include information about what triggered the adaptation request. Includes: - Structure: A UML class diagram for the Adaptation Detector (88 ) Pattern can be found in Figure 5.19. Adaptive systems must determine when observed behavior deviates from ex- pected behavior. These situations typically require some form of adaptation. The Adaptation Detector ( 88) Design Pattern acts as a gateway between the monitor- ing and decision-making processes. Specifically, the Adaptation Detector ( 88) Design Pattern is responsible for interpreting monitoring values and deciding when a recon- figuration is needed. To accomplish this objective, a Health Indicator is associated with a specific Sensor. The Health Indicator can be used with either passive or active Sensors. Once the Analyzer determines that a Threshold has been exceeded, the Health Indicator generates a Trigger to issue an adaptation request. Participants: 90 30.605 *.._ .E H 2...? See .. _ > * .292... 20> . 22.5 ”3.232.: «so H tomcom ”mvfiaoaow chm U 2853 wEbm u .093 «ED U 3:25 98 u 3...... 580m 22 H cease .3580 * - .5208 U 2288:; a 525 ”328800 .E H :E: B~ba=< _ .. _ 288.5. _ > 2.31.3 _ 20> . Cowwcrr ”:88 .E H 8». 5wth H Cnommthogocew _ zr wEbm ” aESmoE: .5208 N 3228:3398 ecom \ wEbm H 858 532—8328: .528 H 8380.. Lemme... Figure 5.19: UML class diagram of the Adaptation Detector (88 ) Pattern 91 o Analyzer: This class is responsible for deciding when observed behavior deviates from expected behavior. Specifically, the Analyzer compares the interpreted values from a Sensor against discrete values stored in a Threshold. An adaptation is warranted when observed values exceed a given threshold. 0 Data: Represents the values reported by a Sensor. The basic data types sup- ported include integers. doubles, and booleans. Other data types may be used as well in conjunction with a complex Sensor. 0 Health Indicator: Coordinates the process of interpreting a Sensor’s values and determining whether an adaptation is required. 0 Observer: Interacts with a specific Sensor. The Observer is responsible for inter- preting Data produced by a Sensor. This process is required before the Analyzer can evaluate the monitoring information against certain Thresholds. 0 Sensor: This class represents any type of simple or complex Sensor that is capable of reporting integers. booleans, or floats. Complex Sensors that produce other types of values can be used with the Adaptation Detector ( 88) Design Pattern, but may need further customization according to the computational resources provided. 0 Threshold: Stores discrete values that represent the boundaries between normal and abnormal behavior. 0 Trigger: This class contains relevant information about what caused the adap- tation request. A Trigger should at least provide information about the error source, the timestamp at which the error was observed, the type of error ob- served and whether it has occurred before or not. Additional information may be included as required. 92 Behavior: Figure 5.20 shows a UML sequence diagram for an example of the Adaptation Detector (88) Pattern in an adaptive system. The Health Indicator first invokes the Observer to gather and interpret data from the Sensor. A Sensor periodically produces Data. which may contain information about the systems internal behavior or the en- vironn’ient surrounding the application. The Observer pulls Data from the Sensor and interprets it. Once the information has been interpreted. the Health Indicator invokes the Analyzer to compare. those values against some Thresholds. In this particular sce- nario. the Threshold is exceeded and the Health Indicator generates and sends a Trigger to notify the decision—making process that an adaptation is required. Consequences: 1. This design pattern separates the monitoring and decision-making processes from each other. Changes in one process should not affect the other. 2. The specific threshold ralues used to represent the boundaries between normal and abnormal behavior are kept within the Adaptation Detector (88) design pattern and not dispersed throughout the source code. This facilitates evolving the system at run time. 3. If many monitoring probes are deployed, then scalability issues may arise. Specifically, this design pattern adds a level of indirection between monitor- ing and decision-making processes which could add a considerable time delay. Constraints: 0 Property 1: Globally, it is always the case that if Observer obtains monitoring information, then Analyzer will eventually compare the data against a specific Threshold. 93 . _ n m u m m . . . _ . u _ . _ _ _ . _ _ . _ . _ _ u _ u _ _ 39.8 _ u _ u u IIIIIIIIIIII WIIIIIIIIIIITIIIIIIIIIIIIIIIII_IIIIIIIIIIIIIIIJIIIIIIIIIIIIIIIV _ . _ . _ . _ _ _ . _ _ _ . _ _ u u u " clowa—t L M u M M AAoamocovv“ " u u u u u u l .......... ._. ................. a ............... .1 ............. v _ _ _ _ . _ _ _ _ _ _ _ . _ _ . _ _ n u u L‘ l . m _ . J.L .3 227.05% 32m :50" u . m u W Li uuuuuuuuuuuu .V n u n . " wl iiiiiiiiiiiii Y n uuuuuuuuuuuuuu l _ _ _ u a m _ as . a Tl _ AAoEocovv ll " “ C:a " H 4L - Amvflmmuow _ . . [.L n t. n l. _ cl~»l_m=< _ clomcom H m _ _ cloZoBO _ _ cloaofifi 5.3: _ Figure 5.20: UML sequence diagram example of the Adaptation. Detector { 88 ) Pattern 94 El ( Observer.getData(Sensor) —> O Analyzer. compare (Data , Threshold) ) This property is desirable because it guarantees that values reported by the monitoring process will be compared against. thresholds that define what con- stitutes normal 'bel'iavior from abnormal behavior. Some application domains may want to further strengthen this property by imposing a timing constraint. 0 Property 2: Globally, it is always the case that if a Threshold is exceeded, then eventually a Trigger will be sent to the decision-making process. Cl ( Analyzer.compare (Data) . ’True’ —+ O Healthlndicator.send(Trigger) ) This property is desirable because it ensures that whenever a constraint viola- tion is detected, the decision-making process will be notified so it may select an appropriate reconfiguration plan. Related Design Patterns: 0 Sensor-Factory (41) Design Pattern: This pattern can be used to deploy sensors across a distributed environment and probe components. a Reflective Monitoring (50) Design Pattern: This design pattern can be used to determine when a monitored attribute ex- ceeds a specific constraint. 0 Content-based Routing ( 59) Design Pattern: 95 The Adaptation Detector (88) pattern could subscribe to the Content-based Routing (59) pattern notification service. Whenever a monitoring value is pub- lished. the Adaptation Detector (88) pattern is notified of the update. Case-based Reasoning (68) Design Pattern: This pattern can be applied to satisfy simple adaptation requirements that tyI.)ically involve only one reconfiguration plan. Architecture-Based (97) Design Pattern: This design pattern can be used to represent a system and its reconfiguration plans as architectural models. Models that satisfy the adaptation requirements indicate how the system should be reconfigured. TradeOfi-Based (106) Design Pattern: This design pattern can be. used to select a reconfiguration plan that best bal- ances multiple objectives at run time. The Adaptation Detector (88) pattern could be used to detect changes that warrant an adaptation. Known Uses: SmartEvents (part of XUES) [37]. PBX - Design Patterns for Software Health l\'lonitoring [59]. Java Agents for Monitoring and Management (J AMINI) - event gateway [77]. Kinesthetics eXtrcme (KX) [79]. 96 5.5.7 Architecture-Based (97) Pattern Classification: Structural - Decision-hrlaking. Intent: Provide an architecture-based approach for selecting reconfiguration plans. Context: The A'rchitect’ar'e-Based (97) Pattern may be used when: 0 Reconfiguration plans are expected to change regularly. o Reconfiguration plans should be reused. Motivation: Low-level adaptation mechanisms that are tightly coupled with application code present two major challenges to developers [29]. First, it is difficult to correctly de- termine the true source of the problem and the remedial action at such detailed levels of abstraction. Second, adaptation policies are not localized, thereby hindering their evolution. Architectural perspectives, on the other hand, shift focus away from source code to coarse grained components and their interconnections [67]. Architectural ap— proaches externalize adaptation and facilitate the reuse of reconfiguration plans. As an application adapts and evolves, however, preserving an accurate and consistent model of the system and its constituent parts becomes increasingly difficult. The Architecture-Based (97) Design Pattern manages the evolution of an architectural model while preserving a correspondence between the model and the implementa— tion. Specifically, architectural models are used to represent both the current state of the system as well as the possible target systems after a reconfiguration has been applied. Figure 5.21 shows a use-case diagram of the Architect'ar‘e-Based (97) Pattern. 97 The main goal of this design pattern is to manage the evolution of a system’s archi- tectural model. Evolution Manager Remove model Figure 5.21: UML use-case diagram of the Architecture-Based (97) Pattern Use-Case: Reflect Actors: Evolution manager Description: Update the architectural model representation of the system such that it is consistent with the system implementation. Includes: - 98 Use-Case: Select model Actors: Evolution manager Description: Select an architectural model of the system that satisfies the adaptation requirements. Includes: Differentiate Use-Case: Add model Actors: Evolution manager Description: Insert. a new architectural model of the system into the repository. Includes: Differentiate Use-Case: Differentiate Actors: - Description: Determine the difference between two architectural models. This can be used to either build a reconfiguration plan or avoid duplicate architectural models in the repository. Includes: - Use-Case: Remove model Actors: Evolution manager Description: Delete an architectural model from the repository. Includes: - Structure: A UML class diagram for the Architectare-Based (97) Pattern can be found in Figure 5.22. Architectitre-based approaches for self-adaptive systems typically perform two key tasks when selecting a reconfiguration strategy [29, 67]. First, the architectural models must be kept consistent with respect to the system‘s current implementation. Second, candidate reconfiguration plans must be evaluated against specific constraints to determine if they satisfy the adaptation requirements. The Architecture-Based (97) Design Pattern accomplishes the first task by introducing an Evolution Manager that 99 updates the current architectural model in response to the applications evolution. To accomplish the second task, a Repair Engine searches through a collection of archi- tectural models and checks whether any of them satisfy the adaptation requirements. If a model that satisfies the specified requirements is found, then the key differences between the source and target architectural models are identified. Identifying these differences will facilitate the development of a reconfiguration plan that will adapt the application as needed. Behavior: Figure 5.23 shows a UML sequence diagram for an example of the Architecture- Based (97) Pattern in an adaptive system. In this specific scenario, the Evolution Manager updates its architectural model of the implemented system. The Evolution Manager begins the reconfiguration selection process by first invoking the Repair En- gine to search for an architectural model that satisfies the adaptation requirements. The Repair Engine retrieves architectural models from the ArchitecturalRepository and then uses the Constraint Checker to determine whether that architectural model satis- fies the required properties. Once an architectural model is found, the Repair Engine determines what are the key differences between the source and target architectural models. With this information, the Evolution Manager can suggest a reconfiguration plan that will correctly adapt the application. Participants: 0 Architectural Model: Each model represents a specific configuration of the entire application. The overall observable behavior results from the different configu- rations of both Components and Connectors. 0 ArchitecturalRepository: Provides access to a collection of Architectural Models. 0 Component: These are responsible for implementing an application’s behavior. 100 .E “ Ewes .E ” 08:8 szm ” oEm: E. n 2 5.3550 ... _ mofioEsEEOo chm ” 2cm: 2: H E EocanoU *.._ MV_ _WV *:_ atonem— ” methane; mcEm a 08m: 3825202202 seozassszoi ” 0.2522032 528; “ 20822352202 ”EBB—22¢ 22 U 2082582292 ”52982228 22 n 2082520223. E3228." bo._momom_8=.oo::oc< 8:9.an _ _ 20> a tonomous— ”92:0602828 20> n A_oeo2_83o2£2< "NE _ bemoan ARESmuVV see—con ” 3:235 Havoc ._ov02_82o2£2< ”Evafiflacovxooso E n =5: coxoonuafiflacou _ 40825202292 :Eseseoee $302: ofiwcmtaom 20> “ 20823303392 “Egg—23052 Bo.» H 360:8 20> ” 2252.83o228< ”5:252:85 53.08 H :32 commcmEcozigm Figure 5.22: UML class diagram of the Architecture-Based ( 97) Pattern 101 " . . u u . . . . . . u _ . . _ _ u . 1r _ . . _ _ . . . . . . . . _ _ . _ . _ . _ . _ . . _ . IIIIIIIIIIII V _ - . u _ . _ Essen—52.35:. " " ANE m 25.2 n “ .Esséeée _ — u n IIIIIIIIIIIIIII J IIIIIIIIIIIIIII .v _ u _ . n . _ O n u _ $72 . _ “ 48156520 bxoogo . iiiiiiiiiiiiii V n u _ _ _ _ . _ I m u . CBS—232:2 . . . . q q _ _ u u _ . . _ _ . n u _ u _ n “ 33:38:80.3 _ n n . . _ . _ _ . . . _ . _ _ u u . u u u u “ 360:8 " . . .2? fl “ . .exoocu __E:.o2_;8< _ Eficiccb .INl._|~.m Figure 5.23: UML sequence diagram example of the Architccture-Based (97) Pattern 102 o Connector: These represent the various interconnections between Components in the system. c Constraint Checker: The main function of this class is to evaluate whether a particular Architectural Model satisfies a set of specific adaptation requirements. 0 Evolution Manager: This class oversees the two primary goals of the Architecture- Based (97) Design Pattern. First, monitoring information provided by the system (see Adaptation Detector (88) Design Pattern for more information) is used to update the current architectural model representation of the system. Second, the Evolution Manager guides a constraint—based approach at selecting the appropriate reconfiguration plan. 0 Repair Engine: This class is responsible for searching and extracting Architectural Models from the Model Repository. It also supports the addition and removal of Architectural Models, thus facilitating the evolution of reconfiguration plans. Searches and extracts Architectural Models from the ArchitecturalRepository. It also supports the addition and removal of Architectural Models at run time. To differentiate between different Architectural Models, the Repair Engine employs graph-based algorithms to identify structural differences. Consequences: 1. Reconfiguration plans are localized, thus facilitating the evolution of reconfigu- ration strategies at run time. 2. In general, architectural models are not application specific, thereby facilitating the reuse of reconfiguration plans between different systems [29]. 3. A computational overhead is introduced by searching and evaluating potential reconfiguration models when adapting the system. 103 Constraints: 0 Property 1: Globally, it is always the case that if a particular model does not satisfy some requirement, then that model is never selected for execution. El ( ConstraintChecker.checkConstraints(m,reqs) . ’False’ —> -1 RepairEngine.selectModel (m) ) This safety property guarantees that the system will not select a reconfiguration plan that violates a specific property. Related Design Patterns: 0 Adaptation Detector (88) Design Pattern: This pattern can be applied to determine when a reconfiguration is required. It can also localize the source of the problem and guide the search for a reconfig- uration plan. 0 Divide and Conquer ( 78) Design Pattern: This pattern can be applied to decompose a complex reconfiguration plan into simpler tasks. 0 Component Insertion ( 115) Design Pattern: This pattern can be used to safely insert. a component at run. time. 0 Component Removal (125) Design Pattern: This pattern can be used to safely remove a component at run time. 0 Server Reconfiguration (135) Design Pattern: 104 This pattern can be used to safely reconfigure a server architecture at run time. The A'I'chitecturc-Based (97) pattern can be used to represent the server architecture. Decentralized Reconfiguration (145) Design Pattern: This pattern can be used to safely reconfigure a decentralized architecture at run time. The Architecture—Based (97) pattern can be used to represent the overall system configuration. Known Uses: Rainbow Adaptation Framework [27, 29]. MADAM [31]. Distributed Configuration Routing (DCR) [42]. C2 [67]. Kinesthetics eXtreme (KX) [79]. 5.5.8 Haderf-Based (106) Pattern Classification: Structru‘al - Decision-Making. Intent: Systematically select a reconfiguration plan that best balances multiple objec— ti ves. Context: The TI‘adeOfl-Based (106) Pattern may be used when: 0 more than one dimension must be considered for adaptation. a multiple reconfiguration plans satisfy the adaptation requirements. Motivation: Rule-based approaches are inadequate for expressing the adaptation expertise involved in trade-off decisions in the presence of multiple objectives [16]. Main- taining consistency between the trade-off preferences becomes unmanageable as the number of cases grow. In addition, these approaches require policy makers to be inti- mately familiar with low-level details of system function, a requirement antagonistic to adaptive and autonomic principles [80]. Utility functions map each possible state of an entity into a real scalar value, thus providing an objective function for selecting reconfigurations. The TradeOfl-Based (106) design pattern supports multiple hetero— geneous services by encapsulating differences at a local level and providing a uniform mean of communicating requirements to an arbiter. Figure 5.24 shows a use-case diagram of the TradeOfi-Based (106) Pattern. The main goal of this design pattern is to evaluate reconfiguration plans during an adap- tation and select the best plan that balances multiple objectives. 106 System Specify function Calculate utility / / / I <> ] I I u x ’ <> I l Select reconfiguration Aggregate data Strategy : Selector , <> Forecast demand Figure 5.24: UML use-case diagram of the TradeOfi-Based (106) Pattern Use-Case: Specify function Actors: Strategy selector Description: Select the utility function to be used. Includes: - Use-Case: Select reconfiguration Actors: Strategy selector Description: Select the reconfiguration plan with the highest. utility value. Includes: Calculate utility. 107 Use-Case: Calculate utility Actors: - Description: Apply the utility function to various reconfiguraticm plans. Includes: Aggregate data. Use-Case: Aggregate data Actors: - Description: Aggregate the different reconfiguration objectives so they may be uniformly input to the utility function. Includes: Get requirements. Use-Case: Get requirements Actors: - Description: Elicit different recrmfiguration objectives. Includes: - Use-Case: Forecast demand Actors: Strategy selector Description: Delete an architectural model from the repository. Includes: - Structure: A UML class diagram for the TradeOfl-Based (106) Pattern can be found in Figure 5.25. It is important to evaluate all objectives when selecting a reconfiguration strategy, even if the objectives are heterogeneous in nature. The TradeOfi-Based (106) Design Pattern provides an approach to integrate the various objectives and select the best reconfigm'ation plan that balances those objectives. This design pattern provides mechanisms to collect reconfiguration objectives and aggregate them into a format suitable for a utility function. The Utility Function provides the means to normalize all demands and the utility they provide to the system so they may be compared 108 objectively. This particular approach incorporates not only what a reconfiguration plan proposes to be its utility value to the system. but also provides a means to incorporate a predictive factor based on previous reconfigurations. The Inference Engine selects the Objective that provides the maximum numeri:a1 utility value. Participants: 0 Arbiter: l\'Iediates the interaction between multiple Objectives. This class pre- processes multiple Objectives so they can be input to the Utility Function. 0 Client: Represents a stakeholder in the system. Each Client has a set of objec- tives it wants to satisfy. 0 Data Aggregator: Combines and pie-processes Objectives so they can be input to a Utility Function. 0 Decision: This class represents the reconfiguration plan with the maximum util- ity value. 0 Demand Forecaster: Predicts the utility gained by a specific Objective. This prediction is determined based on previous knowledge about Objectives. 0 Inference Engine: This class is responsible for coordinating two major steps of the reconfiguration plan selection process. First, it calculates the utility value for each Objective. Second, it selects the Objective that produces the maximal utility value. 0 Objective: Represents any reconfiguration goal in the system. For instance, two Objectives could be “increase bandwidth” and another could be “increase latency” . 0 Utility Function: Represents any function that objectively compares multiple Objectives in terms of utility gain. These functions should return a numerical 109 chm u 0350.30 so: u too: 2:830 *.._ chm ” :EQ _ chm H Eve 9:830 H moZUoEOBw :oaooo wEbm Lune. . . 28:0 _ *.._ 85:.2 _ 03.8.30 N 828030 U 8380505 _ 20> M 205.80 ”Became l. 03.8.50 u 35:0 ”ovmoZUoEOBw 250.30 H 2 3280.30 ”ovofiwocwwa .moc H 33.830 ”80:25.3 :23: ” 005E Legacy—0L UCNEOQ >_ 32.85 “soc H 3360.30 novbaam cessaézi *.._ cosmwewwfizmo chm H .25 .252 3.80.qu 56600 “ 92.30628 20> u BEBBO “805582528 o:_w:moo:28£ Figure 5.25: UML class diagram of the TradeOfi-Based (106) Pattern 110 value in the range of [0,1] for each Objective. Behavior: Figure 5.26 shows a UML sequence diagram for an example of the TradeOfl- Based (106) Pattern in an adaptive system. In this specific scenario. the Inference Engine first retrieves the various Objectives that will be considered when selecting a reconfiguration plan. The Arbiter retrieves each Objective from the various Clients requesting an adaptation. The Arbiter also processes this information so it can be input to a utility function. The Inference Engine also invokes a Demand Forecaster to determine, based on prior reconfiguration experiences, what the estimated utility will be from a specific reconfiguration plan. Meanwhile, the Inference Engine applies the Utility Function to each Objective. Once the maximum utility value is determined, the Inference Engine creates a Decision that contains the selected reconfiguration plan. Consequences: 1. Multiple dimensions of reconfiguration and its outcomes can be evaluated uni- formly at run time. 2. The selected reconfiguration plan provides the maximum utility (desired out- come) for the entire system. 3. Developers must express a utility function to normalize each objective and its outcome. Since each utility function is application-specific, the reuse of utility functions is limited. Constraints: 0 Property 1: 111 ]---_- clo_m._o. |0l0 . . . . . . . . _ _ . _ . . . . . _ IIIIIIIIIIII LIIIIIlIIIIIIIIIkIIIIIIIIIIIIII IIIIIIIIIIII u. . _ _ 1' . . _ _ _ . _ _ . . _ . . . _ _ . _ _ . " AA030covv . _ _ _ . . . . . _ _ . _ _ _ . . _ . _ . . . llllllllllll .IllllIIIIIIIIIILIIIIlllllllllllrlllIllllllll' . . . . . _ . . _ _ . _ . _ _ u 8 03000303.an " u u IF iiiiiiiiiiiiii r iiiiiiiiiiiiii .r iiiiiiiiiiii V _ . _ . _ . . _ _ . _ _ . . . . u u . _ _ . . 3 038030003650 _ . uuuuuuuuuuu 1V . . _ . . _ . _ _ . . _ . . _ 8 0380.30 " n " 03000305 . . _ . . Ir IIIIIIIIIII . . . .4 _ - . . _ . . u " Cm0.600.30.0w . . . A . . . _ _ _ . . cesocsm file: clawed. 0.._l0n_ psimEloa s. .:_0. |_ U. I” .0. I1 303.500.3000w " . . _|llli_as.a Figure 5.26: UML sequence diagram example of the TradeOfiBased (106) Pattern 112 Globally, it is always the case that if Arbiter receives Objectives, then the Infer- enceEngine will eventually select the optimal reconfiguration plan. [:1 (( Arbiter.get0bj ective(0bjective) —> OlnferenceEngine. selectOptima1() ) This liveness property ensures that the reconfiguration plan with maximum utility is eventually selected whenever an Objective is obtained. This specific property can be strengthened by specifying an additional timing constraint. 0 Property 2: Globally, it is always the case that if InferenceEngine calculates the utility of a particular Objective, then InferenceEngine applies the selected utility function as well as estimates the probable utility based on past observations. D(( InferenceEngine. calculateUtilities(Objective) ) ——> (UtilityFunction . apply (Obj ective) /\ Demand Fore- caster . estimate (Objective) ) ) This safety property ensures that whenever the InferenceEngine calculates the utility of a given Objective, it does so by applying the selected utility function and by estimating the probable utility value based on previous observations. Related Design Patterns: 0 Sensor-Factory (41) Design Pattern: This pattern can be used to deploy sensors across a distributed environment and probe components. The monitoring information gathered from this approach can be used to maintain consistency between the architectural model and the implementation. 113 o Adaptation Detector ( 88) Design Pattern: This pattern can be applied to determine when a reconfiguration is required. It can also localize the source of the problem and guide the search for a reconfig- uration plan. Known Uses: 0 Rainbow Adaptation Framework [16]. 0 Unity (Autonomic Prototype by IBM) [17]. o MADAM [31]. 0 Utility Based Allocation [80]. 114 5.5.9 Component Insertion (115) Pattern Classification: Behavioral - Reconfiguration. Intent: Safely insert and initialize a component at run time. Context: The Component Insertion (115) Pattern may be used when: 0 components need to be added at run time. o the aprflication disallows downtimes. o the functional logic has been instrumented with an interface to guide compo- nents into active, passive, and quiescent states. Motivation: Inserting components into an executing system presents some subtle challenges. In many circumstances it is not enough to load a new component into memory and immediately begin its execution process as this may leave the system in an inconsistent state [46]. A new component must be given the chance to initialize itself, either to a default state or to a previously preserved state. In addition, the new component must be properly linked with the rest of the system so it may communicate and process information as intended. The Component Insertion (115) design pattern controls the operational status of the system such that components can be safely inserted at run time. Figure 5.27 shows a use-case diagram of the Component Insertion (115) Pattern. The goal of this design pattern is to guide the insertion of a new component at run time. 115 System Load component Passivate dependents / / /. / / Adaptation Driver Activate component Figure 5.27: UML use-case diagram of the Component Insertion (115) Pattern. Use-Case: Load component Actors: Adaptation Driver Description: Load a new component into the executing system. Includes: - Use-Case: Add link Actors: Adaptation Driver Description: Create a connection between two components in the system. Includes: Passivate dependents. 116 Use—Case: Passivate dependents Actors: - Description: Guide every component that. will share a connection with the new component to a state in which it cannot initiate new transactions and it is not currently engaged in a transaction that it initiated. Includes: - Use-Case: Activate component Actors: Adaptation Driver Description: Instruct a component to resume its normal behavior. Includes: - Structure: A UML component diagram for the Component Insertion (115) Pattern can be found in Figure 5.28. The C ornponent Insertion (115) design pattern coordinates the sequence of steps required to safely insert a component at run time. Components participating in the reconfiguration process must realize the States interface. The States interface can be used by the Adaptation Driver to issue commands that will drive Components into active, passive, or quiescent states. A Change Manager interacts with the executing environment and provides support for basic reconfiguration primitives and rules for loading and unloading components. The Adaptation Driver uses the Change Manager component to effect the necessary changes throughout the system as specified by the Reconfiguration Rules. Participants: 0 Adaptation Driver: Oversees the reconfiguration process of inserting a new Com- ponent into the system. 0 Change Manager: Provides support for loading and unloading Components and 117 90ch H C: 0 szm H :03 00.x. =0:E=wa=000~. AAm00=.0:.vv I 8.3. / =0..w.5wc=000~. \7 / . AAm00:.o:.vv Emacs—2 09.000 20> ” 080506000003: 29 n 35...: 20> H C.=0=00E000§>.mm3 20> ” 9:0:00800000. 20> N 0005000. 20> H 00.0.. 20> ” 030805000000 500.000 H 90:09:00 ”300000.300 000.000 ” 35:00:50 ”0000000.? 20> ” 9:0:0080003380 v1:250:50 N 200030: .000 “ E08030 .000 N 03300 .000 N 03000 05:09:00 50.000 n 080000000 500.000 H 03:00.00 50.000 “ 53.8.00 c035 . . . . AAm0020Evv . / . / / . / . < . _ _ _ _ _ _ AN 35:5 9008050 0000333 3:: 0:0. 00003000 assm AA00et0E.vv .7 AAm00=.0:_vv . _ . 00300 :0.§aa0< V 30:09:00 Figure 5.28: UML component diagram of the Component Insertion (115) Pattern 118 their interconnections. Component: Represents any executable component that can be deployed throughout the system. Each Component that may be involved in a reconfigu- ration must realize the States interface. Note that each Component maintains a pointer to its neighboring Components (this holds for all remaining reconfig- uration patterns). Driver: Manages the operational states of components involved in a reconfigu- ration through the States interface. Specifically, it can guide a Component to active, passive, and quiescent states. Reconfiguration Plan: Stores the specific sequence of instructions for reconfigur- ing the system at rim time. Reconfiguration Rules: Contains rules and instructions for specifying how basic reconfiguration operations are carried out in the system. Some basic reconfigu- ration operations include component insertion, removal, and swapping. States: This interface forces a Component to define which functional states correspond to active, passive, and quiescent states. An Adaptation Driver can control a Component’s behavior through this interface. Behavior: A UML statechart diagram for the Component Insertion (115) pattern is shown in Figure 5.29. Specifically, this statechart models the possible behavior of the Driver class found in the Adaptation Driver component. First the object loads the reconfig- uration plan that must be applied. At this step, we assume that a component must be inserted into the application at run time, otherwise this reconfiguration pattern would not be applicable. Thus, the new Component is dynamically loaded into the 119 system. Before the Component becomes operational, however, it must first be prop- erly initialized to either a default state or some previously preserved state. After the Component has been initialized, it is set to a passive state. The reconfiguration plan is analyzed once more to determine which Components will share a connection with the new Component. These neighboring Components are sent passivate commands. After the Driver receives all pending acknowledgments that neighboring Components are passive, then the new Component can be linked by the Driver. Lastly, activate commands are sent to the affected components so they may resume their normal behavior. Consequences: 1. Components can be inserted at run time without leaving the system in an inconsistent state. 2. Components are properly initialized to a consistent state before becoming ac- tive. 3. Several components may become passive during the reconfiguration process. These components may not initiate any new transactions while they are passive, thereby inducing a processing delay across the system until the reconfiguration process is complete. 4. Components must provide an interface to reach active, passive, and quiescent states. This interface can be either built—in during development or inserted through techniques such as AOP. Constraints: 0 Property 1: 120 :0 R 35:09:00 .0 ©i H Baas... C0.:>.00:.0< .000:>.000.m:000w.0:.0< \ .0:00_ 9:0:00800033000 > 033:0 . m 0 :0 w:_ .: 000:5 30:09:00 302 C000>.mim.uwo.m:000u.0:.0<\ 0. < 0 .0. 3 v.:...m:00.. .0:.0< 35:00:80 > r _0>.mm:a.0_ C.:0:00E000§>.mm3 30330.0:— 00E: ceszsay 025.0,. \ 9:0:00E0008fimmma ENE . 0:0:00800 at —:0.0::=w¢:000~. A .025 3:000.:e_n.:0.§=m::000~.< \ 000000 c 33.50.00. 0:05:00. 302 000000 _/ 000:0:00500.00000..0\ r .0E00x0000. 30:0:00E00000. tmum Figure 5.29: UML state diagram example of the Component Insertion (115) Pattern 121 During adaptation, neighboring components that will be linked with a: must first be guided to a passive state. To achieve this, a restricted condition, RCond must be established such that the system may safely reconfigure in bounded time. Rcond = CK0Component.neighbor.active() /\ 0Component.link()). This restricted state, Ram; prevents neighboring components from being acti- vated by the Adaptation Driver until the new component has been linked to them. Likewise, ROOM also prevents :1: from being linked to active components. This restricted space can be enforced by preventing neighboring components from accepting new transaction requests until the reconfiguration is complete. The complete guided-adaptation property in A-LTL is given by: true ((Componentneighbors 2: null) /\ (0(adaptReq) tfle RCond)) —‘ (Componentneighbors! = null). This A-LTL property ensures that when a component is inserted into the sys- tem at run time, it does not get linked to any other component that is currently active. Thus, when AReq is received the corresponding neighbors must first be guided to a passive state before links can be established between these com- ponents. Links can be created once the new component’s neighbors are in a passive state. Property 2: If a Component has not been initialized, then it is never the case that the Component is linked to its neighboring components. 122 Cl ( fl Component.initialize() —> 0 Component.link()) This safety property guarzmtees that if a component has not been initialized, then it will not be connected to any other components. Related Design Patterns: 0 Case-based Reasoning (68) Design Pattern: This pattern can be used to select a reconfiguration plan based on the available monitoring information. If the reconfiguration plan involves adding components at. run time, then the Component Insertion (115) design pattern can perform this task. 0 Divide and Conquer (78) Design Pattern: This pattern can be used to determine the specific sequence of steps required to safely perform a reconfiguration. Whenever a step requires that a component be inserted, it can be carried out by the Component Insertion (115) Pattern. o Architecture-Based (97) Design Pattern: This pattern can be used to select a reconfiguration plan. Any reconfiguration that involves adding components to the system can use the Component Insertion (115) Pattern. o 'IradeOH-Based (106) Design Pattern: This pattern can be used to select a reconfiguration plan that best balances the overall set of objectives that various stakeholders may have. If the reconfigura— tion plan includes inserting components, then the Component Insertion (115) Pattern can be used. 0 Server Reconfiguration (135) Design Pattern: 123 This pattern can be used to reconfigure an application structured as a server - client architecture. Components can be inserted into the server architecture through the Component Insertion {115) Pattern. Known Uses: Znews.com - Rainbow framework [16]. Software Reconfiguration Patterns [34]. Monitor — Dynamic Reconfiguration in Distributed Systems [46]. Evolving Philosophers - Dynamic Change Management [57]. 124 5.5.10 Component Removal (125) Pattern Classification: Behavioral — Reconfiguration. Intent: Safely remove a component at run time. Context: The Component Removal (125) Pattern may be used when: 0 components need to be removed at run time. o the application disallows downtimes. o the functional logic has been instrumented with an interface to guide compo- nents into active, passive, and quiescent states. Motivation: Safely removing a component from a system at run time is a difficult task. If a component is removed without first preparing the application for such a change, then the entire application may be left in an inconsistent state [57]. For instance, if a component is removed arbitrarily, then some previously initiated transactions may not terminate properly. The Component Removal (125) design pattern safely removes a component at run time by explicitly controlling the operational status of components that are directly connected to the component being removed. As a result, the Component Removal (125) design pattern ensures all transactions have completed before a component is removed. Figure 5.30 shows a use-case diagram of the Component Removal (125) Pattern. The goal of this design pattern is to guide the removal of a component at run time. Figure 5.30: UML use-case diagram of the Component Removal {125) Pattern System Remove Passivate component dependents / Adaptation , Driver ' \ Activate component Force . uiescent Use-Case: Remove component Actors: Adaptation Driver Description: Unload a component from the executing system. Includes: - Use-Case: Remove link Actors: Adaptation Driver Description: Remove a connection between two components in the system. Includes: Passivate dependents, Force quiescent. 126 Use-Case: Passivate dependents Actors: - Description: Guide every component that shares a connection with the component to be removed to a state in which it cannot initiate new transactions and it is not currently engaged in a transaction that it initiated. Includes: - Use-Case: Force quiescent Actors: - Description: Inst met a component to reach a quiescent state. Includes: - Use-Case: Activate component. Actors: Adaptation Driver Description: Instruct a component. to resume its normal behavior. Includes: - Structure: A UML component diagram for the Component Removal (125) Pattern can be found in Figure 5.31. The Component Removal (125) design pattern coordinates the sequence of steps required to safely remove a component at run time. Components participating in the reconfiguration process must realize the States interface. The States interface can be used by the Adaptation Driver to issue commands that will drive Components into active, passive, or quiescent states. No Component will be removed until every affected component has reached their required state. A Change Manager interacts with the executing environment and provides support for basic reconfiguration primitives and rules for unloading and unlinking a component. The Adaptation Driver uses the Change Manager component to effect the necessary changes throughout the system as specified by the Reconfiguration Rules. 127 w:.=m ” C500 _ wEbm H :09— :0.0:0..0::wc:000~. _ AAm00:.0:.vv I 00.3. / :0:0ch:000~. \7 / _ AAm00:.0:.vv . . . 55:03. 0w:000 20> H 9559:00525 20> H 60.5.5 20> H 00550500203300 20> H 9550800000. 20> ” 0:09.000. 20> H 00.:.. 20> H 0.:0000500800 :00.000 H 95:09:00 ”800000.000 :00.000 ” 95:09:00 32000.0 20> H 0.5:00E000003000 *0:0:00E00 ” 200030: .000 H 30000.5 .000 N 030000 .000 H 03.00 05:09:00 :00.000 ” 080000000 :00.000 ” 00000000 :00.000 ” 53.8.00 53.5 . . . . AA50:.0:.VV . / . / / \ / . / . K _ _ _ _ _ . _ 4 00.5.2 9505.5 $203300 30:: 30:. 00.03.00 seam AA000t00:.vv 535 500.0000. ./ AAm00:.0:.vv _ _ . .:0:00 500 Figure 5.31: UML component diagram of the Component Removal (125) Pattern 128 Participants: 0 Adaptation Driver: ()versees the reconfiguration process of removing a Compo- nent from the system. 0 Change Manager: Provides support for loading and removing Components and their intcrconnections. 0 Component: Represents any executable component that can be deployed throughout the system. Each Component that may be involved in a recon— figuration must realize the States interface. 0 Driver: Manages the operational states of components involved in a reconfigu- ration through the States interface. SI,)ecifically, it can guide a Component to active, passive. and quiescent states. 0 Reconfiguration Plan: Stores the specific sequence of instructions for reconfigur- ing the system at run time. o Reconfiguration Rules: Contains rules and instructions for specifying how basic reconfiguration operations are carried out in the system. Some basic reconfigu- ration operations include component insertion. removal, and swapping. 0 States: This interface forces a Component to define which functional states correspond to active, passive, and quiescent states. An Adaptation Driver can control a Component’s behavior through this interface. Behavior: A UML statechart diagram for the Component Removal (125) pattern is shown in figure 5.32. Specifically, this statechart models the possible behavior of the Driver class fomid in the Adaptation Driver component. First the object loads the reconfig- uration plan that. must be applied. At this step we assume. that a component must 129 be removed from the application at run time, otherwise this reconfiguration pattern would not be applicable. Thus, the target Component is sent a quiescent command. Before the Component becomes quiescent, however, it must first complete any pend- ing transactions and, if necessary, preserve its state. After the Component becomes quiescent, the Driver sends passivate commands to neighboring Components. After the Driver receives all pending acknowledgments that neighboring Components are passive, then the target Component can be unlinked from its neighbor Components by the Driver. The target Component can then be unloaded from the system. Lastly, activate commands are sent to the affected components so they may resume their normal behavior. Consequences: 1. Components can be removed at run time without leaving the system in an inconsistent state. 2. Components can preserve state before they are removed from the system. This facilitates replacing components at run-time. 3. Removing a central component from the system may cause many other com- ponents to become passive until the reconfiguration process is complete. Since passive components cannot initiate new transactions, a significant processing delay may be incurred by the system until the reconfiguration process termi- mates. 4. Components must provide an interface to reach active, passive, and quiescent states. This interface can be either built-in during development or inserted through techniques such as AOP. Constraints: 130 :0 — 35:00:50 0 # 00.03.00. 00.03.000.505 .0:.0< \ .0:00_ 00550800000350 > a 00>0E0~. 3.00 5.. 05:03 . 5.520.285.0001 026.5: 3...: 0 282.003 .5858 > _>00~.8.00. 00.5.5 00559500025 C0.0>.mm00.m..00..m.0:.0< \ 25000.50. 95508008030000 €005.00 — :mE 05:09:00 .0:00m0.=0.0< \ F 5.00:. 05000 :0 0.:0.0:0..0:=uc:000~.< \ .00.:. 305000050050 00003 30000000. 0:0.0000. tmum Figure 5.32: UML state diagram example of the Component Removal (125) Pattern 131 0 Property 1: During adaptation, neighboring components that will be unlinked from a: must first be guided to a passive state. To achieve this, a restricted condition, Rama, must be established such that the system may safely reconfigure in bounded time. RC'ond = l:l(fiComponent.nez'ghbors.active /\ -1C'ompon.ent.unlinkO). This restricted state, Room; prevents neighboring components from being acti- vated by the Adaptation Driver until the component has been unlinked from them. Likewise, Ram, also prevents :1: from being unlinked from active components. This restricted space can be enforced by preventing neighboring components from accepting new transaction requests until the reconfiguration is complete. The complete guided—adaptation property in A-LTL is given by: ((Component.neighbors! = null) /\ (<>(adaptReq) tfle Rand» true . —\ (Componentnezghbors 2: null). This A-LTL property ensures that once a source program receives an adaptation request (adaptReq), it enters a restricted condition RCond- In this restricted source. program, no component may be unlinked as long as any of its neighbors are active. ()nce neighboring components enter a passive state, links can be safely removed. 0 Property 2: If a Component is not in a quiescent state, then it is never the case that the Component is unloaded from the system. 132 D ( - Component.isPassive() —> - unloadComponent(Component) This safety property guarantees that a component will not be removed from the system unless it is in a quiescent state. Related Design Patterns: Case-based Reasoning (68) Design Pattern: If the reconfiguration plan selected by the Case-based Reasoning ( 68 ) pattern involves removing a component. this step can be performed by the Component Removal (125) Pattern. Divide and Conquer (78) Design Pattern: This pattern can be used to determine the specific sequence of steps required to safely perform a reconfiguration. Whenever a step requires that a component be removed. it can be carried out by the Component Removal (125) Pattern. Architecture-Based (97) Design Pattern: This pattern can be used to select a reconfiguration plan. Any reconfiguration that involves removing components from the system can use the Component Removal (125) Pattern. TradeOff-Based (106) Design Pattern: This pattern can be used to select a reconfiguration plan that best balances the overall set of objectives that various stakeholders may have. If the reconfigura- tion plan includes removing components, then the Component Removal (125) Pattern can be used. Server Reconfiguration (135) Design Pattern: 133 This pattern can be used to reconfigure an application structured as a server - client architecture. Components can be removed from the server architecture through the Component Removal (125) Pattern. Known Uses: 0 Znews.com - Rainbow framework [16]. 0 Software Reconfiguration Patterns [34]. o Evolving Philosophers - Dynamic Change Management [57]. 134 5.5.11 Server Reconfiguration (135) Pattern Classification: Behavioral - Reconfiguration. Intent: Safely reconfigure a server — client component architecture at run time. Context: The Server Reconfiguration (135) Pattern may be used when: 0 a server architecture needs to be reconfigured at run time. o the application disallows downtimes. 0 multiple client require services provided by the server component. Motivation: Client and server architectures are scalable in terms of the number and functions of clients that interact with the system [34]. Reconfiguring a server at run time is a difficult task for two specific reasons. First, while the presence or absence of a particular client does not affect the overall availability or behavior of the system, the presence of a server is crucial in the continued availability of the system. As a result, it is undesirable to reconfigure a server offline. Second, incoming client requests may continue to arrive While the server is being reconfigured. As a result, to ensure the reconfiguration process is transparent to clients, no requests may be lost during this period. The Server Reconfiguration (135) design pattern provides a behavioral template that describes how a server may be reconfigured at run time without losing client requests in the process. Figure 5.33 shows a use—case diagram of the Server Reconfiguration (135) Pattern. The goal of this pattern is to safely reconfigure a server architecture at run time. 135 System Insert data structure Add component \ l \ I ‘\ ,' \\ | \\ l Queue requests Adaptation . I Dn'ver l I I Remove component Modify arameter Figure 5.33: UML use-case diagram of the Server Reconfiguration (135) Pattern Use-Case: Add a component Actors: Adaptation Driver Description: Insert a component into the server architecture at run time. Includes: Queue requests. Use-Case: Queue requests Actors: - Description: Store incoming client requests so they may be serviced once the reconfiguration is complete. Includes: Insert data structure. 136 Use-Case: Insert data structure Actors: - Description: Insert a data structure that will store incoming client requests so they may be processed after the reconfiguration process terminates. Includes: - Use—Case: Remove component Actors: Adaptation Driver Description: Unload a specific component from the server. Includes: Queue requests. Use-Case: Modify parameter Actors: Adaptation Driver Description: Adjusts a specific parameter that will fine—tune the server’s behavior. Includes: - Structure: A UML component diagram for the Server Reconfiguration (135) Pattern can be found in Figure 5.34. The Server Reconfiguration (135) design pattern coordinates the reconfiguration of a server architecture at run time. Every Component that is involved in the re- configuration process must realize the States interface. The Adaptation Driver uses the States interface to guide a Component to its active, passive, and quiescent states. During the reconfiguration process, Clients may continue to submit requests to the Server component. For safety and operational reasons, however, incoming requests will be stored in a Request Buffer until the reconfiguration process terminates. The Adaptation Driver uses the Change Manager component to interact with the executing environment and effect the reconfiguration steps. Participants: 137 m0_:~_ 20> ” ©0238 20> ” 90m 20> u 00:0canoUumoE: cougawccogm 20> H 005300020 war—0m . 3:05 20> H 3032.08.33. A/ 20> ” 3032000 50.08 a 0582 20> ” 09.585020; _ 5058 ” 39:0 .5058 ” v.02: 20> . CH=0=anoU0um>Em3 AASoEoEVV 500.03 H 025m wEbm . 52a 20> . Cam—memo. _ a0t=mum0=c0m cmicosflswccoBm 20> H 9:0:an0032 _ 7 S 20> U 0508050005... Swag—2 / \ 20> . 9020:825003350 095:0 , \ .5053 H 05c AAm0v:_0:.vv \ . a a . AAm0u:_0EVV .5058 . 0% new / . a025— / \ N x \ - \ 50.59.50 < AAm0v:_0:_vv 53.5 .\ 55895.... AAm0v=_0Evv . \ 02.08025 \ a0>u0m ©0096me 25> N 030005 A Am0v=_0=_V\v 500505 N 5080.10 C8w>zoe 20> ” 05008 N\ 5058 H 0 >7.wa I iv 52. “ E08230 Al I 5058 ”E08230 50058 H 0 >58 58 H 0338 .8053 H 0335 E0coquU . Eon. ” 0>=0w F8053 ” 028m 555 a0>a0m 50:0 AA00w.t0::vv Figure 5.34: UML class diagram of the Server Reconfiguration (135) Pattern 138 Adaptation Driver: Oversees the reconfiguration process for the Server. This component is responsible for ensuring that incoming Client requests are queued for further processing and that a Server completes unfinished transactions before the reconfiguration begins. Change Manager: Provides support for loading and unloading Components and their interconnections. Client: Represents any component that requires services provided by the Server. Component: Represents any executable component that can be deployed throughout the system. Each Component that may be involved in a recon- figuration must realize the States interface. Driver: Manages the operational states of components involved in a reconfigu- ration through the States interface. Specifically, it can guide a Component to active, passive. and quiescent states. Reconfiguration Plan: Stores the specific sequence of instructions for reconfigur- ing the system at run time. Reconfiguration Rules: Contains rules and instructions for specifying how basic reconfiguration operations are carried out in the system. Some basic reconfigu- ration operations include component insertion, removal, and swapping. Request Buffer: This is a data structure for storing Client requests while a re- configuration takes place. Server: Represents a set of components that provides services to multiple Clients. States: This interface forces a Component to define which functional states correspond to active, passive, and quiescent states. An Adaptation Driver can control a Component’s behavior through this interface. 139 Behavior: A UML statechart diagram for the Server Reconfiguration (135) pattern is shown in figure 5.35. Specifically, this statechart models the possible behavior of the Driver class found in the Adaptation Driver component. First the Driver loads the reconfigu- ration plan that must be applied. Two possible reconfigurations are possible at this stage, either a component needs to be inserted or removed. Notice that to perform a swap operation we would first perform a removal followed by an insertion. De- pending on whether a component needs to be inserted or removed, the Driver can perform either an insertion through the Component Insertion (115) pattern or a re- moval through the Component Removal (125) pattern. Two options are possible after this operation is complete. Either more structural changes need to be performed or the queued requests need to be serviced. If no more structural changes need to be performed, then the queued requests can be serviced until the Request Buffer is empty. At this point, the server reconfiguration is complete. Consequences: 1. Pending transactions arevcompleted before the reconfiguration process begins. This ensures the server is in a consistent state before it is reconfigured. 2. No incoming request is lost during the reconfiguration process. 3. The system can be transparently reconfigured at run time with respect to a client. 4. Latency can increase significantly during the reconfiguration process depending on the complexity of the reconfiguration. Specifically, numerous components may be driven to a passive state during the reconfiguration procedure. Until the reconfiguration is complete, these components will not be able to initiate new transactions with other components. 140 .50 .020. u coming _..0..E0..0t=m0m0=.00~.: 000a>.00m0.0..0t:m..m0=.00~.< \ E550..0t:m0m0:.00~: 55.50 g .0 .. 5.03.0 .— .00E5..0n. _ O00.>.0m..0t=m.m0:c0~.< \ t m. . . m _ ”8.... "403.55.. lV© .0..0 _>0aE0..0t=m.m0=.00~: _ C05>..0m0.0..0t=m0m0:c0~.< \ .7 30.00.000.38 _bQEO..0t=m.m0:.00~: .05.0_ E005n...0>050~.505..500 \ 0.0 50.55% . _0>050...5_n.5.5.=w..500~._ A _05.0. _ 0505.550505: 35.2.0 # on 5.55 0 . . 50.09.558555 :50 .20 . a... n. g 3.05. 57.55.55.003: 50%.:50 3.40543 050.505.00.35. . 020.0 0. 300.53; a car. A 5.5.5.5003. 5...... 50000.63. _ C05....00..0t:m.m0=.00~.<\ fl 0 a 0.0m.5_n...o.5.=wc500~.< .0 .0 o... .055.57.55.29.580”?\ _0>..om..0t=m.0m0= .03: _ Cm:.500...0=0:.0 203.50.00— 0505.002 tfim Figure 5.35: UML state diagram example of the Server Reconfiguration (135) Pattern 141 Constraints: 0 Property 1: During adaptation, Clients will continue to submit transaction requests. If the Server keeps servicing incoming requests, then it may not reach a quiescent state in bounded time. To guide the Server to a quiescent state, the AdaptationDriver forwards all incoming Client requests to a RequestBuffer during the reconfigu- ration phase. Once the reconfiguration is complete, the Server may proceed to service all the Client requests until the message queue is empty. To achieve this, a restricted condition, RCond must be established such that the system may safely reconfigure in bounded time. Room, 2 D(-IServer.aecept() /\ RequestBuffer.active). This restricted state, RCond prevents a Server from accepting any new incom- ing connections during the reconfiguration phase. Likewise, Ream; also ensures that the Ada ptation Driver queues incoming requests for further processing. This restricted state can be enforced by redirecting all incoming connections to a message buffer. As a result, the Server will be able to complete any pending transactions that were already started before AR“, was received. The complete guided-adaptation property in A-LTL is given by: ((AdaptationDriver.queuelncoming() /\ (0(adavptReq) tfle Rcondll tfle (RequestBufferempty). This A-LTL property ensures that when an active server needs to be dynam- ically reconfigured, it will first be allowed to reach a passive state in bounded 142 time. Specifically, once an adaptation request, ado ptReq is received, the Adap- tationDriver blocks any incoming requests from being delivered to the server. Instead, incoming requests are stored in a RequestBuffer for further processing. A server will reach a quiescent state once it completes all pending transactions. At this point, the server can be safely reconfigured. Once the server becomes ac- tive again. it must first service all pending requests stored in the RequestBuffer. The reconfiguration process is complete once the RequestBuffer is empty. 0 Property 2: Globally. it is always the case that if a message is stored in RequestBuffer, then it; will be eventually serviced. Cl ((RequestBuffer.queue (request)) —+ O (RequestBuffer . retrieve (request) ) This liveness property guarantees that if a message is queued, then it will even- tually be retrieved and processed. This property ensures that messages are always processed at some point. Related Design Patterns: 0 Case-based Reasoning Design Pattern: This pattern can be used to select a reconfiguration plan to be performed by the Adaptation Driver in Server Reconfiguration (135). 0 Task Decomposition Design Pattern: This pattern can be used to determine the specific sequence of steps required to safely perform a reconfiguration. These steps can be carried out in Server Reconfiguration (135) if the application is structured as a server - client archi- tecture. 143 o Architecture-Based (97) Design Pattern: The Archifccture-Bascd (97) pattern can be used to determine the reconfigura— tions that need to be performed on a server architecture. The Server Reconfig- uration, (135) pattern can then perform these changes at run time. o TradeOff-Based (106) Design Pattern: This pattern can be used to select a reconfiguration plan that best balances the overall set of objectives that various stakeholders may have. If the application is structured as a server, then the Server Reconfiguration (135) design pattern can perform the necessary reconfigurations. a Component Insertion (115) Design Pattern: This pattern can be used to safely insert a new component at run time. a Component Removal (125) Design Pattern: This pattern can be used to safely remove a component at run time. Known Uses: 0 Z.com - Rainbow Adaptation Framework [16]. 0 Server/ Client Reconfiguration Pattern [34]. 144 5.5.12 Decentralized Reconfiguration (145) Pattern Classification: Behavioral - Reconfiguration. Intent: Safely insert and remove components from a decentralized component architec- ture. at run time. Context: The Component Insertion {115) Pattern may be used when: 0 components need to be added and removed at run time. o the application disallows downtimes. o no single component coordinates the activities of the distributed components. Motivation: Decentralized applications function without any single component coordinating the activities of the distributed components [34]. The lack of a centralized coordi- nator implies that every component is responsible for the collective reconfiguration of the entire application. If components do not adhere to a reconfiguration proto- col when they are inserted or removed from the system, then the entire distributed application may be left in an inconsistent state. The Decentralized Reconfiguration (14 5) design pattern provides a behavioral template that every component in the distributed application should follow to properly engage and disengage from other components during a reconfiguration. Figure 5.36 shows a use-case diagram of the Decentralized Reconfiguration (14 5) Pattern. The goal of this design pattern is to guide the insertion and removal of components in a distributed application at run time. System Passivate / <> I 1’ I I Component Disengage Figure 5.36: UML use-case diagram of the Decentralized Reconfiguration (145) Pat- tern. Use-Case: Engage Actors: Component Description: Initiate a transaction with another component. Includes: - Use-Case: Activate Actors: Component Description: Start requesting and servicing transactions with other components. Includes: - 146 Use-Case: Passivate Actors: Component Description: Terminate pending transactions while not initiating new transactions. Includes: - Use-Case: Stop Actors: Con'lponent Description: Terminate the component. Includes: Force quiescent. Use-Case: Force quiescent Actors: - Description: Terminate all pending transactions and await for every neighboring component to acknowledge the component’s departure from the system. Includes: Disengage. Use-Case: Disengage Actors: Component Description: Notify neighboring components of intention to go quiescent. Includes: - Structure: A UML component diagram for the Decentralized Reconfiguration (145) Pattern can be found in Figure 5.37. The Decentralized Reconfiguration (145) design pattern provides a behavioral template for reconfiguring decentralized components at run time. Components are res1')(‘)nsible for safely reconfiguring the overall application. Each Component must realize the States interface so they may autonomously cooperate with other Compo- nents during a reconfiguration. Components can notify each other of their intentions through the States interface. This enables a Component to properly engage and dis- engage other Components without leaving the system in an inconsistent state. 147 05> H 0.0m m.....m . C55 .0552 5.3. 50.00.. H 0.550. 0w5..0 5.553503. 50.00.. . :05. 5050.. H 0550 ? S w......m . 5... .. \ 55.55.55.003. 05> . 05050500505: 05> . 3:050:50 . 0.0.5.5: 05> H 95?..50. 20> . 0505095050. 20> H 9:05.500 H 0...... 05> . 0550.500 ”0.055.... 5. . 255.85.. 2505....50 . m.o....w .0: . \ N 50.00.. H 05.0 \ x \ . .. . \ \ \ 50.00.. . 53.3.5 AAm00:.0...vv AAm0.....0...vv \\ \ \ .0>..D . \ \ \ \ . . \ \\ AAm0.....0...vv ’ \ \ \ \ .. \ AAm0.0...0...vv \ \ \ 05080.5 \ s \ .. \ \\ \ \ 50.05 N 50805.. $053.50 \ . \ \\ \ \ 50.00.. H 035.. 3...... . \ \\\\ \ v1:05....50 . 202.30.. 00550 .‘W\\ \ 50.00.. n 3025000.. nnnnnnnnn V C0558... . AAWQNm _~ND.—VV OHN> SUN A9055...va 500.com. . 03.05 O . 505.500 \ \ . . 505.....00 8.8m. ’ % ..o AA005..05.VV Figure 5.37: UML component diagram of the Decentralized Reconfiguration (145) Pattern 148 Participants: 0 Change Manager: Provides support for loading and unloading Components and their interconnections. 0 Component: Represents any executable component that can be deployed throughout the system. Each Component that may be involved in a recon- figuration must realize the States interface. a Driver: l\Ianages the operational states of components involved in a reconfigu- ration through the States interface. Specifically, it can guide a Component to active, passive, and quiescent states. Additionally, a Driver may issue engage and disengage commands to other Components to notify its intentions. o Reconfiguration Plan: Stores the specific sequence of instructions for reconfigur- ing the system at run time. o Reconfiguration Rules: Contains rules and instructions for specifying how basic reconfiguration operations are carried out in the system. Some basic reconfigu- ration operations include component insertion, removal, and swapping. 0 States: This interface forces a Component to define which functional states correspond to active. passive, and quiescent states. In addition, it provides a negotiation protocol that specifies whether a Component wants to engage or disengage from other Components. Behavior: Explain 3 possible sequences. First, we can load another component and activate it. After that, each component is responsible for its own connections. Second, we can create a connection (link) between two components. Third, we can remove a connection (link) between two components. If there are no more links remaining and 149 the component needs to be removed (die), then the component unloads itself from the system. Otherwise it just remains in the system until a component requests a connection. A UML statechart diagram for the Decentralized Reconfiguration (145) pattern is shown in Figure 5.38. Since there is no Component to organize the reconfigura- tion process. each Component is responsible for reconfiguring the entire application. Specifically, this statechart models the possible behavior of the Driver class found in a Component. First the Driver loads the reconfiguration plan that must be applied. Two possible reconfigurations are possible at this stage, either a component needs to be inserted or the Component determines it should unload itself from the system. If a Component must be inserted, then it is loaded into the system and initialized. How- ever, every Component is responsible for engaging and disengaging other Components in the system on .its own. If the Component determines it must remove itself from the system, then it initiates disengage transactions with its neighboring Components. Af- ter the Component receives acknowledgments from its neighboring Components, then it can unlink itself from them. Finally, with no pending transactions, a Component can unload itself from the system. Consequences: 1. Components are responsible for the overall reconfiguration of the entire system. This facilitates the evolution of the system at run time. 2. Components must receive engagement acknowledgments from components it will interact with before it commences any transactions with them. This ensures that the insertion of a component does not leave the system in an inconsistent state. 3. Components must receive disengagement acknowledgments from neighboring 150 50:0..500 .0500. :0 00000.5: 0 . 6350505000005: \ 3.505.500.0005: 58.0.023550 ,0..=_.§.e8.0§.0: . casemeessweqP \ t 7.03.300. 3......5. t 35080.50. 30m0wc0m=0 a 5003.00 08.55: 0.0.2502 A F w:.w0w:0m.n. A F 50.5..500 > .50 0.... H 5005...... 0 \ .ouumco..00m:0... 350000.20 30.05000 .05... . 30.0... :00. 0.0.. cm .0... 0< 5. m. w_0 # \30.0>..00 Ya .00.0>..0< 0.5.0305... 00.. .. 0.... . 2 _ VF 05050500 5050500 > 00.0.. .I. >.0Z...000.~ 0 .030......m.0....w.0...0< .3.0....m.05..=...0 \ .00.. ”0.13000 .020. n 02.0.00. .0>.mm0...w.0....w.0... 0 0.00% 53.8.00. 3...... .0350. 30.03300 30w0wc0.m.0....w.0=.0< \ .d .0w0wc0.50.052.053.503._ .030w0wc0g :0... g 03000.. 0.0.2302 A . =0..0.:wc503. A . .0...... g 3.00 :0.....0..0.=w...503.< 00003 .. .c0..0...0....5..0.:wc503.< \ > 0.0...mm.....0.....cocoQEouzaooza \ 3:30.... _ .3505... 3:07.08. _:0.......0_..._0..0.=m...503.. 35050500000. _ . 0 50.50500 00.000; - ed Reconfiguration N N UML sequence diagram example of the Decentrali Figure 5.38: {145) Pattern 151 components before it can be removed. This ensures the removal of a component does not leave the system in an inconsistent state. 4. Each component is responsible for reconfiguring the entire application. This (*‘0111plicates verifying and analyzing that a reconfiguration plan is correct. 5. Components must provide an interface to reach active, passive, and quiescent states. This interface must also provide a protocol to notify other components of engaging and disengaging intentions. This interface can be either built-in during development or inserted through techniques such as AOP. Constraints: 0 Property 1: During adaptation, neighboring components that will be linked with :1: must first be guided to a passive state. To achieve this, a restricted condition, RCond must be established such that the system may safely reconfigure in bounded time. RCond = C](fiCO'mponent.neighbors.active() /\ —wComponent.link()) This restricted state, Room, prevents neighboring components from becoming active until the new component has been linked to them. Likewise, RCond also prevents :1: from being linked to active components. This restricted space can be enforced by preventing neighboring components from accepting new transaction requests until the reconfiguration is complete. The complete guided-adaptation property in A-LTL is given by: ((Component.neighbors == null) /\ (0(adoptReq) tfle RCond)) "—146 (Component.neighbors! = null). This A-LTL property ensures that when a component enters the system, it does not establish any communication links with active components. Specifically, the system must first enter a restricted condition, Rama, in which neighboring com- ponents will eventually reach a passive state. Links between the new component and its neighbors can be created once the component and its neighbors are in a passive state. Property 2: During adaptation. neighboring components that will be unlinked from a: must first be driven to a passive state. To achieve this, a restricted condition, Ream; must be established such that the system may safely reconfigure in bounded time. Rcond = Cl(0Component.neighborsoctiue /\ 0Componen,t.unlink()) This restricted state, RCond prevents neighboring components from becoming active until the component has been unlinked from them. Likewise, Room; also prevents a: from being unlinked from active components. This restricted space can be enforced by preventing neighboring components from accepting new transaction requests until the reconfiguration is complete. The complete guided-adaptation property in A—LTL is given by: ((Componentneighborsl = null) /\ (<>(ada.ptReq) tfle RC0.,,_d)) tfl‘xe (Componentnez'ghbors == null). 153 Where S Spec are the specifications that must be satisfied in the source program before the adaptation request, AReq is received and TSpec is the specification that must be satisfied after the component has been removed. 0 Property 3: If a Component is not in a quiescent state, then it is never the case that the Component is unloaded from the system. [:J ( 0 Component.quiescent ——> 0 Driver.unloadComponent() . This safety property guarantees that a component will not be removed from the system unless it is already in a quiescent state. Related Design Patterns: 0 Case-based Reasoning (68) Design Pattern: A component participating in the Decentralized Reconfiguration (145) pattern can use case-based reasoning mechanisms to determine which reconfigurations are necessary. 0 Divide and Conquer (78) Design Pattern: A component participating in the Decentralized Reconfiguration (145) pattern can use the Divide and Conquer (78) pattern to determine the specific sequence of steps required to safely perform a reconfiguration. o Architecture-Based (97) Design Pattern: A component participating in the Decentralized Reconfiguration. (14 5) pattern can use architectural models to determine which reconfigurations are necessary. 0 'I‘radeOff-Based (106) Design Pattern: 154 A component participating in the Decentralized Reconfiguration (145) pattern can use the TradeOfi-Based (106) pattern to select a reconfiguration plan that best balances the overall set of objectives that various stakeholders may have. 0 Component Insertion (115) Design Pattern: The Component Insertion (115) design pattern can be used to safely insert a component into the system at run time. 0 Component Removal (125) Design Pattern: The Component Removal (125) design pattern can be used to safely remove a component from the system at run time. Known Uses: 0 Unity — IBM Autonomic System [17]. 0 Software Reccmfiguration Patterns [34]. 0 Evolving Philosophers - Dynamic Change l\-’Ianagement [57]. Chapter 6 Process This chapter presents two ideas to facilitate the modeling and formal analysis of adaptive systems. First, we provide more details on how to accomplish several of the modeling steps briefly mentioned in the model-based development process [85]. In particular, we explain how the design patterns in this thesis can be leveraged by the model-based development process when building adaptive systems. Second, we illustrate how UML state diagrams can be used to model the behavioral aspects of the adaptive logic. Specifically, we introduce an iterative process that leverages automated formal analysis tools and techniques for analyzing the models against certain safety properties. 6.1 Model-based Development Process It is increasingly important to be able to adapt an application’s behavior at run time in response to changing requirements and environmental conditions. As a result of their high complexity, adaptive programs are generally difficult to specify, design, verify, and validate [85]. In order to leverage the benefits of model—driven engi— neering, including code generation, it is advantageous to address adaptation early in the development process, starting with requirements, progressing to design and then 156 eventually to code in a systematic fashion. Previously, Zhang and Cheng introduced a model—based development process to model and analyze adaptive systems [85]. In particular, the process focused on the assurance of the adaptations at each step of the development process. This thesis extends that work to focus on the creation of the design models that can be used as part of the design phase of the overall development process. We assume steps (1) through (4) of the model-based development process have been completed (see Figure 6.1). Requirements R,- have been specified for a given domain D,- that satisfy the overall system goal C. These requirements are opera— tionalized in the form of design models Mi. Furthermore, non-adaptive models M,- and .le have been created and verified against their respective local ((1),- and (DJ) and global global properties (INV), specified in terms of formal specification languages such as linear temporal logic. Nonetheless, at this stage, the resulting models lack the infrastructure required for self-adaptation. Each of these models must be in- strumented with monitoring and decision-making capabilities in order to automate the tasks of introspection and intercession. To provide the required monitoring and decision—making functionality, step (4) of the model-based development process has been extended to incorporate the design patterns presented in this thesis. Developers must analyze the specific domains, requirements, and constraints of the non-adaptive models M,- and Mj to determine which monitoring and decision- making design patterns are suitable. Once the domain and its requirements are understood, developers can browse the available design patterns for reusable solutions tl.1at address their needs. A design pattern’s Context field is particularly helpful at this stage as it identifies under what circumstances should the pattern be applied. Once an initial set of design patterns have been identified, developers should consult the Related Patterns field to review other design patterns commonly used together. This helps identify alternative approaches that were previously unforeseen during the 157 (4) Legud adaptation design patterns —> refinement l:| non-adaptive functional logic ---- '> transition 5 requirement or constraint that . """"" > satisfies must be satisfied Figure 6.1: Adaptation Design Patterns Within Model-Based Development Process. 158 design phase. If various design patterns are applicable, then developers should analyze the. Consequences field to determine the tradeoffs incurred by applying the particular pattern. After a set of design patterns is selected, the patterns can be instantiated, integrated with the non-adaptive models M,- and M j and formally analyzed against safety critical properties. Although the non—adaptive models M,- and M j are now instrumented with mon- itoring and decision-making capabilities, these models are still incapable of reconfig- uration. Step (5) of the model-based development process focuses on the creation of models to represent the adaptive logic (e.g., Mz‘o‘ and Mid) and verifies them for correctness. The reconfiguration design patterns presented in this thesis can be in- corporated at step (5) to guide the development of the adaptive models. These reconfiguration design patterns should be selected according to the reconfiguration scenarios that are possible as well as the overall architecture of the self-adaptive sys- tem. Analyzing a system’s architecture helps determine the different interactions between components as well as any dependencies that might exist between them. This is important as it guides developers in identifying the quiescent states in 114,-, the starting states in Al], and the integration of these states with the adaptive model Alid- 6.2 Modeling Adaptive Logic To fully leverage model-driven development technology for adaptive systems, such as systematic refinement of abstract models to more concrete models, it is nec- essary to model both the structural and behavioral portions of an adaptive system. \K-"liile several approaches focus on the modeling and analysis of the architectural (structural) dimension of an adaptive system [16, 29], it is also important to model and analyze the behavioral portion of an adaptive application. Model checking has 159 been I'n'eviously used to verify properties of adaptive software [3, 13, 56] and cor- rect errors before the system is implemented and deployed. By analyzing the design models against functional and adaptation properties, we minimize the potential to pr<_)pagate errors from the design to the implementation and maintenance phases. Despite the formal analysis capabilities, the combination of the functional logic in— tertwined with the adaptive logic makes the maintenance and analysis of the overall adaptive system models challenging. Previously. we presented an iterative approach to constructing and analyzing UML design models for adaptive systems, where we separate the modeling of the functional logic from the adaptive logic [68]. For the purposes of this thesis, we consider an adaptive system P to comprise n steady-state programs, where a steady- state program is a state machine that is non-adaptive. We consider adaptation to be the transition from one steady-state source program to another target program. Thus, while it is possible for P to transfer execution between any of the n programs, only one steady-state program may be executing at any given time. In general, our approach decomposes large adaptive programs by first separating the steady-state program verification from the adaptive logic verification. Our approach verifies three key types of properties. Local properties are those that must hold within a particular domain. Global properties or invariants are those that must hold at all times. Once each steady-state program is verified against their local and global properties, they do not need to be verified again if involved in a different adaptation scenario. Thus, by separating concerns at the model level, the complexity of verifying the model correctness of adaptive programs is decreased. Our iterative approach is as follows (see Figure 6.2): 1. Create UML statecharts for objects that are involved between target model 1le and source model A1,. 2. Use Hydra [63] to automatically translate the resulting collection of statecharts 160 Local Create UML ‘ . ——H ———> Statecharts Requr rements Statecharts A l AMOEBA Hydra Verification Translation 7 (333.113.. , 5,... 9 Verification Properties ldentify _ Development Starting States - Models Figure 6.2: Iterative Process for Modeling Adaptive Logic. that constitute the adaptive logic into Promela code. 3. Analyze the adaptive model for adherence to the global and transitional proper- ties using SPIN [47], and the adaptive propreties through the AMOEBA model checker [86]. If any global proprety is violated, return to (1). 4. Identify quiescent states in source model M, and add transitions from these states to adaptive model AIM. 5. Identify starting states in target model M]- and add incoming transitions to these states from adaptive model MM. In order to complete step (1), developers should refer to the source and target models. Examining the structural differences between these models will help identify which objects were affected by the adaptive logic. Unfortunately, just examining the structural differences‘will not identify all the objects involved in the adaptive logic. Some objects exist only within the scope of the adaptive logic and will not show up in 161 either set of diagrams. For instance, a temporary buffer in the adaptive infrastructure that holds data while the system initializes the target steady-state program will not show up in either source or target models since it is not present in either of them. These objects, however, will become apparent as the adaptive logic is modeled since they bridge the gap between the source and target models. Steps (2) and (3) of this iterative modeling process rely on automated tools for formally verifying programs. Specifically, step (2) uses Hydra, a tool based on a UML formalization framework developed by McUmber and Cheng that automatically translates UML state diagrams into Promela code [63]. Step (3) uses the SPIN model checker [47]. SPIN takes Promela code as input and can be run in either simulation or verification mode. Simulation mode is helpful for visualizing sample executions of the system. Nonetheless, verification mode is required to state any claims about satisfying or violating specific properties. If a property is not satisfied, SPIN produces a trace output showing where the error occurred. One of the main advantages of using Hydra and SPIN together is that enables automated formal analysis of development models. That is. the same models that are used to guide development are used in the verification and analysis process. Step (5) involves identifying several application-specific states. Several re— searchers [34, 57, 46] advocate that a component is quiescent when it has com- pleted all pending transactions and is not engaged in communications with any other component. Currently, developers manually identify which states conform to those requirements in an application. As a result, the identification of quiescent states is application-specific. Likewise, when a component is loaded at run time it might need to be initialized to a particular configuration. 162 Chapter 7 Case Study This chapter presents a “proof of concept” case study that applies several adap- tation design patterns in the construction of a self—adaptive application. First, we describe the application domain. We then list the specific functional and adaptation requirements that must be satisfied by the resulting application. Next, we present our design and implementation. Finally, we present a comparison between a pattern- oricnted approach and a framework-oriented approach at constructing an adaptive system. 7 .1 Application Description The Z.com case study was originally described in [16]. Z.com is a fictional news site that is planning to use adaptation to address the “slashdotting effect” where news sites when listed on slashdot (or brought to the wider public’s attention through some other means) are unable to deal with the larger number of requests for content and either suffer from high latency or else are unable to serve content altogether. For instance, on “Black Friday 2006”, the Wal-Mart website was inaccessible into late afternoon costing the store millions and the day before Amazoncom traffic was problematic due to the demand for the Xbox 360 [16]. 163 Garlan et al. modeled the Z.com system as a set of clients and servers with the overall constraint that latency must fall within a given threshold. Nonetheless, adap- tation concerns for this application are multi—faceted. Some of the utility concerns that must be balanced at run time include cost, latency, and fidelity. Cost is incurred by the company whenever it runs a server. Latency measures the amount of time it takes for a server to provide the requested content to a client. Fidelity represents the content format, either graphical or textual. The purpose of the adaptive Z.com system is to optimally balance the costs incurred by running servers while providing quality content at a low latency. This case study uses the adaptation design patterns presented in this thesis to re..-engineer the Z.com adaptive web server previously presented in [16]. Although our ar'laptive system is implemented using a notably different approach, it exhibits similar behavior to the one Cheng et al. created using the Rainbow framework. Specifically, our version of the Z.com application provides the same reconfiguration capabilities as Z.com provided. Having two implementations of the same adaptive system enables us to perform a more comprehensive comparison of the key differences between the approaches. 7 .2 Requirements Since this case study is aimed at replicating Rainbow’s Z.com adaptive news server [16], their same functional and adaptive requirements apply to our case study. Specifically, there are conflicting requirements between operational costs and quality of service constraints. The following requirements were identified by Garlan et al. for Z.com: o The news server will provide basic HTML functionality to requesting clients. 164 o The operational cost may not be exceeded at any time. Specifically, Z.com has a maximum monetary budget for providing its services. Being a company, it will attempt to maximize its profits by not exceeding its allocated budget. 0 The quality of the content should be the best one possible. Specifically, when- ever possible, service client’s requests in graphical content mode. 0 The system will avoid losing customers due to a high response time if it can somehow provide faster content. Specifically, if the server’s average response time is too high, the content may be switched to textual mode in order to reduce transmitting large file sizes. Even though Rainbow uses a utility-based approach for selecting which recon- figuration to apply depending on different stakeholder’s needs, it must first quantify conditions that warrant adaptations. The Z.com application requirements and its implementation define several macros to represent these operational boundaries at a high level of abstraction. For instance, cost is expressed as being within budget or exceeding budget. Likewise, the three possible values for latency include low, middle, and high. Each macro is replaced during compilation with the specific numerical val- ues that developers consider to represent different operational levels. This facilitates the task of evolving and fine-tuning the adaptation requirements as needed. Given the three objectives of minimizing operational costs and latency and pro- viding graphical news content whenever possible, Garlan et al. reasoned about the possible adaptation scenarios that might arise for Z.com. For instance, Z.com will increment its server pool by one integral amount if the response time is high and the budget will not be exceeded. Otherwise, Z.com will switch to textual content mode if it is not already in that mode. Additionally, when the response time is low, Z.com will decrement its server pool size by one integral amount if it is near budget limit. If the response time is low, then the servers will be switched to graphical mode if they 165 are not already in that mode. Lastly, when the response time is in the medium range, Z.com will switch to graphical mode if the mode is textual, while the server pool size may either be incremented to decrease response time or decremented to reduce cost. As an example, consider the following reconfiguration scenario for Z.com. Under normal conditions, Z.com is hosted in one active server. Breaking-news are issued at Z.com’s homepage and many clients start connecting to the server and requesting the HTML web page. Gradually, the latency increases to a high level. T we possible reconfigurations are available. First, Z.com could add another server and split the load from incoming users while maintaining graphical content delivery. Second, Z.com could switch to textual delivery mode without adding any servers. Since the current budget at Z.com allows at least two servers to be executing without exceeding the allocated budget, the first reconfiguration plan is selected. This provides the best user experience without exceeding cost limitations. The reconfiguration plan is applied, a new server is initialized and the latency drops back to a low level. 7 .3 Application Design We re-engineered the Z.com application in three major stages. First, we mod- eled and implemented the functional logic according to the functional requirements identified in [16]. Next, we identified a set of monitoring and decision-making design patterns that were applicable to our version of Z.com and we proceeded to instanti- ate them. To ensure our design satisfied certain properties, we analyzed the resulting models against local properties and invariants before we implemented them. Lastly, we modeled and implemented the adaptive logic responsible for reconfiguring the server architecture. 166 7 .3.1 Non-Adaptive Design Our Z.com application is modeled after a multi-threaded server-client architec- ture (see Figure 7.1). Specifically, our design comprises a Gateway, a Gateway Thread, a Load Balancer, a Server, a Server Thread, and a Stats class. The Gateway, Load Bal- ancer, and Gateway Thread classes are responsible for taking incoming HTML requests from different web browsers, determining which available Server currently has the low- est average response time, and redirecting the web browser to that Server, respectively. The Server and Server Thread classes are responsible for servicing common HTML re- quests such as retrieving a file across a network. The Stats class follows the Singleton design pattern [‘26] and enables the Load Balancer to keep track of usage rates for each Server. We implemented the design models in the JAVA programming language. Any web browser capable of displaying HTML content can readily connect to the applica- tion and retrieve web content. This interface also facilitated the use of a simple script to test parts of the application. The script performs a basic load test by repeatedly requesting a web page at various intervals. For instance, running the load'test on a single server with no adaptation capabilities quickly showed an average latency of over 500 miliseconds. This simple test facilitated the analysis of our Z.com application under different configurations and usage rates. We selected a set of monitoring and decision—making design patterns based on the context of the Z.com application. We chose to apply the Sensor-Factory (41) design pattern to periodically monitor the average latency for two reasons. First, a distributed monitoring scheme is required for Z.com’s networked architecture. Second, our functional logic already provides an interface to the attributes that need to be monitored at run time. Although this might seem impractical, the same approach was followed in [16]. Garlan et al. noted that system administrators would have 167 20> ” 000330.500th 20> ” 900053—203808 20> H C508 20> H Cam0zc0mmm0ooa *.._ m0¢080m=0 _ 20> ” chEm 5530006 20> ” Cam0=c0m~0w A wctum £200 20> H CE: @3050 0005,;03806 _ _ $00502 05 ” C._0>0m000_0m macaw H “00:30 wfibm ”600 _000 n 0360 “0000—36004 % _ 38m H CSSme “E H 0—0020m83200w 03:00 N O0EFw><00w 20> H A0328 £0Errw><0§00= .023 80.0.0. 22, H 3.5% 550% 20> H 01:2 E0550. 20> H 038902098005 .8208 H 35% $2585 20> H Ocean—0003.58 20> ” CE: 2: u E 0002....020m 50:00. 0:50: *zo 20> ” 8mm 29 u 350 macaw ” 600 .8305 *..o 0>0_.=0._ _ EV 38m H 38m 39m 20> ” 050203—3000:— Eo> N 3050008 20> ” 228% 8:235 05% chm n 6.00 h0>e0m Figure 7.1: UML class diagram example of the Z.com functional logic 168 access to monitoring information from the application’s interface. Since the objective of Z.com is to automate tasks performed by a system administrator, it makes sense to provide an interface to these attributes that can be remotely probed by a sensor. The instantiated version of the Sensor-Factory {41) pattern is shown in Figure 7.2. Our Z.com application uses Simple-Sensors to probe active Servers for their av- erage. latency. Given the nature of our application, the instantiated Sensor-Factory (4]) pattern does not include Complex-Sensors. In addition, since our Simple-Sensors realize the Abstract Sensor interface, there is no need for an Adapter pattern [26] to facilitate the communication between a Client and a Simple—Sensor with incompatible interfaces. We used Hydra [63] to automatically convert several state-based models of Re- source Manager, Sensor—Factory, and Simple-Sensor into Promela code. A constraint violation was found when we attempted to verify the Promela models in the SPIN model checker [47]. The violated property stated that if a Resource Manager denies a sensor request, then Sensor-Factory would not deploy that sensor. However, an earlier version of the Sensor-Factory (41) allowed the existence of multiple Resource Managers across the system. Although this did not seem problematic at first sight, it enabled the following scenario: “the same sensor request is granted by instance 1‘. of Resource Manager and denied by instance y of Resource Manager.” Since our focus is not on distributed consistency. we resolved the problem by permitting only one Resource Manager in the system. Notice that if distributed resource management techniques are applied, then this constraint can be lifted. Two decision-making design patterns were applied to Z.com, Adaptation Detector (88) and Case-based Reasoning (68). The Adaptation Detector (88) pattern was selected to interpret the monitoring data supplied by the Sensor-Factory (41) pattern and detect when a reconfiguration was required. Figure 7.3 shows the instantiated 169 03> H 3008 22 u 05. 03> H 33:00 3.030.008 03> H 33:00 3.8.098 03:00 n .0380. .00: H N300 030a H C330 03:00 ” NA0.00 35 H 2000 SOQ H 0000 ANNE—WWW“ - wfibm ”.3090. 0300 03:00 ” 0.0303000» . mEbm 300:0 AA00b0300vv 03:00 ” €330.00. .0m00m0300m 380900.330. *..o > *z. w0Em ”.000 AA000t000VV £30 30w.0,_. AA0ab0000vv _ 33m ”.000 ka-QDU EozU *..o 38:00. _ _ 03> H C0m00m0EE_m ”3.032% 03> H 0030.0. 03> u C0m00m0_90_m ”$030.0. 000303 N 6000:0000 03> “ 0.0530. .0330. 03> ” G030... 8.3300 _ _ 000303 N c.0m00m000 002003 ”330.08 A . 000.003 N 00.000000 V 002003 N 03.82830 wEbm n 0032 _ _ 000.003 H 3.0003000 03030 03:00 N 5300000 .9833. wEbm ”.000 .0w000200.:0m0~_ E030“.-.0m00m Figure 7.2: UML class diagram of the Sensor-Factory (41) Pattern applied to Z.com 170 version of the Adaptation Detector (88) design pattern. The key participants in this design pattern are Observer and Analyzer. A single Observer interacts with a Simple- Sensor (not shown) to obtain the monitored attributes. The Observer interprets the data by casting it to whichever type it expects to receive from the Simple-Sensor data feed. This data is then compared against three specific value boundaries by the Analyzer. If the boundaries are exceeded, then a Trigger is created and sent to the Inference Engine of the Case-based Reasoning (68) pattern. As with the Sensor-Factory {41) pattern, we used Hydra to automatically convert UML state-based models of Health Indicator, Analyzer, and Observer into Promela code. We then used the SPIN model checker to analyze the two properties previously specified for the Adaptation Detector ( 88 ) design pattern. Specifically, we wanted to ensure that if Observer received any monitoring value, then it would eventually be compared against the Threshold. Likewise, we wanted to ensure that if a Threshold was exceeded, then a Trigger would be created. The SPIN model checker did not find any violations for these two properties. The Case-based Reasoning ( 68 ) pattern was selected to determine which reconfig- uration plan should be applied based on the monitoring information available. Garlan et al. used a utility-based approach for selecting reconfiguration plans in their ver- sion of Z.com [16]. Nonetheless, the reconfiguration scenarios for this application are simple enough that they can be efficiently captured in a set of “if-then” rules. Figure 7.4 shows the instantiated version of the Case-based Reasoning ( 68) design pattern. Though the instantiated version is similar to the Case-based Reasoning ( 68 ) pattern, there are slight differences between the two. Specifically, the case-based reasoning decision-making process for Z.com does not support any learning capabilities. As a result, Z.com will only support reconfiguration scenarios that are known ahead of time. 171 03> ” A0300 ”0:05.02: 0.0a n tomc0m ”30.0900. wibm H 00:35.0 m0_..m ” .0300 .0>.0m3O * . 000303 U 33300.30. 0 .0300 ”30.09000 29 H 03.50. 30.2006. _ \ 02w: _m>0 I 03> H 20%;; ”$003 .03.; H C.0ww...r0.0.000w 000303 ” 35302003000 —- *2 *. E H :E: 2052.: 000m _ 3000.003200: V 0: n 0003000000. .E H 099 wEhm u 900.000.... witm U 00.:0m 000303 N 0000000. 3»th Figure 7.3: UML class diagram of the Adaptation Detector {88) Pattern applied to Z.com 172 06> H cease 0003 H 00:00 000303 N 3308.5 0 .0000 ”30.00.08 0: u 0.0: wEbm ” 00:00 .. . . . 0 * _ _ *:O .0mw_.,_. 3M— mo_:~=vox_n_ \ _ > 0.... > 8.0% 3:000 3000 _ _ _ 00_m30D N 000000 03> ” C0003 03> H C035. “00.0003: _..o 03> u C0300. ”3000000 000:3 u 00_0 A 0 03> ” 30:. _ ]/ “E H 3000.3 00.2000 0.; 30:00. _ 000m wEbm H 0.053 0500900000300— 0.00_m000~_.0ww_.0. Figure 7.4: UML class diagram of the Case-based Reasoning {68) Pattern applied to Z.com 173 We used Hydra to automatically convert UML state—based models of Inference Engine and Fixed Rules into Promela code. These Promela models were then analyzed with the SPIN model checker against two properties. First, we want to ensure that if a Trigger is received, then it is always the case that a Decision is produced. Our application design includes a default rule and decision pair to enforce this constraint in the event that no other pair matches at run time. Second, we want to ensure that if a decision is produced, then it is always the case that it is logged. Logging the reconfiguration decision and why it was selected will help developers understand how their system is behaving at run time. The SPIN model checker did not find any instances of property violations for either of these two properties. 7.3.2 Adaptive Design At this stage we have augmented the Z.com application with monitoring and decision-making capabilities. Specifically, we can periodically observe the average la- tency, detect when a reconfiguration is required, and select a reconfiguration plan that will yield the desired behavior. Figure 7.5 shows the resulting class diagram of inte— grating the monitoring and decision-making processes with the functional logic of the Z.com application. This class diagram also includes an Adaptation Driver that over- sees the specific reconfiguration steps of the entire system. The Inference Engine from the Case-based Reasoning ( 68) pattern notifies the Adaptation Driver that a specific reconfiguration plan needs to be applied. The Adaptation Driver then performs recon- figurations drawn from the behavioral templates found in the Component Insertion (115), Component Removal {125), and Server Reconfiguration (135) patterns. Previously, we identified four possible reconfigurations for our version of the Z.com adaptive news server. Two of those reconfigurations involve tuning param- eters to alternate between content delivery mode. The two other reeonfigurations 174 ion icat UML class diagram of the Z.com appl Figure 7.5 175 involve either adding or removing a Server at run time. In contrast to the parameter reconfiguration, we must first prepare the system before a server is added or removed. Specifically, incoming client requests need to be queued so they may be processed af— ter the reconfiguration is complete. Otherwise, client requests may be lost during the reconfiguration process. We used the Server Reconfiguration (135) pattern to safely reconfigure the Z.com application in scenarios that involved the addition or removal of a server. The Server Reconfiguration (1.95) pattern, in turn, reuses the Component Insertion (115) and Component Removal (125) reconfiguration design patterns to safely add and remove components, respectively. For instance, to add a server at run time, the Adaptation Driver first loads and initializes a new Server and Load Balancer. The Adaptation Driver then inserts a Request Buffer to store incoming requests during the reconfiguration procedure. Then the Adaptation Driver sends passivate commands to both the Servers and Load Balancer so they can be safely reconfigured. Once these components are passive, the Load Balancer can be driven to a quiescent state so it can be removed from the system. Notifications are then sent by the Adaptation Driver to activate the affected components. Finally, once all the queued requests are serviced, the reconfiguration is complete and the system continues to operate as normal. At this stage, the Z.com application comprised instantiations of one monitoring pattern, two decision-making patterns, and three reconfiguration patterns. This set of six design patterns rendered our Z.com application with self-adaptive behavior. That is, sensors periodically probed the servers for the average latency, and whenever a substantial change was detected, an adaptation request was issued. The decision- making determined which reconfiguration plan to apply based on the monitoring information. The reconfiguration plan was then applied by the Adaptation Driver and either switched between content delivery modes or added or removed servers at run time. When compared to the Rainbow version of Z.com, our application provides 176 similar functionality and reconfiguration capabilities. 7 .4 Results Re—engineering the Z.com application originally presented by Garlan et at. in [16] enables us to compare the advantages and disadvantages of both approaches. Our design pattern approach has several advantages over a framework-oriented approach at developing dynamically adaptive systems. For instance, design patterns impose few initial constraints on the system being developed. As a result, patterns provide a flexible approach that can be readily customized to specific systems. Frameworks, on the other hand, incorporate many design decisions already made by the framework developers. Likewise, design patterns do not entail a steep learning curve in order to apply them successfully. To properly use a framework, however, a developer must understand the underlying framework mechanisms and how they relate to the appli- cation being built. Additionally, instantiated versions of the design patterns can be analyzed through formal verification tools and techniques to ensure a design satisfies certain key properties before it is implemented. Attempting to verify the correctness of a framework is. at best, impractical. Lastly, with our design pattern approach, developers select only those adaptation mechanisms their application will require. As a result, adaptive applications built with our adaptation patterns contain only those features it needs. rather than including many features that may not be necessary. Framework-oriented approaches, on the other hand, have several major advan- tages over our design patterns for building dynamically adaptive systems. For in- stance, adaptation-enabling frameworks provide large amounts of code that can be directly reused when building adaptive applications. If the application and the frame- work share the same context and domain, then a large section of development over- head can be avoided by reusing the framework’s code. Design patterns, however, offer 177 no code at all. After the system is designed and the patterns are instantiated, they must be implemented by developers. Likewise, adaptation-enabling frameworks, such as Rainbow, tend to support a wide range of adaptation approaches and techniques. Each desired functionality must be carefully integrated and implemented into the ap- plication with a pattern-oriented approach. Lastly, adaptation-enabling frameworks hide the internals of dealing with specific reconfiguration scenarios from developers. In contrast, design patterns must be instantiated and customized for the particular application being developed. As a result, developers have to deal with the details and complexities of reconfiguring applications at run time. 178 Chapter 8 Conclusions Our work with adaptation design patterns has yielded three main contributions: an adaptation design pattern template that assists developers in understanding and designing adaptive systems; a set of twelve adaptation-focused design patterns to promote the reuse of successful design decisions; and extensions to the model-based development process introduced by Zhang and Cheng [85] that incorporate the use of adaptation design patterns and state-based modeling techniques. We describe these contributions in more detail below. First, we developed an adaptation—focused design pattern template for the de- velopment of adaptive systems. We extended the pattern template used by Gamma et al. for describing design patterns [26] with the Behavioral and Constraints fields. Developers can use the Behavioral field to analyze the interactions between different objects in the design pattern. Likewise, developers can use the Constraints field to ensure their instantiated design pattern satisfies the specified properties. In addition, we modified the Related Pattern field such that it indicates which other adaptation design patterns are commonly used together when building an adaptive system. The information provided in the template enables developers to understand the conse- quences and trade-offs incurred by applying a pattern. Furthermore, the use of a. 179 design pattern template enforces the uniform organization of every adaptation design pattern, thus facilitating their use. Second, we introduced twelve design patterns to support monitoring, decision- making, and reconfiguration of adaptive systems where the patterns facilitate the separate development of the functional logic and the adaptive logic. Each design pattern was harvested from at least two successful design solutions and generalized so that they may be applied across different adaptive domains. To assess their maturity, we validated each design pattern against instances in adaptive systems that were not used in the harvesting process. In addition, we successfully applied a subset of the patterns in the development of an adaptive news web server. This example helped illustrate how various design patterns could be combined to construct self-adaptive and autonomic computing systems. Finally, we extended the model—based development process previously introduced by Zhang and Cheng [85] in two key ways. First, we developed concrete guidelines for using set of adaptation design patterns to realize the design modeling steps of their process. Specifically, we incorporated the monitoring and decision-making patterns into the creation of the non-adaptive models and the reconfiguration patterns into the creation of the adaptive models. Second, we incorporated the use of UML state-based models to represent the adaptive logic within the model-based development process. Using UML state—based models to represent the adaptive logic facilitates the visual inspection and formal verification of the instantiated design pattern models against specified properties through the use of automated tools such as Hydra [63] and the SPIN model checker [47]. This verification step enables develOpers to ensure a design satisfies specific constraints before the implementation phase. Several directions for future work are possible. First, additional design patterns for adaptation could be identified and integrated with the set of design patterns presented in this thesis. Second, we could examine how these design patterns can be 180 inserted into a non-adaptive application through the use of aspect-oriented techniques [38. 82]. Third, we could explore the use of digital evolution techniques to automati- cally identify the points of an application to insert the monitoring patterns. Lastly, we could explore the use of digital evolution techniques to determine how adaptation design patterns can be evolved and instantiated to satisfy new sets of properties [33]. 181 APPENDICES 18‘2 Appendix A Sample Instantiations This chapter presents sample original implementations that were used to harvest the twelve adaptation-oriented design patterns presented in this thesis. In particu- lar, for each adaptation design pattern, at least two sample original implementation sources are presented and compared against the resulting design pattern. It is impor- tant to note, however, that while there may be some similarities between each design pattern and its corresponding original implementations, there will not be a one-to- one correlation between them. Specifically, each design pattern provides a generalized solution based on these original implementations (as well as others). Each original implementation is presented through UML class diagrams, component diagrams, ob- ject diagrams, or state diagrams. Furthermore, for clarity, each model presented in this section has been elided from its original version to include only those elements relevant to the design pattern being considered. 183 A.1 Sensor-Factory (41) Pattern Rainbow Adaptation Framework [16, 27, 30]. The Rainbow adaptation framework provides a reusable infrastructure for probing components, determining when an adaptation is warranted, and then effecting the necessary changes. Figure A.1 shows an elided UML class diagram of the probing mechanisms employed in Rain- bow. Various similarities can be observed between Rainbow’s probing infrastructure and the Sensor-Factory (41) design pattern. Specifically, both define explicit inter- faces to which RegularPatternGauges (probes, sensors) must adhere. This interface facilitates the creation of various types of interchangeable probes across the system. The S ensor-F actory (4]) pattern follows a similar approach by defining an interface to which every Sensor must adhere. Moreover, in the Rainbow probing framework, each RegularpatternGauge is associated with some GaugelnstanceDescription, which defines the type and configuration of the gauge. Likewise, both Rainbow and the Sensor- Factory (41) pattern employ objects to create, deploy, manage, and remove probes. The GaugeCoordinator is responsible for creating, configuring and deleting instances of RegularPatternGauges. Notice that this functionality is provided by both Sensor- Factory and Registry in Sensor-Factory (41) Nonetheless, there is no explicit use of a ResourceManager to oversee the allocation and deallocation of probes in the Rainbow framework. 184 lmEbm " 30000038083300 22 . E&0..2.0>3300< ”0:_0>30:_0>0_w0_mb0:0 03> u 3005000893000. 03> n 30: A ”080.00wc000v0w:000.:wc000 w00_ U 30230000003 03> n 3000003 $=0U30=m3< A0.03008 03> ” $03.5 H 083 0. 03> . 300w0000.:wc000 03> H 30.0w:000_0030 03> u 3.00. “00:00 .w0_..w ”0300000003000 03> ” 3000003 03> “ 3030.02 ”8 38.5 “0802300083308200 03> u 3.0000 ”0 .wEhm ”080230008380000000 22 N 0803.50 [IV 03> H 38.3 ”03003000000380 03> n 3000020 002 n 002 0.00038 0%08000083w0lm AA00 _ _00.VV AV 000303 ” 3.000032002083002 ”0:_0>30:.0>0_w0_wbo:_0 000303 N 30w:0O0.:wc0000. 000303 n 305 ”08800w300030w:000.:w3000 000080200»... ” 3000Q0w:0w 9.0. H 300000000003 3.088800%:00 0w:00_ AA0000.0.0_VV 0000. 03> ” A0005 ”0.0530030305300 000000 N 3000003 33% n 3000002 ._00w0_0002b.000.00:_0> n 38.5 ”0800380002003 03> u 3_00w0_0002b.000.00:_0> 38000838000230 _ wEhm ” 38088000000008 w0_..m ” 3080Z0w00w 002 “ mw0_0008l8 000000 ” 000003I8 205 n 0.80I8 0:05 “Bus wEbm 300880000030. 0.8.5 ” 080200030. 00000000300000§00 00008020000. ” $8.0m ”080030:_0>00:000000¢ 03> H 33008020000. ”.00030:.0>00:0000000 wEbm ” 3000880000». wEbm “ 300»r_.0w:0w 00003000300000.0300 H 38.5 0008800003 .mEhm ”00.p0w:0w30000000_00_08 0000000000900W¥00 Figure A.1: UML class diagram of the Rainbow Adaptation Framework [16]. 185 SNMP4J-Agent [24]. SNMP4J [24] is an enterprise class (open-source, com- 111ercial) SNMP implementation for the JAVA language. In particular, the SN MP4J- Agent is capable of periodically polling various SNMP—conforming entities across the network. Figure A.2 shows a UML object diagram of the SNMP4J-Agent [24], which is similar in structure and behavior to the Sensor-Factory (4]) pattern. In SNMP4J, a user enters commands through a CommandProcessor, which then submits each re- quest to the RequestFactory. Likewise, various Clients in the Sensor-Factory (41) pattern submit their monitoring requests to the Sensor-Factory. Once the Request- Factory receives a request in SNMP4J, both a SnmpRequest and a RequestStatus are created. These two constructs facilitate the tracking of requests as they get processed through the system. Once a SnmpRequest is granted, then the RequestHandler creates a Snmpv2MlB, which is an interface through which the user can obtain the monitoring information he desires. Likewise, in the Sensor-Factory (41) pattern, when a request for a Sensor is granted by the ResourceManager, then the Sensor-Factory returns the requested object to the Client. 186 0000003508360:000085 mm 0 0 0. 0 V 0000000085 AV 000000035 AA000...030 _VV 30053000000 30000.0 ,_ <— 8333053000000 _ *.._ 4 300.5303 5000003000030. 0 E00000 AA0000.08_VV 9 0. 3.0300 3030003000000 0.202.505 * mow: :— _ 3300800008800 A 30000.0 8.0003300003— Figure A2: UML object diagram of the SN MP4J-Agent [24]. 187 A.2 Reflective Monitoring (50) Pattern Adaptive Exception Monitor [19]. The Adaptive Exception Monitor im- plemented in [19] is based on the JAVA reflection package [25]. This exception monitor exploits the intercessional processing capabilities of the JAVA language and runtime system to transparently inspect each exception generated by pre—specified objects. Each exception is logged into a knowledge-based of the autonomic element for further processing and analysis. Figure A.3 shows an elided UML class diagram of the Adaptive Exception Monitor [19]. Strong similarities can be observed be- tween the Adaptive Exception Monitor and the Reflective Monitoring ( 50) design pattern. In. particular, both make explicit use of MetaObjects, Proxies, and lnvoca- tion Handlers. MetaObjects provide information about a particular type of object such as its structure, attributes, modifiers, and interfaces. Proxies make use of the infor- mation provided by the MetaObject to provide a functional and transparent wrapper around some specific object. The lnvocationHandler is then able to intercede when- ever a targeted method of a Proxy is invoked. Specifically, application-specific data is logged before and after these methods are invoked by the Proxy. Furthermore, lnvoca- tion Handlers can link various monitoring Proxies together to construct more complex forms of monitoring. One notable difference between this sample instantiation and the Reflective Monitoring (50) pattern is that in the Adaptive Exception Monitor. the equivalent of Manager is implemented by Controller. Although similar in respon- sibilities, the Controller is decentralized in the sense that each lnvocationHandler has its own Controller. Thus, instead of there being one centralized Manager that tracks the various monitoring Proxies, there are several of them interspersed throughout the implementation. 188 20> “ A. 205 u E :02 0.. _ 00:03:00 009052.: 000.30 H .0 00,500. 80.30 N 0090500: I. 60.30 H Ewcfirfia .E ” _0>0_I:0E 50.30 ”E0000 .0_Ucwzco_auo>:_ f 00062: AAO~ _ .00._vv _ .0_0:0I:o_aoo>:1_>_ H 300.30 u,Afimvbficmzcosaooé20w 80.30 H 200020005 “0000:0053:Exoisac 0.00.0 H eggsmwmc :0umocmmm_0.?ois0w 05$ _ 3:000:30 cog—ESE .0w _ 4 *z _ 22 u :02 _ _ E_ n _0>0_i:oE A.l._ _ s 3 _ see. __ 59.30%: E 35:; 50.08 U 320.; ynEmeEflcoo 20> H 2on “.AEEPEEE 20> H CxommgoEE 20> H CEoEoEEE EC.» U C980; ”.Afiavxummcbvum 20> U 255 c?.&.=o._.._o._.gm 20> “ 205$ ”zfigccfiomfiunm 20> ” 27.05 uAEQVEoIEu—um :00.000 U Cxonmz $00.95 N waEELE 52002 H CEOEE 20> N 30030 ”onowcmtgmam 20> ” 30030 ”Bozowcfirsiam 30> u 300.30 ”_.noz0w_0,_.;0zd0m 80.30 ” 90whmtw0wz0w 8030 H 90w53>0$~0w 50.30 H C~0wen._.;0z.0w 20» N 3on ”.AEEEBHNLBm 20> ” CE u_0>0_I:oE:0>0J:oE~0m E_ ” C_0>3:0200w 20» u C0:3m_x::0>m :2 n.EErocgmfiscgmhigm 00.30 H 66., “.33.?ci05000 BicmzcozsooEZE AA00300E _vv Monitor [19]. ion UML class diagram of the Adaptive Except Figure A.3 189 Reflective Monitoring of Real-Time Systems [5]. Monitoring mechanisms in real-time systems must not introduce a significant overhead since the process of monitoring is already computationally expensive. One approach to monitor the exe- cution of a real—time system is to exploit reflective programming through the use of meta—level objects. Figure A.4 shows a reflective monitoring approach for monitor- ing real-time systems [5], which is similar in structure and behavior to the Reflective Monitoring (50) pattern. Specifically, both approaches separate base-level objects from meta-level objects, which contain information about base-level objects. In the reflective monitoring approach presented in [5], every object that will be monitored, such as Task, must realize a MetaProgram interface. It is through this interface that other objects are able to probe for the desired information. This approach is simi- lar to the one found in the Reflective Monitoring (50) pattern, in which Metaobjects provide an interface to base-level objects, such as Target, so they may be probed by other objects. Note that there is no explicit use of a Proxy in this approach since every monitored object directly implements the Meta Program class. Nonetheless, the monitoring procedure works similarly. Whenever a predetermined event occurs, such as a method call, the Monitor collects the necessary information from the MetaPro— gram. This process is paralleled by the lnvocationHandler in the Reflective Monitoring ( 50 ) pattern. 190 39:02 _ £90 00w _ _ Ea .; mafimEBmzm A 08:52 _ g... _ £50 00w :00 _ 350 00w _ :00 :5 wsEFQ EEwoiéB—z A u .. n 1 =55 . _ I p 39:82: 50:39.2? 59:0 Figure A.4: UML object diagram for Reflection-based Monitoring of Real-Time Sys- tems [5]. 191 A.3 Content-based Routing (59) Pattern Rebeca Notification Infrastructure [83]. Rebeca is a content-based pub- lisher/ subscriber service that has been extended to support mobile computing [83]. Their middleware-based approach enables existing applications to be adapted from a static to a mobile scenario without having to adapt client applications. Figure A.5 shows a UML class diagram of Rebeca as it relates to the Content-based Routing (59) pattern. Figure A.5 shows a simplified UML class diagram of Rebeca as it relates to the Content-based Routing (59) pattern. The specific UML class diagram was obtained from Rebeca’s documentation. Although Rebeca is a sophisticated content-based publisher/ subscriber implementation, strong similarities can be seen with respect to the Content—based Routing (59) pattern. In Rebeca, an EventBroker acts as an access point to the publish/ subscribe system. It is defined as an interface so that different EventBrokers can be swapped in or out as necessary. In terms of the Content-based Routing (59) pattern, the EventBroker maps to the Manager class. Although Manager is not defined as an interface, it provides the same functionality as EventBroker. Rebeca also defines a Filter and two subclasses Subscription and Ad- vertisement. These correspond to Filter and Pattern in Content-based Routing (59), respectively. Specifically, an Advertisement is used to identify the origin of the data being published to the EventBroker. A Filter, on the other hand, is used to select a specific event in the EventBroker. Finally, notice that Case-based Reasoning (667’s Server and Forwarding Table provide similar functionality as EventTransport and Rout- ingTable, respectively, in Rebeca. 192 e. 8000800503. .0 5508:3895 22 c 00:53:088E0>u< 20> c cozmvzouatomazw 20> 308002.025. 0030535 0 0:35:83. :00.000 b2...... 30.5 a... _ .. - 005.0: ... c 00:000 0 E0>mz=0>mfit3 20> __ _ 9:05.000. :05 _ _ _ 03%| 0Ew=mw=5=oa camcetcofi 0.0255800 _ Seem—830850”. - fi _ _ AA00N:00._VV _ a: 0 oo 0— _ 4 _ 3 0:0E0m_:0>0<00m_:0>00§ Ros A0 E088E0>c00 20> Am 535350005802: 20> 030,—. wESom Goa $0005.55 .0 85053500800003 20> 8.501033 22 80.29530. AA000t0EVv Figure A.5: UML class diagram of the Rebeca Notification Infrastructure [83]. 193 Siena Routing Infrastructure. The second Sample Instantiation is taken from the Siena Routing Infrastructure [14, 43]. Siena is a wide-area event notification service based on a publisher / subscriber architecture. Siena routes messages across a network based on their contents. Specifically, clients send a Subscription to the Siena service. A Packet Receiver stores the incoming Subscription. Although the Content-based Routing ( 59) does not have a Packet Receiver, Clients still submit their Subscriptions to the EventService. After some event occurs, a Notification is sent to the Siena service. Since the Content-based Routing ( 59) pattern is oriented towards monitoring processes, Notifications are explicitly sent from Sensors. This restriction, however, is not evident in Siena. Both Content-based Routing (59) and Siena use a series of Patterns and Filters to map notifications to Clients. Specifically, each update is characterized by a Pattern that identifies the update source. The Event Service then applies a Filter to the update to determine which Clients should be notified. The PacketSender then proceeds to send a Notification to those Clients. 194 and cos—005002 and 020: _ Stamgscoc qu 50005.0: 0:00. Eozmm a... _ 300—00 _ azésoz .Essfivzcosas *..o 0:0 :0 toms—0m 8000:0003: D *..o 0:003:00: .003 0.000: E025 000598.00; 00x0>:_ 0:280:00: :20. 00:83:38.0 195 300 0.1000: _ 800 0:00 030:qu .000—5000:0322: Awfibm .000—£000E0>00:: 0.005002 .._0.__..:0£._000:m CE: 25080 823232. Aw:t0mvm:o_atomnam000_ 0205300309020 0:05. 02:02:22 00530005 3020.502: 350m .000—5000?.03020 033053000550.— azssaz .EsEVBEBa 92:083.: i ecsscsozzezsa _ ties *.._ 95.32808 Aw:_.:m .000—5003:0300 08—w— 0:05 Figure A.6: UML object diagram of the Siena Notification Infrastructure [14]. A.4 Case-based Reasoning ( 68) Pattern ForkLift Agent [4]. The ForkLift Agent application is a simulated multi-agent system that uses case-based reasoning as the main inference engine for task planning. Specifically, autonomous forklift agents unload, transport, and stack crates from a truck to a determined location in a warehouse. Agents are equipped with sensors to interact with their environment and communication channels to relay important in- formation to other agents. Figure A.7 shows the UML class diagram for the ForkLift agent and its case-based reasoning constructs provided by the FraMaS framework [4]. The case-based reasoning used by the F orkLift agent is similar to the one presented in the Case-based Reasoning ( 68 ) design pattern. Specifically, both accept some form of event input from the environment and match it against predetermined conditionals. In the ForkLift agent, this task is performed by the Matching class, which searches through the CaseLibrary for a conditional that satisfies the triggered event. Addition- ally, the ForkLift agent attempts to assimilate similar, yet previously not encountered events. to those found in the CaseLibrary through the Ranking class. The Ranking class takes some event and produces an ordered list of the most applicable cases stored in the CaseLibrary. Once a matching pair of events-case is found, then the appropriate plan is loaded by the CaseAgent. Note, however, that the ForkLift agent is not able to learn new pairs of cases and actions as Case-based Reasoning ( 68) does. As a result, the Learner and Log found in Case-based Reasoning ( 68 ) is not applicable to the ForkLift agent. 196 CoEESfimEEN: . CwEfiE—éom 055508003. 05020200000 _ 5000 030:0. cast Cam—U yum—U ? 00x02: _ 0:: 500:. 0000500000 0000 0505. 00050000 0000000» 050550000 30550000 00000000 _ _ 0005003000 C:0030:<00:00000£ 0090 0:03. C000302000m 300.055 000:2: 0:0: C00=E_m Ow:_v_:0~_000 0050:0060 00:32.02 0:20:02 :0N>_0:<00:0._0m0.£ EMwl< CE: :o_>0:0m00o:0>_0< m:o:0<0:0w<0_m0m 000.03.: 00000 0:000 005055 03:20 00005200 0:05”. 0:00:00 00w 0:: 05— game 000020900 000002500 00:8 25 C:o_0:_om00w O:oc0a_m00w 00:00 030300000 E0w<0000 _ 028% Cm:_0_:0~:0w ©000m00w 0050.500 [00:50 Figure A.7: UML class diagram of the ForkLift Agent [4]. 197 UM-PRS [60]. The Procedural Reasoning System (PRS) is a generic case-based reasoning system that can be applied in domains where procedures are available for handling predetermined situations [60]. Figure A.8 shows an object diagram of the UM—PRS system being used to control a real outdoor vehicle that changes its behavior based on what it senses from the environment. UM-PRS is similar in both structure and function to the Case-based Reasoning (68) pattern. Specifically, as new inforn‘iation is obtained by a Monitor, the Database searches for any particular matches. If an event is matched in the Database, then the Interpreter obtains the corresponding plan from the KALibrary. Likewise, the Case-based Reasoning (68) pattern receives notifications, in the form of Triggers. Each Trigger is processed by the InferenceEngine in which it attempts to match the Trigger against a particular Rule in the FixedRules object. If a Rule matches the Trigger, then the InferenceEngine produces a Decision which contains the appropriate response plan. Note, however, that the UM-PRS does not have any mechanisms present to facilitate the discovery of new rules once the system is deployed. 198 0:08:50 0:95:00 00:00: 0.302% 000:2:— 0.000 _ 0.00m 00w 0000505000 00:0 0:0.0 00m _ _ 00000 00w ban-1— 0030:=000EF0000=0> 2862 ” 0:323:00. a 00000 0000::805:.s00_0> 05.50 0 0.0203 29 u 9.0 _ 22 ” 0:0 3:05 M 3:05 n 2030300000 000.QO *z _ :00.000 ” 300000002 ”5300: .ll 06> ” 000005000 06> H 060.000: ”00020:? .3005 “08026000068050 06> u 000.05.250— 0§QO ” 3:05 ”08028300003503 02.858000550229000 ” 0600006005003 60000002 u 3:05 “08026000050033 HE N 30030 ”00000000800 =50 N 00250000000000 :0 ”000.502 0:50 “0051.503 _ 000.0 N 00.21502. .5 “0200000009200 :00.000 “ 330000020m “5000000005. 06> ” 0000000:QO 03000000080000.0000 06> H 3:300:50 29, n 808552 éfizea 06> ” 3:05 “0300050E 22 ” ceé 00:000.”.— 00m0m _ 30000:. 0:00 828229000 0600:3060 00w asses: ” 002903 *.. 0030:0200050m u 0630:0303 :00.000 H 005QO H000005000 00280 n 3000000 ”80.000.030.000 :00600 ” 800000002 ”:0000 3:05 0805:0030? 0:30 n 32030808 80800000055022.0005 ”08000 .05 ”002000000360056005000 06> ” OE: 06> ” 3:05 ”00060500500 06> ” 300000002 ”5300: 06> M 3:05 ”0000:0200; 6000> H 00600006005003 06> ” 3:05 ”000.:M0>OE0~_0_E0:»0 :00.000 H 90000063505000.2200QO 0300020000QO _ 0.. _ 0006>:_ _ 06> H 0:300:20 06> 0 0E ”0:059:002E3900000 06> “ 05: 06> n 300000002 ”5300: 06> H 3:05 ”03:00:03. 5:009:20 Figure A.9: UML class diagram of the XUES Event Distiller [37]. 201 Software Health Monitor [59]. Figure A.l(') shows a UML object diagram of the software health monitor presented in [59]. This software health monitor is responsible for processing monitoring information. Specifically, as a Sensor provides information about a particular entity in the system, the Indicator determines whether those values are within zweeptable bounds or not. Information from the Sensor is obtained either through the Observer, when the Sensor pushes new information out, or by polling the Sensor directly whenever the Timer determines that a timeout has occurred. If the values re1')orted by the Sensor are deemed unacceptable by the Indicator, then a notification is sent to the HealthMonitor. A similar structure and functionality is prrwided by the Adaptation Detector (88) pattern. In the Adaptation Detector (88) pattern. an Observer is responsible for both receiving and polling the Sensor for Data. ()nee Data has been obtained, the Healthlndicator invokes an Analyzer to compare the monitored values against specific Thresholds. If any value exceeds its corresponding Threshold, then a Trigger is created by the Healthlndicator and fowarded to an entity responsible for determining how the system must be reconfigured. 202 i. a o__:3*:r— E<__°‘-§ B a) O V) t’. O o. 2 a) .o L- Q. ‘5 i— ‘5 a) 2<——._. E 2 _§*. [— "' 0...; a) H E *0 0* '5 O _:: < HealthMonitor Figure A.10: UML ob ject. diagram of the Software Health Monitor [59]. 203 A.6 Divide and Conquer ( 78) Pattern Care-O-Bot II [39, 40]. Care-O-Bot II is an experimental robot that provides human assistance such as fetching and carrying items around a room. Robots such as Care-O-Bot II need an appropriate control system that achieves high-level complex goals while interacting with a complex and often dynamic environment. For instance, a seemingly simple goal such as “fetch cup” might entail loading an updated map of the environment, calculating the robot’s current position and the cup’s position, generating a navigation plan, moving towards the cup while probing the environment (to avoid collisions), managing battery power consumption, and so forth. Task de- composition. is a commonly used approach to decompose complex goals into simpler goals that can be readily solved. Care—O-Bot II incorporates the metric-FF task de- composition module based on the Planning Domain Description Language(PDDL) [45]. Figure A.11 shows the metric-FF task decomposition module [45] that is used by Care—O-Bot II. In metric-FF, Main sequences the process of task decomposition. Essentially, Main combines the functionality of Solver and Inference Engine from the Divide and Conquer (78) pattern. lex-fct-pddl uses the scan-fct-pdd|.y, scan-ops—pdd|.y, Ix-ops-pddl.| and Ix-fct-pddH files to perform lexing tasks. Main begins by lexing and parsing various files through the lex-fct—pddl and Parse classes. These two classes correspond to the Lexer and Parser classes in Divide and Conquer ( 78), respectively. To represent goals, metric-FF uses the State class. Metric-ff then uses the Search class to perform an enforced hill-climbing with deletion heuristic search. Likewise, the Divide and Conquer (78) pattern uses the Informed class to employ heuristic- based searches. Both Divide and Conquer { 78 ) and metric-FF rely on known facts (KB and Fct, respectively) to guide the search process. After the search process yields a solution, metric-FF invokes the Orderings class to produce a sequence of tasks that 204 £00.. 003 30500... 205 :30... 20503012100500. Cm0. *000200mv:0_n.l000.:x0 .oom H A: * 000200000000.00Im.0wl.003|>>0: .00m “3... .5 is... 200 .g .5 .50... 0.0500.00mI000001000100000m .oom ” 20:0... 0005 .00.!n 250052,:642685.518 h .ocm C00:0m0|.0owl0..=n. H E 0:00.05050043080 A 00.: 0002005: 000..0I.00000 C00:030I.003I00=0E00 $600000 6028 0:0 C::3:I.0.0000J:0 00.00000 3:.0E 00:00.. :000< 00:00.. , 00005 $0.... 0000 .000 2:: 0002. a.Z000...I00I:000:=.EO0100.0E .00: H 2:... 0002_LA_0._2..I0..0I0_ .00m ” 2*... 00027. 1:0000I00I:000:0.300I040E .00». H C:.0E00i.00l00.0E E. H :3... 00000000303 0E0; E05. _. 02-50-: _. 60050010. A. 60050010000 A. .000I.0..I=00m _ . C:0EI.:00 A00 :000 ” AV0.07].0.0001081: 0.031% A H A .0.0.mlm=0.>0al.0wt_2 03-8.32 Figure A.11: UML class diagram of the metric-FF (Care-O-Bot II) [39, 40]. 205 will satisfy the overall goal. Likewise, Divide and Conquer {’78) employs the use of a Dependency Calculator and a Planner to organize the tasks. F inally, metric-FF an Output class to format the solution in terms of Actions. 206 Rainbow Adaptation Hamework [16, 27]. The Rainbow framework incorpo- rates a task decomposition approach when selecting a reconfiguration plan to apply at run time. Figure A.1‘2 shows an object diagram of the various entities that make up Rainbmvs task decomposition approach and how they each map with respect to the Divide and Conquer ( 78) pattern. First, in Rainbow, a Goal is represented as an architectural constraint that must remain true throughout execution. The Stitch Language Interpreter [16] is used to translate the utility formula, tactics, and strate- gies provided by the developer into an internal representation used by Rainbow at run time. The Stitch Language Interpreter provides a Lexer and Parser to provide these functions. Rainbow’s Inference Engine is utility-based (described in TradeOfi-Based (106)). The Dependency Calculator and Planner from Divide and Conquer {78) are implemented in Rainbow as Strategies. A Strategy is used to group different tactics (Tasks in Divide and Conquer (78)) together into sequences and alternatives that work together to repair the system after a constraint has been violated. Lastly, the Solver class found in Divide and Conquer (78) does not exist in Rainbow per se. Rather. this capability is handled by the Rainbow framework as a whole. 207 053540 005000:— 0000903003 > _ 80.00.00 _ 300005 806036 l7 _ _ moxo>:. 00205300500 0000 P *.._ *z. 00.009005 030:3:3 000.5 0080:6000 0:000:00 003080.05. Figure A.12: Object Model for the Task-Decomposition Pattern in Rainbow [16, 27]. 208 A.7 Architecture-Based (.97) Pattern Rainbow Adaptation Framework [16, 27]. The Rainbow adaptation frame— work uses architectural models [28] as part of its decision—making process in two key ways. First, Rainbow analyzes probing data against architectural model constraints to determine if any properties have been violated during execution. If a property has been violated, then Rainbow triggers a reconfiguration request in order to restore the system to safety. Second, Rainbow uses architectural models to determine which reconfiguration plan to apply. Specifically, various architectural models are evalu- ated and if they satisfy the adaptation requirements, then they are executed. Figure A.13 shows a UML class diagram of the various entities in Rainbow that provide architecture—based reconfiguration, which are similar in both structure and function to the Architecture-Based ( 97) design pattern. For instance, in Rainbow, the Adapta- tion Manager is akin to the EvolutionManager in the Architecture-Based (9’7) pattern. Both are responsible for overseeing the safe reconfiguration of the application when- ever a property is no longer satisfied. To determine when a property has been violated, both Rainbow and the Architecture-Based ( 97 ) pattern rely on architectural models, model repositories and utility functions to evaluate the effects of a model before it is applied. Rainbow wraps Acme constructs (components and connectors) with Rain— bowModels, which implement the interfaces of Model and ModelRepository. Although the Architecture-Based (97) pattern does not explicitly include Acme models, similar component-connector models are encapsulated Within ArchitecturalModels. Given the amount of architectural models possible, both Rainbow and the Architecture—Based (97) pattern include some entity to manage the set of models. This management func- tionality is provided in Rainbow by the ModelManager and by ArchitecturalRepository in the Architecture-Based (97) pattern. Lastly, the ArchEvaluator in Rainbow evalu- ates whether a specific architectural model satisfies a set of properties or not. The same functionality is provided by the ConstraintChecker in the Architecture-Based (97) 209 pattern. Thus, when a property is violated, the decision-making process searches for some architectural model that corrects the problem and propagates the structural changes. 210 06> ” C:000<:_: 06> ” 3:05 5330. 06> ” 30800.0 06> H 060033965. _ 600205002...~ 5053 00000.90 0... _ 00:000.0:0>m_>>00:.0m. ” 3:05 ”0.00:00055600 000.00 H A00:0am:.0:0E0.m0E0<. ”0 3:05 ”0:00200000.200005608050000.0 06> ” C:000<:E 06> “ 3:05 ”0530. 22 m sea 06> ” 00800.0 06> n 9033026003. 00w0:0.>:000.>. :00.000 H 000000050. 06> ” $002.00 3: 05 ” A00:00m:0:0E0.m0EU<. 0:080.0v:000000:0::0.m00w 06> ” 90002300500 0030:08 "w..— :00.000 ” 00.030006000000030 :00.000 H 00.0.0.>0:.000:00IE :00.000 ” 003:0..00000IE .000—20803 H >:m030|_.: .000.>.0E0<_ ”0E00IE 08.238500 06> “ 300.00 0000:9000260000500wn 000.00 M 3:05 H 08028000503060.000—>003 . . . AAmOE _wo._VV _ _ _ 4 AAm 0N . _w00VV _ 22 “ 08059028 06> ” C:000<:_: 06> n 0300005 U 0.0005005320050008 :00.000 u 3.000305560000000 06> H 06000000303300 06> ” E00600 ”£00.00:m:0000000<00m :00.000 H 300.00:m:00000000 06> H 3:05 5530. 06> “ $000000 06> H 9030:02:0000000< 0030:05. :0000000< 0000000050003. AA000000:.VV 6005306000 000.00 06> ”4000.06.25000600006 :00.000 “ 30000650505600. 06> ” 03500200000205 06> H 3003:00Ub0000k0006 :00.000 ” 00035005600500: 06> U 000.30 ”0:.0> 3:05 60000500002000: 3:05 u 3:05 “0.000000003505003 .0060 ” 3:05 ”0.300005003 08.30 N 00822000 00.30 N 008205300 .0002 AA000000:.VV Figure A.13: UML class diagram of Rainbow’s adaptation manager [16, 27]. 211 MADAM [64]. The Mobility and Adaptation Enabling Middleware (MADAM) uses componerit-connector models to represent all different configurations, or con- texts, that the system can adopt during execution. Figure A.14 shows an elided UML class diagram of the various entities responsible for managing the different forms of components and their connections in MADAM. Although MADAM is a complex mid- dleware that comprises several key components for automatically managing dynamic reconfigurations. it shares several key similarities with the Architecture-Based (97) 1:)atte1'n. In particular. in both MADAM and the Architecture-Based (97) pattern, every entity in the system is reI‘n'esented as both a set of components and a set of con- nections through which they can communicate. In MADAM, an InstanceManagement tracks all the component-cormector models that have been instantiated in the system. Likewise, in MADAM, a ComponentManagement is responsible for storing, searching, and evaluating all the different models. In the Architecture-Based (97) pattern, these functionalities are provided by both the ArchitecturalRepository and the RepairEngine. Although not shown in Figure A.14, in MADAM, every component-connector model is associated with a specific set of properties, which can be verified by the Adaptation- Management. Likewise, in the Architecture-Based (97) pattern, a ConstraintChecker evaluates each ArchitecturalModel to determine whether it satisfies any given property. ‘212 22 “ 002005500 22 ” 08:02:50 06> ” 35 06066 6000005828800 “N008 .00:000:0:0:0m800 ”20800080006 06> ” 3:05 060600 6053058060800 ”00:. 0083058060800 ”208000800 0,000.30 ” 0802 002000: .0802 “00:80:.08000000000063 0800058060800 0 $090,560 “0000 .0802 003000: .0802 u 00000508083600: 0:803:05 AA000008.VV 0:080w0:02m:.0:.m AA000000:.VV 060 06> ” 00600080.“. 6:000:0060006050680: 06> “00:20.4:07. 6:000:00600565000 06> ” 90.n— 800.805.5088. 29, u .50: 52350605 0000 “ 00700000800 0000603808903 0000 H 0002 ”000: 0070800005 ”08000000600060:00m *:0.n00000::00 u 00056000600 “000000:0E6000::000:0 0:05 H 00008060800 “0050:05806080060 80830528060800 AA000008.VV 06> ” 0005 “00000 0050058060800 00:00:. 06> ” A0802 “080208000:00060050680: 06> H 0802 u 08028000:58060808800608 06> H 0802 ”08020060088300800 0802 H 00.?8060800 80000000000060. 8080?:0200605 AA000008.VV . 8080m0:02:000&00< Figure A.14: UML class diagram of MADAM’s Core [64]. 213 A.8 TradeOfi-Based (106) Pattern Mobility and Adaptation Enabling Middleware (MADAM) [64]. The Mo- bility and Adaptation Enabling l\-'Iiddleware (MADAM) system uses utility theory in its decision-making process to select specific reconfiguration plans [64]. Figure A.15 shows an elided UML class diagram of the classes responsible for utility-based decision-making in MADAM. Although MADAM is a complex middleware that com— prises several key components for automatically managing dynamic reconfigurations, it shares several key similarities with the TradeOfi-Based (106) design pattern. Specif- ically. an AdaptationManager is responsible for reasoning on the impact of context reconfigurations across the system. To select a particular reconfiguration and execute it, the Adaptation Manager invokes the AdaptationCoordinator. The AdaptationCoor- dinator uses various EvaluatorAdapters and ConstProperties to quantify the effects of different reconfiguration plans. The reconfiguration plan that yields the best utility gain is selected by the AdaptationCoordinator and then effected throughout the sys- tem. Although not shown in Figure A.15, MADAM also comprises a component that arbitrates different context reconfiguration requests. Likewise, in the TradeOfi-Based (106) pattern, a Arbiter oversees the different requests for context reconfigurations. The InferenceEngine then determines whether any of the reconfiguration plans would yield better system performance than the current configuration. To maximize utility, UtilityFunctions are employed by the InferenceEngine to quantify the effects of a recon- figuration plan. Notice that MADAIVI makes no use of DemandForecaster to predict the utility outcome of different. reconfiguration plans l’)ased on previous knowledge. 214 20> H 200.004.35.59 ”0:800258090... 30> “ A:0_.0L:wc:000x:0:00_.002 “0:0.08wc:0_b.0m 20> H 2:080w0:0280:0080u_ “8:0M0:02.:0:0080U.0m 000.080F:o:0:=wc:0u u :03tion—005808080503: ”0 .8080580809 “0:_<:0..:00_0m0:<000:_0>0 20> u 880280—002 “5:300:8500 080280002 A: ”08028032055850 22;: L. c z . .1. “0 .0_0_080P:0:8=wc:cb 30333008081000 20> ” C:80:6:00U:0=0Eav< 20> ” c.0000 2.: u 80.3.4 ”N0 .wEbm “Na .5030 ”.0 .mEbw :30020805 002 N 20030 ”0 .wEbm ”30020808 Es» ” C0030 ”00.9.6005:ng Aromas—05:09 09088009888. 00< Bag—02:80. 00< .. 000.20 H 33.:0920E0E. : 05 , _ * _ ”0 458.05.38.09 “32030.6 \ :01 :0_m00<:o.0=_0>m 30: .028 AAm0N _ _00:VV 4 50.00 H 320802000305b05000 d .::080_m.23:05 ”32030.6 :0.0=_0>m.€000£ AA000t08_vv UML component diagram of MADA "I [64]. Figure A.15 215 Rainbow Adaptation Hamework [16]. The Rainbow framework incorporates an approach that maximizes utility gain when selecting a reconfiguration plan to ap- ply at run time. Figure A.12 shows an object diagram of the various entities that make up Rainbow’s utility—based decision-making approach and how they each map with respect to the TradeOfi-Based {106) pattern. First, in Rainbow, a Goal is rep- resented as an architectural constraint that must remain true throughout execution. The Stitch Language Interpreter [16] is used to translate the utility formula, tac- tics, and strategies provided by the developer into an internal representation used by Rainbow at run time. Rainbow’s Inference Engine is utility-based in the sense that it evaluates a set of different reconfiguration plans (Strategies) and selects the one that yields the maximum utility gain. Likewise, in the TradeOfi-Based (106) pattern, an InferenceEngine applies a set of UtilityFunctions to quantify the effects of applying a reconfiguration plan. Whichever reconfiguration plan yields the maximum value in terms of utility gain is selected by the InferenceEngine. Note that in Rainbow there are no DemandForecaster and Arbiter objects. Instead, Rainbow’s InferenceEngine is a centralized process that selects a reconfiguration plan only to repair a violated con- straint. In contrast, the TradeOfl-Based (106) pattern provides functionality support for users to submit different Objectives to the InferenceEngine. 216 0:_w:m 00:0..005 00037055 > _ 00030.00 $000.5 808090 luv _ _ m0¥0>:_ :030m30080m 0:002. tr..— *.._ 00:08:00:— 0w0=w:3 :0Em 88080000 *.._ 0808800 0.3000305. Figure A.16: Object Model for Rainbow’s Utility Decision-Maki11g [16]. ‘217 A.9 Component Insertion (115) Pattern Monitor Reconfiguration [7]. Figure A.17 shows the component diagram for the reconfiguration driver. This simplified component diagram is similar to the one presented in Component Insertion {115). Driver is the key component that oversees the reconfiguration process. To enact some of the changes across the system, however, Driver invokes the functionality of Change Manager. The reconfiguration consists of inserting a logging component between the Net- work (Network-comp) and Link (Link-comp) layers at run time (see Figure A.18). Their component insertion approach is similar in behavior to the one presented in the Component Insertion (115) pattern. First, both approaches load the respective com- ponent into the executing environment. In this specific application, the load command dynamically allocates memory to hold the logging component. Once the component has been allocated into memory, the component is then instantiated to either a default state or some previously stored configuration. Next, the Network—comp and Link-comp are. unlinked from each other so the logging component can be inserted between them. The process of unlinking two components from each other is handled by the ArchMM. Specifically, to unlink the components, the system must first passivate Network-comp and Link-com p. This passivating step is accomplished by sending a message to each component. in this case Network-comp and Link-comp, such that they stop producing output and accepting input from each other. Links are then prepared between the newly loaded component and the system. In particular, the logging component will be connected to both the Network-comp and Link-comp components. Again, this step is performed by the ArchMM by redirecting the Network-comp’s output to logging and setting Iogging’s output to Link-comp’s input. Once the links are in place, the Ioggingl component is activated. 218 20> H A0 88008003088 20> H AN0 80:00800 . 20 880080808: 20> H Amo 8800800 . #0 80000808088: 20> H A0 88008003038 20> H A0805 85508—028 20> H A0 88008080880008 20> H A0 8800808000— 2250.2. \7 _ AAm00208vv :0w0:02 I OWENSU I 00>EQ _ AAm0030EVV _ _ _ :0>_:Q I 58800.0. l Figure A.17: UML component diagram of the Monitor Reconfiguration [7]. 219 >000: 88: 358-02: 0500202522603 .AwEme .0800 8050200592252: 0:0:00800 ”N0 3:0:00800 ”.3080 fl 0>:0< o. F 08800800 Aw:_ww0_0000>:00 \ 0550800 ”30003000 > 002028 8800800 3800-085 08000—0030028882.22:0}? \ 3:0:00800 “N0 8800800 20:85:: 00:028. 8 0_ \ 3550800 ”000028038 80:00800 w:_ww0_ 00000. 3:0:00800 ”0:000. 088: 8000.? .025 Pan—m Figure A. 18: UML state diagram of inserting a logging component at run time [7]. 220 Conic [61]. Figure A.19 illustrates how components can be inserted at run time with the use of Conic [(51]. Specifically, a new display screen is added to the system at run time. The system must reconfigure its input and output displays to properly (’lisplay data on both screens. Behaviorally, the component insertion reconfiguration is similar to the one presented in Component Insertion (115) However, in this particular example. there is no need to either initialize a screen nor to passivate other screens in the system. As a result, the first step of the reconfiguration process is to create an instance of the display screen, screenl, to represent the new component loaded at sunl. Next, links are created to connect the two screens together. In particular, the output of screenl is connected to the input of screen2 and the output of screen2 is connected to the input of screenl. For instance. to set up screenl’s output to screen2, its output address is set to that of screenl and vice versa. Since every display screen remained active during the reconfiguration process, no activation commands are needed to terminate the reconfiguration process. 2‘21 0.0.. a, .© 0 r _ _ :208. 802% n _ _ _8080.~:00:0m 2:00:00 .~:00:0$0_8_ \ 3:0:00800 No 8800800 “—0008: 0:0 _ 000.8— 4___808.N:00:0mn___808c._:00:0m F :00:0m 00000Ltl .088 B :85 .:00:0m 3050808 u N:00:0m \ 380800 . 8008308: \ 80.00004 ”— .8800800 ”000.005 3:0:00800 ”N0 .80:00800 ”—000.8— Figure A.19: U ML state diagram of inserting a logging component at run time with Conic [61]. 2‘22 A.1O Component Removal (125) Pattern Mobility and Adaptation Enabling Middleware (MADAM) [64]. The Mo- bility and Adaptation Enabling Middleware (MADAM) [64] is capable of inserting, removing, and modifying components at runtime whenever a context change occurs. Figure A20 shows an elided UML component diagram of MADAM. Figure A21 shows a UML state diagram of how MADAM removes a component from the system at runtime. When a reconfiguration is required, the Ada ptationManagement is notified of a cmitext change. The AdaptationManagent then invokes the AdaptationCoordinator to evaluate and select the appropriate reconfiguration plan, which in this case is a component removal. One of the key steps in removing a component is first placing it in a quiescent state. AdaptationManagement accomplishes this by sending a suspend notification to the corresponding component, which must implement the Configurator interface. The suspend function is implemented independently by every component that is managed by MADAM and it ensures that the component will not initiate any new transactions and that it will terminate any transactions that may be pending. Once the component. is in a quiescent state, the AdaptationManagement proceeds to unbind the component from other components in the system. The unbind operation essentially disconnects the component from the system. Lastly, once all connections have been severed. the AdaptationManagement issues a command for the core system to unload the component. 00858800800000 C0000m::0:00800:0w C0002». 0:00:0w 080080 008.805. 9:8 08:. 80> Agra 0:00>0:0 0888—8800800 ”~08. 0800808800800 “—00:90080080 80> ” 3:th 0:00>0:0 0800808800800 “N08. 0800808800800 f8§00800 "100.50 H 0802 ”:0>.0m0: .0802 00:0.8.0800d0~.08:0:0w 0800808800800 ” 20.00.20.800 ”8:00 .0802 202000: .0802 ” 08008008030380: 8080w0:02$:]=08m AA0000:08.VV 0.0088800 0 5:080. .800 0:00 80> ” A:0:00m...:0.0 080:0.880.058.00.680: 80> ”2:0:0:m.1_:0.0 080:0..v:0:0.m...:0.0000 80> ”80.0 80.080.08.88: 80> H 80.0 808880.138. .000 ” 80.0:900800 ”0003000088898 500 n 0002 ”000: 80.08.0005 ”08000000055880.8:0w u_.:0.0:0:00::00 H 00088000800 ”00038800000800.80 u..:0.0 ” 00088800800 ”008080.0880080080 80888028800800 AA0000:08.VV 80> ” 0:05 “0:000 0800088800800 08.88 80> ” A0802 ”080208008.008008_0>080: 80> “ A0802 ” 08028.:00:58800800028888. 80> a 0802 ”08020806883082? 0802 H 0088800800 80.008.0008800. 808880208008. AA0000:08.VV .00: H 0808080800 . 8080m0:02:0.§000< Figure A20: UML component diagram of MADAM [64]. 2‘24 0000080080 0 380.502 \ . 00.80080Hn080m8800 80000w. 503.. 30020000000008.0388 08800800 _ 080000.00 000 8803 20.0.0.C080.080:08:00.50.>. \ 30.80080 nu 0000m80co080000w0080.0 05% 00.80080 nu 00058800800008.0002. C0880 8002000080008 T0888 8.80:0 28$.0.800880008wc000< \ f .0wc0c080800. 30020088088080. 200208080.0880080085 _ 0_Eun0w:0~.08 0800 _ 0.8 v.08 Figure A21: UML state diagram of removing a component at run time with MADAM [64]. 225 Mobility and Adaptation Enabling Middleware (MADAM) [64]. Figure A.‘20 shows an elided UML component diagram of MADAM [64]. The Configurator component defines the interface that must be implemented by all components in the MADAM system. This interface explicitly defines all the possible execution states for a given component. Figure A22 shows a UML state diagram of all the possible states that a component may undergo within MADAM. More importantly, this UML state diagran‘i also shows the specific sequence of execution states that a component must undergo when being inserted and removed from the system. In particular, notice that. when a component is in the active status, it must enter the suspended status before MADAM may remove it from the system. In MADAM, When a component enters the suspended status, it may no longer communicate and collaborate with other components. 226 $800.50.). \ 00.00.800.80 . _00.800mamnu0§m880080000w 80.): 28.200308000880800 08800800 _ > 000.002.0880 80.808.00.503. \ 3080080 un 00890000080000.0800 0.00... 00.8008; nu 0.058800800000802. C8080 800230080080 r _ 2.0200988088008000:E 080000.10 1‘ A 708800 m:.w:0:0 000 8.0.0.5 .20020800880088.800<\ y .088080800. 28200800058080. .88uu0w88080802 22 28m Figure A22: UML state diagram of a component’s states in MADAM [64]. 227 A.11 Server Reconfiguration (135) Pattern Reconfiguring Servers in Equus [52]. Kindberg described how to safely recon- figure a server architecture at runtime in [52]. Figure A23 shows a UML component diagram with the key entities responsible for reconfiguring a server architecture at runtime. Figure A24 shows a UML state diagram illustrating the process of recon- figuring a server architecture through the use of proxies. Specifically, the solution is centered around a generic server Proxy such that it interacts with both Clients and Servers during the reconfiguration process. That is, during normal operation, the Proxy forwards all incoming Client messages directly to the active Server. When a reconfiguration is required, however, the Proxy queues incoming Client messages into a Buffer. l\-’Ieanwhile, the system waits for the active Server to finish servicing all pending transactions and then enter a quiescent state. Once the Server is quiescent, it is deactivated and unloaded from the Equus distributed system. A new Server can then be loaded by the environment and initialized. After the new Server is activated, it will proceed to service all pending Client messages until the Buffer is empty. Lastly, the Proxy will reorganize connections such that new incoming messages are forwarded directly to the new Server. Thus, in this manner, the client/ server architecture is reconfigured transparently by means of a proxy. The same behavior can be found in the Server Reconfiguration (1‘25) pattern. Although the design pattern does not involve. a Proxy, the steps required to safely reconfigure an active server are similar. Specifically, incoming requests must be stored somewhere so they are not lost during the reconfiguration process. While incoming messages are queued, the Server will eventually reach a quiescent state. Likewise, after the reconfiguration is complete, the queued requests are serviced by the new Server. 228 8.0% u 080.02 80> H 3 8.098000 :00.000 ” 03.00.0080 00000 80> ” 3 W0.0mv00.>00m 7 80> H 3.800000 / 80> ” 30308000 / 80> H 30.0. / 80> N 00003000 / 8. u .800 / 000.000 H 03000000000 / hQZUm / 0 ., _ . . _ 00>.0m 80> ” 300000800 ”00.00080 80> H 300000800 “000000000 80> N 3030880 80> ” 000000 80> ” 300000800 ”00.000. 80> ” 300000800 ”0008.080. 80> ” 30.0. 80> H 30000003080 80> ” 300000800 ”000003000 000.000 N 00000 00> .00 80$. 80> ” 3.800000 80> ” 00.50.0080 80> H 3.000.000 80> H 30.0. 80> n 3000800 w80m u 800 .3800 Figure A23: UML component diagram of the Equus distributed environment [52]. 229 9000.0002005 00.00 n 0800000000 \ 73080000000 000% 0300008000— 30000003020 fl00000 w0.0.>00w 00.00n00000\ a g .000 ©M F00300.0 00000 A C00>00m >000 \ 00>00m w0.>080~_ # 30209000. . . 30000000.._0>00m< \ 308300003000 03.0.0080m< \ . 0000000000.... 1% . 00300300000>00m< \ 300000800083 00.0% ounm00000>00m_ 3030900080 000080.00 g 0:003 _1 300000000023< \ _0> 000000000— 308090000000 V 00t0m M00003 \ 0000>=0< 00>00m . . . r 0 fi 0. ”Meow—VON— wfl Cuoo.___uu...hxo._n_< EFF—O Z 000 u 080000.000 \ 30000— 300000 :03 Figure A24: UML state diagram of removing a server component at run time in the Equus distributed environment [52]. 230 A.12 Decentralized Reconfiguration (145) Pat- tern OpenRec Reconfiguration [44] . Figure A25 shows a UML component diagram for OpenRec, a framework for managing dynamic reconfiguration [44]. The UML component diagram highlights two key components in the framework, the OpenRec component and the Algorithm component. The OpenRec component manages the various interactions between components and connectors in the OpenRec system at any time. The Algorithm component is responsible for dynamically reconfiguring the components and connectors managed by the Open Rec component. Figure A26 shows a UML state diagram for a typical component removal in a decentralized environment. Specifically. the component that wants to disengage and terminate will first commence the reconfiguration process by blocking incoming transaction requests. In addition, the component is given enough time to terminate any pending transactions it may be currently servicing. These two actions enable a component to reach a quiescent state in bounded time. Once the component is in a quiescent state, it disconnects itself from other components. Lastly, once all connections have been removed, the component proceeds to call its terminate function, which cleans 11p any allocated memory and finishes execution. ‘231 300030000000 3000.008000000000 08.5808 3:000 38.00.0000 3000000000000 3000000000000 30000000000382 380000800000 38 0000800002000 3800008000380. 38050—00300 380>m_0.00_0 38000080000089. 38000080030000 38580000000800 30030800000000 0.M0_0000000000 00000w0000 850cm? 30.w0_000000008_000m.wq 30000080000030: 3032080000000 80000000000002.000003 300—0000000000. 50000000000000.5000? 338.03% A 000000000 38w:50000000000283. 0 00w00020.w0_0 30w000000a 38.00% .300 00w0002000000w000000 0 300000000000w. 30030020800820» 80000800 \7 _ . 0.8502 7 . *:_ m0w0008 3.000000 30000000000003 30000000000. 000020—000 \ 3000000000030 \ 90050020000000.2000. 80000800 7 .. \ Q * _ \ \ . \ 38000080008000 30000080000800 Figure A25: UML component diagram of OpenRec [44]. 232 000,080. # 33.800000 0000000000 _ 0r 3.000000m.0.000000800< \ 3800008000582 080000.00 w00.03 . 00000380000800< .A30000000000003.8800800< \ _30030000000300000800— 30000000000580. 35. .\ 0000838000.. _A 0:00 \ 530.00.00000000000. 300038000000 :30 Figure A26: UML state diagram of a decentralized component being removed in OpenRec [44]. 233 OpenRec Reconfiguration [44]. Figure A25 shows a UML component diagram for OpenRec, a framework for managing dynamic reconfiguration [44]. The UML component diagram highlights two key components in the framework, the OpenRec component and the Algorithm component. The OpenRec component manages the various interactions between components and connectors in the OpenRec system at any time. The Algorithm component is responsible for dynamically reconfiguring the components and connectors managed by the OpenRec component. Figure A27 shows a UML state diagram for a typical component insertion in a decentralized environment. The first task is to create and allocate the necessary resources for the new component. Then, the component that wants to engage will first commence the reconfiguration process by adding connections to other components it wants to connnunicate with. Lastly, once all connections have been established, the component proceeds to operate normally. 234 3 .o 0000000000 % > 3.000000800008008 _ 0207100.000000280000800— 3000000000000 0 00.0000 # a 00:05 A 80000800 _lA3800008000.0053900080000800< \ €00080w000000 L 380000800000 3:00.m \ 330.008000000002 30000 00000000 22 83m Figure A27: UML state. diagram of a decentralized component being removed in OpenRec [44]. 235 BIBLIOGRAPHY 236 [ll [2] l3] [4] [10] [11] Bibliography James S. Albus. Task decomposition. In Proceedings of the 8th IEEE Interna- tional Symposium on Intelligent Control, August 1993. Christopher Alexander, Sara Ishikawa. Murray Silverstein, Max Jacobson, Ingrid Fiksdahl-King, and Schlomo Angel. A Pattern Language. Oxford University Press, 1977. Robert Allen, Rémi Douence, and David Garlan. Specifying and analyzing dy- namic software architectures. Lecture Notes in Computer Science, 1382, 1998. Henri Avancini. Framas a java framework for multiagent systems. Master’s thesis, Buenos Aires National Central University, 2000. Ricardo Barbosa and Luis M. Pinho. Mechanisms for reflection-based monitoring of real-time systems. Technical report, Polytechnic Institute of Porto, Porto, Portugal, 2004. Luciano Baresi, Sam Guinea, and Giordano Tamburrelli. Towards decentralized self-adaptive component-based systems. In SEAMS ’08: Proceedings of the 2008 international workshop on Software engineering for adaptive and self-managing systems, pages 57-64, New York, NY, USA, 2008. ACM. Thais Vasconcelos Batista, Ackbar J oolia, and Geoff Coulson. Managing dynamic reconfiguration in component-based systems. In E WSA, pages 1—17, 2005. Karun Biyani. Dynamic composition of distributed components. Master’s thesis, Michigan State University, 2003. Karun N. Biyani and Sandeep S. Kulkarni. Building component families to support adaptation. In DEAS ’05: Proceedings of the 2005 workshop on Design and evolution of autonomic application software, pages 1—7, New York, NY, USA, 2005. ACM. Frank Buschmann, Kevlin Henney, and Douglas Schmidt. Pattern-Oriented Soft- ware Architecture: A Pattern Language for Distributed Computing ( Wiley Soft- ware Patterns Series). John Wiley & Sons, 2007. Frank Buschmann, Regine Meunier, Hans Rohnert, Peter Sommerlad, and Michael Stal. Pattern—oriented software architecture: a system of patterns. John Wiley & Sons, Inc., New York, NY, USA, 1996. Javier Camara, Carlos Canal, Javier Cubo, and Juan Manuel Murillo. An aspect-oriented adaptation framework for dynamic component evolution. Elec- tron. Notes Theor. Comput. Sci, 189:21—34, 2007. Carlos Canal, Ernesto Pimentel, and José M. Troya. Specification and refinement of dynamic software architectures. In WICSAI: Proceedings of the TC? First Working IFIP Conference on Software Architecture (WICSA 1), pages 107—126, Deventer, The Netherlands, The Netherlands, 1999. Kluwer, B.V. 237 [14] Antonio Carzaniga, David S. Rosenblum, and Alexander L. Wolf. Content-based addressing and routing: A general model and its application. Technical Report CU-CS-902—00, Department of Computer Science, University of Colorado, jan 2000. [13] Anil Chawla and Alessandro ()rso. A generic instrmnentation framework for collecting dynamic information. SI CSOF T Softw. Eng. Notes, 29(5):1—4, 2004. [16] Shang-Wen Cheng, David Garlan, and Bradley Schmerl. Architecture-based self- adaptation in the presence of multiple objectives. In SEAMS ’06: Proceedings of the 2006 international workshop on Self-adaptation and self-managing systems, pages 2~8, New York, NY, USA, 2006. ACM. [17] David M. Chess, Alla Segal, and Ian Whalley. Unity: Experiences with a pro— totype autonomic computing system. In I CAC ’04: Proceedings of the First In- ternational Conference on Autonomic Computing, pages 140147, Washington, DC, USA, 2004. IEEE Computer Society. [18] Geoff Coulson, Paul Grace, Gordon Blair, Wei Cai, Chris Cooper, David Duce, Laurent Mathy, VVai Kit Yeung, Barry Porter, Musbah Sagar, and Wei Li. A component-based middleware framework for configurable and reconfigurable grid computing: Research articles. Concurr. Comput. : Pract. E.rper., 18(8):865—874, 2006. [19] Dylan Dawson, Ron Desmarais, Holger M. Kienle, and Hausi A. Miiller. Monitor- ing in adaptive systems using reflection. In SEAMS ’08: Proceedings of the 2008 intemational workshop on Software engineering for adaptive and self-managing systems, pages 81'88, New York, NY, USA, 2008. ACM. [20] T. Dewitt, T. Gross, B. Lowekamp, N. Miller, P. Steenkiste, J. Subhlok, and D. Sutherland. Remos: A resource monitoring system for network aware appli- cations, 1997. [21] Yunsi Fei, Lin Zhong, and Niraj K. Jha. An energy-aware framework for dy- namic software management in mobile computing systems. Trans. on Embedded Computing Sys., 7(3):1—-3l, 2008. [22] S. Fickas and MS. Feather. Requirements monitoring in dynamic environments. re, 00:140, 1995. [23] Scott D. Fleming, Betty H. C. Cheng, R. E. Kurt Stirewalt, and Philip K. McKinley. An approach to implementing dynamic adaptation in c++. In DEAS '05: Proceedings of the 2005 workshop on Design and evolution of autonomic application software, pages 1-7, New York, NY, USA, 2005. ACM. [24] Frank Fock. The smnp api for java. http://www.snmp4j.org/index.html. [25] Ira R. Forman and Nate Forman. Java Reflection in Action (In Action series). Manning Publications Co., Greenwich, CT, USA, 2004. 238 [20'] [31] [32] [33] [34] [361 Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Pat- terns. Addison-Wesley, Boston, MA, January 1995. David Garlan, Shang-Wen Cheng, An—Cheng Huang, Bradley Schmerl, and Pe— ter Steenkiste. Rainbow: Architecture-based self-adaptation with reusable in- frastructure. Computer, 37(10):46-—54, 2004. David Garlan, Robert T. Monroe, and David Wile. Acme: An architecture description interchange language. In Proceedings of CASCON’97, pages 169- 183, Toronto, Ontario, November 1997. David Garlan and Bradley Schmerl. Model-based adaptation for self-healing systems. In WOSS ’02: Proceedings of the first workshop on Self-healing systems, pages 27* 32, New York, NY, USA, 2002. ACM. David Garlan, Bradley Schmerl, and Jichuan Chang. Using gauges for architecture-based monitoring and adaptation. In Proceedings of the Working Conference on Complex and Dynamic Systems Architecture, 1214 December 2001. K. Geihs, P. Barone, F. Eliassen, J. F loch, R. Fricke, E. Gjorven, S. Hallsteinsen, G. Horn, M. U. Khan, A. Mamelli, G. A. Papadopoulos, N. Paspallis, R. Reichle, and E. Stav. A comprehensive solution for application—level adaptation. Debanjan Ghosh, Raj Sharman, H. Raghav Rao, and Shambhu Upadhyaya. Self- healing systems - survey and synthesis. Decis. Support Syst., 42(4):2164—2185, 2007. Heather Goldsby and Betty H.C. Cheng. Automatically generating behavioral models of adaptive systems to address uncertainty. In To appear in the MODELS ( 2008 ) conference, 2008. Hassan Gomaa and Mohamed Hussein. Software reconfiguration patterns for dynamic evolution of software architectures. In WICSA ’04: Proceedings of the Fourth Working IEEE/[PIP Conference on Software Architecture, page 79, Washington, DC, USA, 2004. IEEE Computer Society. Michael M. Gorlick and Rami R. Razouk. Using weaves for software construction and analysis. In I CSE ’91: Proceedings of the 13th international conference on Software engineering, pages 23—34, Los Alamitos, CA, USA, 1991. IEEE Com- puter Society Press. Paul Grace, Geoff Coulson, Gordon Blair, Barry Porter, and Danny Hughes. Dynamic reconfiguration in sensor middleware. In MidSens ’06: Proceedings of the international workshop on Middleware for sensor networks, pages 1—6, New York, NY, USA, 2006. ACM. 239 [37] [381 [39] [40] [43] [44] [46] [47] [48] [49] Philip N. Gross, Suhit Gupta, Gail E. Kaiser, Gaurav S Kc, and Janak K. Parekh. Model for systems monitoring. In Working Conference on Complex and Dynamic Systems Architecture, December 2001. Jan Hannemann and Gregor Kiczales. Design pattern implementation in java and aspectj. SICPLAN Not., 37(11):161—173, 2002. M. Hans and W. Baum. Concept of a hybrid architecture for care-o—bot. In In proceedings of ROMAN-2001, pages 407—411, 2001. Matthias Hans. The control architecture of care-o—bot ii. In E. Prassler et al (Eds): Advances in Human-Robot Interaction, STAR 14, pages 321—330. Springer-Verlag Berlin Heidelberg 2005, 2004. James E. Hanson, Ian Whalley, David M. Chess, and Jeffrey O. Kephart. An architectural approach to autonomic computing. In ICAC ’04: Proceedings of the First International Conference on Autonomic Computing, pages 2~9, Wash- ington, DC, USA, 2004. IEEE Computer Society. Matthew J. Hawthorne and Dewayne E. Perry. Exploiting architectural prescrip— tions for self-managing. self-adaptive systems: a position paper. In WOSS ’04: Proceedings of the 1 st ACM SI CSOF T workshop on Self-managed systems, pages 75— 79, New York, NY, USA, 2004. ACM. Dennis Heimbigner and Alexander Wolf. Definition, deployment and use of gauges to manage reconfigurable component-based system. Technical Report A082924, University of Colorado, 2004. Jamie Hillman and Ian Warren. An open framework for dynamic. reconfiguration. In ICSE ’04: Proceedings of the 26th International Conference on Software En— gineering, pages 594—603, Washington, DC, USA, 2004. IEEE Computer Society. J. Hoffmann and B. Nebel. The ff planning system: Fast plan generation through heuristic search. In Journal of Artificial Intelligence Research, volume 14, pages 2537302, 2001. Christine Hofmeister and James M. Purtilo. Dynamic reconfiguration in dis- tributed systems: Adapting software modules for replacement. In I CDCS, pages 101 110. 1993. Gerard J. Holzmann. The model checker spin. IEEE Trans. Softw. Eng, 23(5):279 295, 1997. E. Kasten and P. McKinley. Adaptive java: Refractive and transmutative support for adaptive software, 2001. John Keeney and Vinny Cahill. Chisel: A policy-driven, context-aware, dynamic adaptation framework. policy, 00:3, 2003. 240 [50] [57'] [58] [591 [so] [61] Jeffrey O. Kephart and David M. Chess. The vision of autonomic computing. Computer, 36(1):41 -50, 2003. Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm, and William G. Griswold. An overview of aspectj. In ECOOP ’01: Proceedings of the 15th European Conference on Object-Oriented Programming, pages 327—353, London, UK, 2001. Springer-Verlag. Tim Kindberg. Reconfiguring client-server systems. Technical report, Proc. International W’orkshop on Configurable Distributed Systems (IWCDS94, 1993. Michael Kircher and Prashant Jain. Pattern-Oriented Software Architecture: Patterns for Resource Management. John Wiley & Sons, 2004. Fabio Kon, Manuel Roman, Ping Liu, Jina Mao, Tomonori Yamane, a Clau- dio Magalh and Roy H. Campbell. Monitoring, security, and dynamic configu- ration with the dynamictao reflective orb. In Middleware ’00: IF IP/A CM Inter- national Conference on Distributed systems platforms, pages 121—143, Secaucus, NJ, USA, 2000. Springer-Verlag New York, Inc. Sascha Konrad, Betty H. C. Cheng, and Laura A. Campbell. Object analysis patterns for embedded systems. IEEE Transactions on Software Engineering, 30(12):970—992, 2004. J. Kramer and J. l\'Iagee. Analysing dynamic change in software architectures: A case study. In CDS ’98: Proceedings of the International Conference on Con- figurable Distributed Systems, page 91, Washington, DC, USA, 1998. IEEE Com- puter Society. Jeff Kramer and Jeff Magee. The evolving philosophers problem: Dynamic change management. IEEE Trans. Softw. Eng, 16(11):1293~—1306, 1990. Jeff Kramer and Jeff l\-‘Iagee. Self—managed systems: an architectural challenge. In F OSE ’07: 2007 Future of Software Engineering, pages 259—268, Washington, DC, USA, 2007. IEEE Computer Society. Alexander Lau. Design patterns for software health monitoring. In ICECCS '05: Proceedings of the 10th IEEE International Conference on Engineering of Complex Computer Systems, pages 467-476, Washington, DC, USA, 2005. IEEE Computer Society. Jaeho Lee, Marcus J. Huber, Edmund H.Durfee, and Patrick G. Kenny. Um-prs: An implementation of the procedural reasoning system for multirobot applica- tions. In AIAA/NASA Conference on Intelligent Robots in Field, Factory, Ser- vice, and Space (CIRFFSS ’04), pages 18. American Institute of Aeronautics and Astronautics, 1994. Jeff Magee. Jeff Kramer, and Morris Slon‘lan. Constructing distributed systems in conic. IEEE Transactions on Software Engineer-tuft. 15(6), 1989. 241 [62] [0'31 [68] [69] [74] Philip K. McKinley, Seyed Masoud Sadjadi, Eric P. Kasten, and Betty H. C. Cheng. Composing adaptive software. Computer, 37(7):56—64, 2004. \N«'illiam E. McUmber and Betty H. C. Cheng. A general framework for formal- izing uml with formal languages. In ICSE ’01: Proceedings of the 23rd Inter— national Conference on Software Engineering, pages 433—442, \Nashington, DC, USA, 2001. IEEE Computer Society. Marius l\‘Iikalsen, Nearchos Paspallis, Jacqueline F loch, Erlend Stav, George A. Papadopoulos, and Akis Chimaris. Distributed context management in a mo- bility and adaptation enabling middleware (madam). In SAC ’06: Proceedings of the 2006 ACM symposium on Applied computing, pages 733—734, New York, NY, USA, 2006. ACM. D. Nau, H. Munoz-Avila, Y. Cao, A. Lotem, and S. Mitchell. Total-order plan- ning with partially ordered subtasks. In Proceedings of IJCA101 , pages 425-430. Morgan Kaufmann, San Francisco, 2001. H. B. Newman, I. C. Legrand, P. Galvez, R. Voicu, and C. Cirstoiu. Monalisa : A distributed monitoring service architecture, 2003. Peyman Oreizy, Michael M. Gorlick, Richard N. Taylor, Dennis Heimbigner, Gregory Johnson, Nenad Medvidovic, Alex Quilici, David S. Rosenblum, and Alexander L. Wolf. An architecture-based approach to self-adaptive software. IEEE Intelligent Systems, 14(3):54—62, 1999. Andres J. Ramirez and Betty H. C. Cheng. Verifying and analyzing adaptive logic through uml state models. In I CS T, pages 529—532, 2008. James Rumbaugh, Michael Blaha, William Premerlani, Frederick Eddy, and William Lorenson. Object-Oriented Modeling and Design. Prentice Hall, En- glewood Cliffs, NJ, 1991. Stuart J. Russell and Peter Norvig. Artificial Intelligence: A Modern Approach {2nd Edition). Prentice Hall, December 2002. Sarmad Sadik, Arshad Ali, Hafiz Farooq Ahmad, and Hiroki Suguri. Policy based ontology framework for mobile agents. In ACIS-ICIS, pages 483—488. IEEE Computer Society, 2007. S. M. Sadjadi and P. K. McKinley. Act: An adaptive corba template to support. unanticipated adaptation. icdcs, 00:74-83, 2004. S. l\’Iasoud Sadjadi, Philip K. McKinley, and Betty H. C. Cheng. Transparent shaping of existing software to support pervasive and autonomic computing. SICSOFT Softw. Eng. Notes, 30(4):1—7, 2005. Douglas C. Schmidt. l\»‘liddleware for real—time and embedded systems. Commun. A CM, 45(6):43»~48, 2002. 242 [7 5] [79] [s0] [81] [8‘21 Mary Shaw. Beyond objects: a software design paradigm based on process control. SICSOFT Softw. Eng. Notes, 20(1):27—38, 1995. Reid Simmons, Long-Ji Lin, and Christopher Fedor. Autonomous task control for mobile robots. In Proceedings of the 5th IEEE International Symposium on Intelligent Control, September 1990. Brian Tierney, Brian Crowley, Dan Gunter, Mason Holding, Jason Lee, and Mary Thompson. A monitoring sensor management system for grid environments. In HPDC, pages 97—104, 2000. Antoine Trad and Damir Kalpic. Proactive Monitoring and Maintenance of Intelligent Control Systems: A Design Pattern for Autonomous Systems. In 26th International Conference on Information Technology Interfaces I TI2004, pages 637—642, 2004. Giuseppe Valetto and Gail Kaiser. A case study in software adaptation. In WOSS ’02: Proceedings of the first workshop on Self-healing systems, pages 73—78, New York, NY, USA, 2002. ACM. \K'illiam E. Walsh, Gerald Tesauro, Jeffrey O. Kephart, and Rajarshi Das. Utility functions in autonomic systems. In ICAC ’04: Proceedings of the First Inter- national Conference on Autonomic Computing, pages 70—77, Washington, DC, USA, 2004. IEEE Computer Society. Danny Weyns, Robrecht Haesevoets, Bart Van Eylen, Alexander Helleboogh, Tom Holvoet, and VVouter Joosen. Endogenous versus exogenous self- management. In SEAMS ’08: Proceedings of the 2008 international workshop on Software engineering for adaptive and self-managing systems, pages 41—48, New York, NY, USA, 2008. ACM. Z. Yang, B. H. C. Cheng, R. E. K. Stirewalt, J. Sowell, S. M. Sadjadi, and P. K. McKinley. An aspect-oriented approach to dynamic adaptation. In WOSS ’02: Proceedings of the first workshop on Self-healing systems, pages 85—92, New York, NY, USA, 2002. ACM. Andreas Zeidler and Ludger F iege. l\-'lobility support with rebeca. icdcsw, 00:354, 2003. Ji Zhang and Betty H. C. Cheng. Specifying adaptation semantics. In WADS ’05: Proceedings of the 2005 workshop on Architecting dependable systems, pages 1 7, New York, NY, USA, 2005. ACM. .li Zhang and Betty H. C. Cheng. Model-based development of dynamically adaptive software. In I CSE ’06: Proceedings of the 28th international conference on Software engincering, pages 371—380, New York, NY, USA, 2006. ACM. 243 [86] Ji Zhang. Betty H.C. Cheng. and Heather J. Goldsby. Amoeba—rt: Run-time verification of adaptive software. In Proceedings of the International Workshop on Models @run.time as part of the ACM/IEEE 10th International Conference on Model Driven Engineering Languages and Systems I M ODELS 2007), Nashville, TN. USA, October 2007. 244