ࡱ; v  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuwxyz{|}~R F,CompObj\WordDocument2iObjectPool],],  FMicrosoft Word 6.0 DocumentNB6WWord.Document.6;  Oh+'0, 2 > JV^ fr DMHD:Applications:Microsoft Office:Microsoft Word 6:Templates:NormalALP/JL ACTD BAA 97-32 Ken Anderson Ken Anderson'@`k,@v@`ܥhO e2imXX_____4dadadadadaxa.ada/hj(b:cPcPcPc|cSe\+gh h h h h h h&hXhA/h_gPc,|cgg/hg__Pc(bgggg_Pc_PchN_`N____ghg,gSELF-ADAPTIVE SOFTWARE SOL BAA 98-12 PROPOSAL COVER SHEET Organization/CompanyBBN Technologies Proposal Title and Identification Number:Self-Adaptive Dynamic Design P98-STD-367 Technical AreaContractorSub-Contractor IdentificationTopic Area 1: Evaluation of Software Functionality and Performance at Runtime BBN Technologies, A Division of BBN Corp.Northeastern UniversityPrincipal Investigator:Dr. KennethDr. Karl Last Name:AndersonLieberherrPI Address:10 Moulton Street Cambridge, MA 02138360 Huntington Avenue 423 Lake Hall Boston, MA 02115Phone Number:(617) 873-3160(617) 373-2077Fax Number:(617) 873-2794( 617)373-4595PI E-mail: kanderson@BBN.comlieber@ccs.neu.eduAdministrative Contact:MarkJerryLast Name: DanieliMurphyAdmin. Address:10 Moulton Street Cambridge, MA 02138360 Huntington Avenue 423 Lake Hall Boston, MA 02115Phone Number: (617) 873-2010(617) 373-4588Fax Number: (617) 873-3797(617) 373-4595Admin. E-mail: mdanieli@BBN.commurphg@neu.eduContractors type of business:LARGE BUSINESS OTHER EDUCATIONAL Proposal Duration:Three (3) yearsTotal Cost:$1,511,276Total Base:$999,866Total Option: $511,410CY1: $504,277CY1: CY2: $495,589CY2: CY3:CY3: $511,410 CY=Contract Year Table of Contents toc \o "1-3" A. Innovative claims pageref _Toc410634939 \h 1 B. Technical Rationale pageref _Toc410634940 \h 2 C. Deliverables pageref _Toc410634948 \h 18 D. Statement of work pageref _Toc410634949 \h 19 E. Schedule of milestones pageref _Toc410634950 \h 21 F. Technology transfer pageref _Toc410634951 \h 22 H. List of key personnel pageref _Toc410634955 \h 26 I. Description of facilities pageref _Toc410634956 \h 30 J. Cost by task pageref _Toc410634957 \h 31 Innovative claims Problem: Traditionally, software design decisions are committed to at compile time. Unfortunately, inappropriate decisions eventually reveal themselves as performance problems. Thus as applications become larger and distributed, design decisions should be made as late as possible. We propose an approach called "self-adaptive dynamic redesign that allows an application to become more responsive by redesigning its components at runtime. This is accomplished by combining runtime meta-data provided by the program about its measured performance, with design time meta-data provided by the programmer about its structure. Experience: BBN Technologies has substantial experience in adapting large-scale systems to extreme environments. For military logistic planning systems, we have applied adaptive techniques to make sub-systems smaller and run faster, based on techniques such as structure sharing and remote message reduction. For the DARPA Quorum program, we have developed a Quality Object (QuO) framework for creating adaptive distributed systems. For both of these systems, we currently use ad-hoc mechanisms to achieve runtime adaptation. We plan to formalize these adaptive mechanisms and integrate them into existing DOD sponsored development environments. Solution: We propose using the emerging technology of Aspect-Oriented Programming (AOP) as a theme for organizing self-adaptive systems. AOP breaks out aspects of a system which traditional programming styles merge together and spread throughout the code. AOP allows changing one of these aspects and "weaving" it back into the code. These aspects organize runtime meta-data that describes the structure of the system and its environment. Implementation: This project will extend two existing adaptive programming environments to include dynamic redesign techniques. Demeter/Java (Northeastern University) is an AOP programming environment that allows programs to be easily changed at design time. Demeter/Java will be enhanced to include new aspects for dynamic redesign. These aspects and the program-structure can be encoded into the runtime code to enable the choice of alternative self-adaptive mechanisms. The QuO Runtime (BBN Technologies) supports adaptation in distributed object-based systems, such as CORBA. QuO will be extended to automatically reconfigure resources between remote method invocations using dynamic redesign. These environments will be tested and refined in the context of large distributed systems. Distributed systems require adaptive mechanisms because they operate over a wide range of variable environments that are difficult to anticipate at design time. Thus, we expect tremendous gains when dynamic redesign techniques are applied to them. Team: Our team combines leading researchers in Aspect-Oriented Programming with practical experience in developing and fielding large distributed systems. Karl Lieberherr's (Northeastern) Adaptive Programming (AP) methodology is a precursor to Aspect-Oriented Programming by introducing object-structure as an aspect. BBN Technologies has several large military-relevant systems that can be used to test this technology. Specifically, Analysis of Mobility Platform (AMP), and OpenMap will be used as a stable test applications and subsystems. The BBN Technologies and Northeastern team facilitates technology transfer by allowing AOP technology to be tested against real DOD sponsored projects. Technical Rationale B.1 Introduction:  Software can become more responsive as it runs by adapting the structure, behavior and remote messages of its objects to better match its needs. This can be done by self-aware software that uses knowledge of its runtime performance, and its own design to redesign its components to improve its performance under its current operating conditions. Self-Adaptive dynamic redesign is the integration of runtime redesignand design for adaptability. In "runtime redesign" we study the mechanisms used to redesign software at runtime. Effective use of such mechanisms requires knowledge of the design of the application. In "design for adaptability" we study how such design knowledge can be made accessible to the program at runtime as part of the redesign process. We believe that Aspect-Oriented Programming (AOP) is crucial to this integration. Programs are written in terms of components. For example, in an object-oriented language, the components are classes, instances and methods. Traditionally, after a program is implemented, its design decisions are fixed, and thus its performance characteristics are fixed. Fixing a performance problem requires modifying the program. Unfortunately, performance issues often crosscut component boundaries. Thus substantial modification to the program may be required to improve its performance. The resulting program becomes a "tangle of concerns" [AOP]. Using AOP, the performance aspects of a program can be separated from its basic functionality. Each aspect is described in its own simple "aspect language". A complete program is constructed by "weaving" the aspects together. The following figure shows the difference in programming style.  Figure 1: Aspect Oriented Programming separates aspects that spread throughout the code. The separated aspects provide a meta-level description of the program that can be used at runtime to redesign components of the application. This redesign parallels the relatively local redesign of components done by programmers to improve performance of the application. Thus AOP captures an ongoing design dialog between the programmer and the program about meta-level features that effect its performance. We base our proposed research on two DARPA funded projects that can provide the basis of support for runtime redesign and design for adaptability - Aspect-Oriented Programming, and Quality Objects, (QuO). AOP provides a framework for dynamic redesign. QuO provides a framework for runtime adaptive distributed systems. This framework includes design time code generation, and runtime monitoring of performance and selection of alternative implementations. Both AOP and QuO provide an excellent foundation for exploring dynamic redesign. The scope of the base project is proposed to be two years long with two demonstrations. Each year we will experiment with several Self-Adaptive mechanisms and select one or two of these mechanisms to be automated. The optional third year has a third demonstration on a DARPA-supplied operational network. The basic task cycle for the option year is the same, but the mechanisms will be refined to a level that will allow the tools to be used by other researchers within DARPA ISO exercises. The rest of the "Technical Rationale" describes the Dynamic Redesign process. Section B.2 introduces the main issues in software redesign and how it can be made self-adaptive. Section B.3 and B.4 the current state of AOP and QuO that will provide the basic metadata needed for dynamic redesign. Section B.5 describes the runtime redesign mechanisms we will investigate. The issues of dynamic redesign are motivated using a simplified example based on our experience with fielded logistics systems. Section B.6 describes how runtime redesign capabilities might be retrofitted into an existing application. B.2 Design Process: The following subsections describe the issues underlying software redesign. We summarize several redesign techniques routinely used by programmers to improve performance and outline how they can be automated. This leads to a more generic style of programming where the programmer and the program cooperate. When developing a software application, a programmer makes hundreds or thousands of design decisions, such as: What fields should this class have? What container class should be used here? How should this distributed object be accessed? While high level architectural decisions are crucial, these relatively small decisions can have profound effect on the performance and capabilities of the resulting application especially when it is stressed to the limits of its design envelope. For example, scaling the amount of data the application must handle by an order of magnitude may require a redesign of the underlying class hierarchy. Thus traditionally, these decisions are important enough to be left to the programmer to make. The programmer makes each decision based on information available to him, such as a design specification, or prototype. Unfortunately, these decisions cannot be completely verified until the application is fielded. Then, an inappropriate decision becomes a performance problem. Software design is even more difficult today because an application that works fine on an individual computer may need extensive modification to become a distributed or mobile application. Thus, current software design practice is brittle and costly. The intense time-to-market pressure of the World Wide Web makes such redesign even more costly.  Redesign: BBN Technologies has delivered military transportation and logistics systems since 1990 (Desert Storm). As these systems have matured, in addition to adding new capabilities, we have repeatedly modified these systems to better match performance requirements. This perpetual redesign can be thought of as a meta-level outside loop to the running application: 1. Run the application. 2. Measure its performance. 3. Choose one or more components to redesign. 4. Redesign those components 5. Modify the application to accommodate the redesign. 6. Verify that the modification improves performance. 7. Repeat. We believe that this performance adaptation loop can be automated by making the application self-aware. The self-awareness required includes: Resource consumption - How much memory, time and bandwidth is consumed during each phase of the application, such as each command execution? Redesign strategies - What is important to optimize? Which components of the application are critical to its performance? What changes to these components are likely to improve performance? Application metaknowledge - How can a redesigned component be integrated back into the application? Self-evaluation - How is the self-adaptation loop going? Should I work harder? Can I rest for a while? Should I ask for help? Knowledge of the application domain is not essential. However, guidance from the programmer and user can help the self-aware application focus on the critical issues. This guidance is provided at design time using the Aspect-Oriented Programming (AOP) approach of Demeter/Java and QuO. Adaptive Mechanisms: We propose to develop suitable aspect description languages, which allow the programmer to express, at a high level of abstraction, how building blocks should be exchanged automatically based on runtime information. We propose to investigate self-adaptive performance improvement in at least the following three broad areas: Adaptive remote messaging - Adapting message patterns between remote objects. Adaptive object storage - Optimizing space and time requirements for accessing local object state. Adaptive collections - Optimizing space and time requirements for collections of objects. These areas cover many of the implementation level optimizations made by programmers. Other adaptive strategies will also be investigated. The ultimate self-adaptive application: We believe, software required to deliver distributed self-adaptive applications will be one of the most important consumers of self-adaptive technology. Thus, we plan to use dynamic redesign in our development, thus eating our own silver-bullet. For example, in one application, 1.5 MB of storage was required to keep meta information on the fields of the application. Applying the structure sharing techniques described below provides a one third saving in storage (0.5 MB). Also, the caching techniques used in adaptive remote messaging will be a heavy user of adaptive collections. Impact on programming style: While we will concentrate on self-adaptive runtime redesign techniques in the proposed research, Dynamic Redesign leads to a new style of programming. Programs are described in terms of interfaces rather than classes and performance aspects rather than exact implementations. The program rather than the programmer now control the implementation details. Implementation suggestions become aspect-oriented hints provided with the code. Overall, the program becomes more generic and less committed to particular implementation details. Aspect-oriented hints become a medium of dialog between the programmer and the application. The programmer provides hints that the application uses in self-adaptation. The application constructs hints that summarize its redesign decisions. These hints can also be used by the programmer and the application the next time it runs, or shared among other applications. Conflicting hints can be identified and corrected. Ineffective hints can be improved. B.3 Aspect-Oriented Programming and Demeter/Java: Even with present technologies, software is complex, thus hard to write, maintain, and evolve, as needs change. Much of this complexity comes from the tangling that the software must have to provide for features that involve many different components spread throughout the system. Even with object-oriented technology, this tangling means that the application will be harder to write and maintain. One response to this problem is Aspect-Oriented Programming (AOP). AOP is an emerging programming technique that distinguishes between 'components' (which can be cleanly encapsulated in the functional modules of the language, such as objects) and 'aspects' (which cannot be so cleanly encapsulated, but which cut across, or affect, many different parts of the overall program). Each aspect is described separately thus allowing developers to work explicitly with the aspects of the solution. AOP is a term coined and developed at Xerox PARC [AOP]. In this approach, the aspects are described clearly and succinctly, and with minimal redundancy both within a given description and among different descriptions. Changes to the aspect are limited to the aspect description itself rather than spread throughout the program, and changes to one aspect have limited impact on other aspects and components. Thus, this approach increases robustness of the resulting system and simplifies system maintenance and evolution. One special case of aspect-oriented programming is 'adaptive programming', in which one of the aspects is expressible in terms of graphs and the other aspects or components follow 'strategies' to control and interpret references to these graphs. We have developed a system to support AOP, Demeter. Its latest incarnation, Demeter/Java, supports four basic aspects (Structure, Behavior, Object Description, and Synchronization). With Demeter, programs can adapt easily to interesting changes in the object structure. This capability allows simpler and more understandable programs and easier (and even partially automated) evolution. Demeter/Java already includes a generic weaver, which is used to weave behavior, structure and synchronization code together. Demeter/Java is already used in commercial projects, for examples at GTE Laboratories; refer to [GTE-Labs]. For other commercial projects see: [Success] and for many academic projects, see: [Overview].  B.4 QuO-Quality Objects: BBN Technologies has developed Quality Objects (QuO), a framework for developing distributed object applications which adapt to Quality of Service (QoS) [ZBS]. QuO provides an environment in which a programmer can specify possible QoS regions, the system elements that need to be monitored and controlled to measure and provide QoS, and behavior for adapting to changes in QoS. In this way, QuO opens up distributed object implementations [BBB], providing control of both the functional aspects of a program and its implementation strategies, which are often hidden behind CORBA IDL interfaces. QuO also supports aspect-oriented programming [AOP], in which a program is divided into aspects of concern, each of which are programmed separately in a suitable language and then woven together into a single application. QuO provides a suite of description languages for describing aspects of the QuO application and code generators that weave them together. While QuO has architectural support for many different kinds of adaptation, the actual mechanism for adaptation is left to the programmer. QuO has the necessary components to implement runtime redesign mechanisms. Specifically, this proposal will concentrate on negotiation time reconfiguration of resources. Between remote method calls, resource can be reconfigured in anticipation of future call patterns or changes in available resources. The QuO Runtime keeps the clients interface to a remote object the same, but can completely redo the plumbing for the connection between the client and object. The proposed dynamic redesign techniques will be used to automate this reconfiguration for the programmer. Execution Model of a QuO Application: In a traditional Common Object Request Broker Architecture (CORBA) application, a client makes a method call on a remote object through its functional interface. The call is processed by an ORB on the clients host, delivered to an ORB on the objects host, and processed by the remote object. The client sees it strictly as a functional method call. As indicated in Figure 2, a QuO application adds additional steps to this process.  Figure 2: QuO has architectural components for handling adaptation to QoS at Runtime. The QuO application not only consists of the client program, ORB, and object, it also has the following components provided by the QoS developer: A local delegate of the remote object. The delegate provides a functional interface identical to the remote object, but can trigger contract evaluation upon each method call and return. The QoS developer can provide alternative behaviors and a dispatch statement that chooses among the alternatives based upon the current state of the contract. A QoS contract between the client and object. This specifies the level of service desired by the client, the level of service the object expects to provide, operating regions indicating possible measured QoS, and actions to take when the level of QoS changes. System condition objects interface between the contract and resources, mechanisms, objects, and ORBs in the system. These are used to measure and control QoS. Figure 3 illustrates the steps that can occur during a remote method call in a QuO application. When a client calls a remote method, the call is passed to the objects local delegate instead. This is transparent to the client, since the remote object and the delegate have the same interface. The delegate can trigger contract evaluation, which grabs the current value of all system conditions measuring aspects of the systems state. The contract consists of a set of nested regions, which describe the relevant possible states of QoS in the system. Each of these regions is defined by a predicate on the values of system condition objects. The contract evaluates the predicates to determine which regions are active (i.e., their predicates are true) and passes the list to the delegate.  Figure 3: A QuO remote method call changes its behavior based on the current QoS region. The delegate chooses how to process the method call based upon the current operating regions. For example, the delegate might choose between alternate methods, might block or buffer when QoS has degraded, or might simply pass the call through to the remote object. The delegate performs similar processing upon a method return, i.e., it evaluates the contract to obtain the current QoS regions and selects a behavior based upon the current regions. Contract evaluation can also be triggered by changes in system condition objects that are observed by the contract. Other system condition objects, especially whose values change frequently, are non-observed and do not trigger contract evaluation. Regardless of how contract evaluation is triggered (by a method call/return or change in a system condition), a transition from one active region to another can trigger transition behavior, which consists of client callbacks or method calls on system condition objects. QuO Framework Support for Building Adaptive Applications: As indicated in Figure 2, the development of QuO applications requires an additional role over that necessary to build a distributed application: Application developers who develop functional code for the clients and distributed objects; QoS developers who develop QuO contracts, system condition objects, callback mechanisms, and object delegate behavior; and Mechanism developers who develop system components, ORB wrappers, mechanisms, and libraries providing access to or control of system- or ORB-level capabilities.  Figure 4. Quality Description Languages (QDL). To support the added role of QoS developer, the QuO framework consists of the following components: A suite of Quality Description Languages (QDL) for describing contracts, system condition objects, and the adaptive behavior of objects and delegates The QuO kernel, which coordinates evaluation of contracts and monitoring of system condition objects Code generators that weave together QDL descriptions, the QuO kernel code, and client code to produce a single application program. QDL currently consists of the following aspect languages (Figure 4): Contract Description Language (CDL), a Structure Description Language (SDL), and a Resource Description Language (RDL). CDL is used to describe the QoS contract between a client and an object, including the QoS that the client desires from the object; the QoS that the object expects to provide; regions of possible levels of QoS; system conditions that need to be monitored; and behavior to invoke when client desires, object expectations, or actual QoS conditions change. SDL describes the internal structure of objects implementations, including the amount and types of resources they require, and the adaptive behavior of object delegates. We currently have an object delegate generator that generates client-side and server-side object delegate code from SDL, CDL, and IDL code. RDL describes the resources available in the system and their status. SDL and RDL are currently under development. This project will integrate these QDL languages into the Dynamic Redesign framework. New aspect languages will be based on the new aspects that are developed are part of this project, such as descriptions of resource usage and alternative implementations. B.5 Runtime Redesign: This section describes several optimization techniques, which we have used on fielded logistics systems and outlines how each can be automated by a self-adaptive program. We use an example application based on BBNTs Analysis Mobility Platform (AMP) logistics software as a running theme. It demonstrates many issues that real applications must deal with every day. We describe a simplified military transportation application using Java interface classes, augmented with performance aspect hints indicated as comments, "/// like this". These hints represent knowledge that a programmer uses to redesign the application. This knowledge is available to the self-adaptive application. In a real application, several aspect mini languages would be used to express such knowledge. A Simple Transportation Application: A military deployment plan is described by a data structure called a "deployment plan". We will only consider six classes of objects to represent this data structure and related objects: DeploymentPlan, Requirement, GeoLocation, GeoDB, Record and Map. A DeploymentPlan contains a collection of Requirements, and a collection of GeoLocations. It is read from a stream of Records. GeoLocations can be looked up in a GeoDB database by their four-character code, can be displayed on a Map, and can be used in distance calculations. For each military unit in the DeployementPlan, a Requirement describes certain characteristics of the unit, such as its id, what service it belongs to, WHEN it needs to move, WHERE it moves, and WHAT cargo moves with it. (Imagine planning a vacation for your extended family.) A GeoLocation, represents a geographic location. A Requirement contains up to five GeoLocations. We assume there is a database object, of class GeoDB, that returns a GeoLocation given a four character code, the geolocCode. The Java interfaces to these objects might look like: //Example Java Logistics interface with performance aspects Interface DeploymentPlan { void load(Enumeration records); Requirement readRecord(Record r); void addRequirement(Requirement m); void addLocation(GeoLocation loc); // Compute table of distances between locations void computeDistances(); // Distance between 2 locations. float distance (GeoLocation L1, GeoLocation L2); display(Map map); // Display locations on map. } interface GeoLocation { String code(); /// readonly. float latitude(); /// readonly. float longitude(); /// readonly. String name(); /// readonly. // 17 attributes total... // Display location on map. void display(Map map); } interface Requirement { String reqid(); // Requirement ID. GeoLocation Origin(); GeoLocation Destination(); Date earliestDepartureDate(); Date latestArrivalDate(); // 40 attributes total ... } interface GeoDB { GeoLocation lookup(String code); /// memoizable. } Suppose our application has three phases, corresponding to three methods of a TransportationPlan. 1. load() - load Requirements from a file of Records. 2. computeDistances() - Compute the table of distances. 3. display() - Display locations on a map. A small transportation plan may have 10,000 requirements, while a large one can have over 150,000. While there are over 50,000 GeoLocations in the GeoDB, a transportation plan typically references only about 500. To be concrete, we will run different versions of our application with a transportation plan with 10,000 requirements and 500 locations. Suppose the average method invocation time is ten microseconds. This is quite generous since single instruction times are currently below 5.0 nanoseconds. Also, suppose a remote method invocation takes forty milliseconds, 4,000 times slower. The following exhibit shows the call graph of our application. The base code captures the algorithm with its sub-systems calls, but does not give any indication of the call frequency. Hints are needed to capture the call frequency, which may depend on the data set, hence may not be known until runtime. // Call graph with message counts. load { /// TotalMessages ~= 120,000 for each record { /// N-requirements ~= 10,000 readRecord for each location { /// N-locations ~= 5 gdb.lookup addLocation addRequirement } computeDistances { /// TotalMessages ~= 50,000*5 ~= 250,000 for each location pair /// Iterations ~= 500*500/5 ~= 50,000 distance { 2 * latitude, 2 * longitude } } display { /// TotalMessages ~= 500* 4 ~= 2,000 for each location { /// Iterations ~= 500 code, latitude, longitude, name. } } Adaptive remote messaging: Objects can now be distributed between multiple processes using various methodologies. For example, CORBA and Java Remote Method Invocation (JRMI) provide facilities that allow a program to reference a remote object with the same syntax as a local one. ObjectSpace's Voyager 2.0 will allow an object to become distributed automatically. Unfortunately, a remote method invocation is orders of magnitude slower, 4,000 times, say. Thus, a remote method invocation can easily be distinguished from a local one based on its performance. Object granularity is a problem faced by every distributed system designer. The application must be redesigned to alter the communication pattern to remote objects. Essentially, fine-grained communication must become coarse grained. Reducing the number of remote messages can do this, as well as increasing the amount of information passed per message. This can be done by: Memoizing - ask only once if the answer won't change. Prefetching - Ask several useful questions at once. Batching - Ask the same question about many objects. Each of these requires modification to the application: Memoizing - Requires caching results in the client. Prefetching - Requires smart proxies wrapping remote objects in client. Batching - Requires extending the server's interface. Client side of remote objects becomes lazy. The following exhibit shows the performance impact of several redesigns. Performance of remote messaging strategiesWhatTimeRemote MessagesRelative Time %1. Single process3.72 seconds00.12. Distributed GeoDB1.13 hours102,000100.03. Memoize lookup0.58 hours52,50051.04. Prefetch lat/lon40 seconds1,0001.05. Batching lat/lon26 seconds5030.6 1. Single process application. The first version of the application runs inside a single process. Under these conditions, our application requires about 120,000 + 250,000 + 2,000 = 372,000 method invocations and which take a total of 3.72 seconds to execute. 2. Distributed GeoDB. The application requires (50,000 + 50,000 + 2,000 = 102,000 remote method invocations requiring 4,080 seconds or 1.13 hours. Thus by distributing 5% ((1 + 500)/(1 + 500 + 10,000)) of the objects, the applications is over 1,000 (4,080/3.72) times slower, because one-third of the messages become remote. 3. Memoize lookup(). There is a meta-level hint on lookup() that it is memoizable. This means it returns the same value given the same input. This means the result of a lookup() can be cached on the client side, reducing the number of remote method invocations. With this improvement, there are (500 + 50,000 + 2,000) remote method invocations, for a total of 2,100 seconds, or 0.58 hours. Almost a factor of two better performance. 4. Prefetch latitude and longitude. In this version, latitude and longitude are prefetched during the lookup() of the GeoLocation. This leads to an execution time requiring 500 + 500 remote methods or 40 seconds. 5. Batching lat/lon. During load() only the identity of the GeoLocation is used, while during computeDistances() the latitude and longitude are also required. By deferring the actual lookup() until the first latitude is required, we can ask for all the GeoLocations and their latitudes and longitudes at once, in one large query. Thus single batched query returns 500*3 = 1,500 pieces of information. We simply assume this takes one-tenth the time of 1,500 remote messages, or 6 seconds. On the client side, this requires a lazy version of the GeoLocation object. The interface to the GeoDB must also be extended to allow the batched query. This requires changes to both the client and server. One might continue further, reducing the communication between client and server to a single message. However, messages with long responses increase the latency of the application. Also, greedily minimizing the number of messages could lead to such performance anomalies as retrieving an entire 300 page book simply to check it's price. Demeter/Js RIDL language addresses this issue. Adaptive object storage: Many object-oriented languages, such as Java, are class based. A class describes the fields (attributes) and behavior (methods) of each instance of that class. Fields are inherited from each superclass. This design choice trades space for time. Each field can be accessed in constant time, but also requires constant space (often one word) per object. When storage is important several strageties can be used to compress the object: Merging slots. For example, several boolean fields can be merged into a single "flag" field. Class specialization. When a field can contain only a few constant values, such as, "hot" or "cold", a subclass for each value could be defined. Fields that have constant value can be dropped from the class definition altogether. Structure Sharing. Fields that have common values over a group of objects, can split off into a component object shared by many objects. This has proven to be very useful in Palmtop computers, such as the Apple Newton, where memory is scarce. Defaulting. When the value of a field is mostly constant, values of objects that don't have the default value can be kept in a small exception table. Such object storage decisions can be made automatically by: Monitoring the amount of space used by the objects in each class. Classes that use the most space are candidates for restructuring. The entropy (information content) of each field and sets of fields can be used to identify which shape strategies to use. For example in a real logistics application, a field information content analysis of 40-field Requirement objects showed that half the storage can be recovered by splitting the object into two parts: a 25-field object that is part of a small (1,000) shared pool of objects; and a 15-field object. As shown in the following table, half the storage was recovered. Compression of movement requirement storageWhat # FieldsMBytes Relative %Original 401.72100Structure sharing 150.8348 The information content of the slots can reveal natural structures that make sense in the underlying domain of the application, but that are not captured in the class hierarchy. For example, in the above analysis of the Requirement class, the five GeoLocation (and related) fields make up the shared objects. In military transportation terminology these shared components are referred to as "Transportation channels", or "Lines of communication". Hence, structure sharing found a natural optimization used by human planners, but not written into the code. Adaptive collections: A typical class library contains several collection classes. For example ObjectSpace's JGL library provides 14 collection classes and the GNU C++ library has 11 set classes. Each class provides different space/time tradeoffs. For example, while a hash table can provide O(1) lookup of an object based on the hashed attribute, an implementation may not be optimal for a table containing less than 25 elements, say, where a linear search would be faster. Also, the average space per element may be larger than that of another collection class. In one 250,000 line application we studied, there were over 450 static hash table construction sites. Statistics from a snapshot from the running application showed that of the 1781 existing hash tables, 50 percent used a suboptimum implementation chosen by the programmer.  We propose that the choice of the appropriate collection implementation should be determined by the application. To make the choice, the application tags each collection by its construction site. For each construction site it collects statistics on the access pattern of the underlying collections. From these statistics, an optimum implementation class can be chosen. B.6 Accommodating Adaptation at Runtime: The previous section describes how design decisions, traditionally made by a programmer can be made automatically. This section describes how these decisions can be implemented automatically. In the Adaptive Object Storage example, above, the class hierarchy was redesigned to be more space efficient. To accommodate this change, the following changes must be made: A new class implementing the Requirement interface must be defined. If the old implementation has subclasses, the new implementations will have a new set of similar subclasses. Methods for the new classes must be written using the old methods as a template. Access to a merged or shared field is changed appropriately. Object construction sites must be informed to construct objects of the new classes. The transformations made by the self-adaptive software will be similar, but sometimes simpler than those made by a programmer. To accommodate these changes, the self-adaptive application must be self-aware. It must be able to reason about: The class hierarchy. The interface to each class. Some details of the methods that implement each interface. Existing classes must be changed to the new structure. The self-adaptive application makes simple design changes as it runs. To do this, the application monitors itself, collecting performance statistics and periodically alters its underlying design decisions dynamically. The cost of this monitoring can be minimized by combining it with other activities, such as: Object construct or destruction An operation on a collection of objects Sending or receiving a message to a remote object. Overall performance is improved since design decisions are made as late as possible. This is particularly valuable for unusual situations, or long-lived applications. A short-lived application can cache its statistics to be used the next time it runs, or the next time it is compiled. Alternatively, statistics can be combined from an ensemble of users. Since the programmer is not involved, certain optimizations can be performed that a programmer would not be able to make safely. For example, protective layers of abstraction can be eliminated. Runtime Support: Self-adaptation can be added to an existing program if the implementation language is dynamic and introspective enough. Such languages include Smalltalk, Common Lisp, and Java. For example, they provide information about the structure of the class hierarchy, and the fields and methods of each class. Additional information can be acquired by reading source code, byte codes, or binaries. Full understanding of the source code is not required. Lets take a Java application as an example. Java provides introspection facilities that allow the structure of the class hierarchy and methods to be identified. The byte-codes of the compiled Java class files can be used to infer additional information, such as object construction sites, and field accesses. Given this information, a new self-adaptive version of the application is constructed where: Each implementation class is split into an interface, and a default implementation of the interface. Each default implementation is the original implementation augmented to help collect performance statistics used in self-adaptation. Each object construction site is replaced by an object factory that constructs an object that provides a particular interface. Meta-level information used during self-adaptation is provided. A self-adaptive program monitors its performance as it runs and adapts accordingly as described above. New Java classes can be defined and loaded on the fly and integrated into the application. The adaptive environment we plan to use, Demeter/Java and QuO, allow us more control over runtime introspection. The code generator can be modified to provide metadata that is not available from existing languages. Thus, we take advantage of existing language features and enhancing them, without creating a new programming language. C. Deliverables The proposed deliverables for this project include the following: Software: This project develops software, which allows applications to dynamically adapt to their environment at runtime. Dynamic Redesign techniques will be developed and added to existing adaptive environments. We will make two software releases as part of the base project, with a third release as part of the option year. Two software environments will be enhanced as part of this project. Demeter/Java will be enhanced by Northeastern University to include Runtime Redesign aspects. Quality Objects (QuO) will be enhanced by BBN Technologies to include Runtime Redesign algorithms at "negotiation-time." In addition, a runtime library will be co-developed by Northeastern University and BBN Technologies. Demonstrations: This project will demonstrate the benefit of Runtime Redesign on militarily relevant distributed applications (Logistics Planning). The demonstrations will show how Self-adaptive applications can be more responsive and use less critical resources over a wider range of environments than their non-adaptive versions. The first two demonstrations will be held at the BBN Technologies Cambridge facility and will use the QuO testbed to emulate a dynamic environment. Two demonstrations are part of the base project. One demonstration will be made as part of the third year option on a DARPA supplied operational network. Reports: Monthly Technical Reports, a Technology Transition Report, and a Final Project Report, will all be delivered as part of this project. Proprietary claims: No proprietary claims to the results, software, or hardware developed in the proposed project will be made which would in any way restrict government use or access to any of these results, software or hardware. We anticipate that we will make use of freely available redistributable software in the performance of the statement of work. Should any third party software be required in the performance of the statement of work, it will be delivered in accordance with DFARS 252.227.7013. D. Statement of work This project will develop prototype software to allow systems to self-adapt to their environment at runtime. The project will use Aspect-Oriented Programming (AOP) techniques as a theme for organizing meta-data about the program structure, usage patterns, resource consumption, alternative implementations, and performance requirements. Self-Adaptive mechanisms will use this meta-data to choose between alternative implementations at runtime. Existing design-time adaptive environments will be extended to generate code to make legacy systems more adaptive. The resulting systems will be more efficient and more responsive than their non-adaptive version.  Figure 5: Tasks Interaction Tasks: The work is divided into five tasks. The central focus is experimentation with Self-Adaptive mechanisms using AOP techniques in the context of large distributed applications. The experiments will feedback and refine the other basic tasks. Self-Adaptive mechanisms will be refined from design-time techniques done by humans to automated algorithms executed at runtime. Large logistics applications will be modified with Self-Adaptive techniques and measured to illustrate the improvement. AOP techniques will be enhanced as we define new aspects to describe runtime adaptive systems. Finally the process of creating self-adaptive system will be added to existing compile-time environments and runtime libraries. Scope: The base project is proposed to be two years long with two demonstrations. Each year we will experiment with several Self-Adaptive mechanisms and select one or two of these mechanisms to be automated. The optional third year has a third demonstration on a DARPA-supplied operational network. The basic task cycle for the option year is the same, but the mechanisms will be refined to a level that will allow the tools to be used by other researchers within DARPA ISO exercises. Base Project: Task 1: Aspect-Oriented Programming (AOP) R&D We will investigate under this task extensions to AOP to support runtime adaptive systems. We will define new aspect description languages that formalize the runtime meta-data which is needed by the self-adaptive mechanism. We will design aspect-weaver algorithms, which combine several independent aspects into a single program. Task 2: Self-Adaptive Mechanisms R&D We will develop under this task Self-Adaptive mechanisms that can be used at runtime to redesign a system's implementation without human aid. We will specifically refine and formalize structure sharing, adaptive collections, and method compression. We will also develop runtime representations for aspects. Task 3: Experiment with Self-Adaptive Systems We will experiment with applying AOP to formalize mechanisms in the context of distributed logistics applications. We will mockup runtime redesign algorithms and apply them to several logistics subsystems. We will work with AOP researchers, mechanism researchers and logistics experts to select the most promising algorithms for automation. Task 4: Automate Self-Adaptive Mechanisms We will extend existing Demeter Java to support new aspects and redesign algorithms for self-adaptive runtime systems. The resulting system will generate Java code, which can redesign its implementation at runtime. We will extend the QuO Development Environment to include support for runtime adaptability in distributed object systems. The main extension to QuO Runtime will concentrate on reconfiguring resources at "negotiation-time", the time between connecting to an object and invoking a method on the object. The resulting system will generate CORBA delegates and QuO system conditions, which automatically reconfigure resources without the programmer defining specific algorithms. We will create support libraries to implement common functions, such as measuring call patterns, available resources and resource costs. These libraries will be used by the code generators to raise the level of abstraction for the generated code. Task 5: Measure Improvement We will modify Logistic Planning subsystems using Self-Adaptive techniques and measure the improvement. Several subsystems should be tested, such as LogWeb, Open Map, and QuO Kernel. Part of this task will be identifying metrics for measuring the improvement. E. Schedule of milestones This project creates software, which automates Runtime Redesign techniques. The software will be developed over a one-year cycle resulting in a demonstration at 11 months and a software release at 12 months. The basic cycle has four phases. First, we will experiment with Runtime Redesign techniques by applying them by hand to logistic planning subsystems. Second, we will formalize the experimental results using AOP techniques. Third, we will automate the Runtime Redesign algorithms. Fourth, we will modify logistic planning subsystems using the new tools and measure the improvement. The base project will complete two passes through this cycle, thus resulting in two demonstrations and software releases. The optional third year will complete the cycle again, but will emphasize a robust demonstration in DARPA ISO exercise.  F. Technology transfer BBN Technologys transition approach for our Self-Adaptive Dynamic Design technology begins by capturing the application-independent technology via DARPA ITOs Quorum project. The next step is to capitalize on our application-specific results with further technology transfer in the specific application domain of the AdCon-21 program. The Quorum projects goal is to implement fundamental change in approaches to network computing. A key mechanism in achieving this goal is the design and implementation of architecture addressing adaptive approaches to QoS. Current work under the Quorum program specifically investigates mechanisms to facilitate the implementation and execution of adaptive software. The focus of QuO and other Quorum initiatives is the collection of runtime performance information from within a running distributed system and the use of that information to inform intelligent resource allocation and/or appropriate selection among alternate implementations. Although Quorums mechanisms to support adaptation do not limit the techniques used by adaptive applications, the usual assumption is that the various adaptive behaviors are custom-designed and handcrafted by the applications designers and implementors. The proposed research is an exceptional match for Quroum, because it focuses specifically on improving the available techniques for creating the adaptive software enabled by current Quorum research. By mating self-adaptive software with Quorums adaptation-support infrastructure, the level of dependence on custom-designed and developed distributed software solutions can be significantly reduced. In affect, self-adaptation technology serves as an engine for the automated creation of adaptive software. Quorum software will also be helpful in accomplishing the proposed self-adaptive software research. By leveraging from reuse of software capabilities provided in Quorums adaptation-support infrastructure, we will avoid the development of redundant performance-measurement and adaptation software. In addition, the timing is ideal for technology transition to Quorum. The Quorum project is on the verge of entering into an integration phase. Quorum integration is planned to run concurrently with and continue on beyond the completion of the proposed research. BBNT is a participant in current Quorum research. We will work with DARPA and the Quorum integration contractor to insert self-adaptive applications at appropriate phases in the Quorum integration cycle. The second phase of BBNTs transition plan will take advantage of our experimental results in applying self-adaptive techniques to application-specific problems. We propose to investigate transition paths that take advantage of BBNTs extensive experience in distributed software development and the Quorum projects developing relationship with the U.S. Navys AdCon-21 program. The Naval Surface Warefare Center, Dahlgren Division (NSWCDD), through itsAdCon-21 program, is addressing issues of integrated C4I and combat operations among various components of the Navys 21stcentury fleet. In order to meet the programs demanding requirements, AdCon-21 advanced software technology must include the capability to adjust to changing configurations during the planning, deployment, execution, and redeployment phases of integrated operations. In particular, the very nature of ship-board communications implies significant run-time variability in network performance, not only with different ship configurations, but also with the various phases of an operation. The rapidly changing environment of AdCon-21 makes it a strong candidate to benefit from the proposed research. For example, as an operation moves from a planning phase into the deployment phase, communication resources are likely to be more and more at a premium. Self-adaptive software, equipped with Quorum-based QoS-monitoring capabilities, can sense the degrading performance as communication links become more saturated. Adaptive techniques discussed in section B above, such as request batching, could automatically be invoked to move the system away from a mode that optimizes processing resources in a communications-rich environment towards a mode that optimizes communicating resources in a communications-limited environment. Comparison with other ongoing research Foundation: Our approach to self-adaptive software is founded on Metaobject programming, Open Implementation, Aspect-Oriented Programming [AOP], and Adaptive programming [Demeter]. Self-awareness in terms of meta-level knowledge of program structure is essential for self-adaptation. Open Implementation is the idea that the programmer should have disciplined access to an underlying implementation so he can influence its performance characteristics. We propose to extend this capability to the program itself. In Aspect-Oriented Programming (AOP), aspects of a system are described separately rather than merged together and spread throughout the code as in traditional programming. AOP programming allows changing one of these aspects and "weaving" it back into the code. We plan to use aspect languages to organize runtime meta-data for the structure of the system and its environment. We will also develop new aspects, including usage patterns, resource consumption, and resource status. Adaptive Programming (AP) is a compact and fluid style of programming. In traditional object oriented programming, such as Java, the class hierarchy and methods are defined together. Changing the class graph often requires changing the methods too. In AP, methods can be defined independently of certain details of the class graph, such methods are referred to as "structure-shy". A method is described in terms of a traversal strategy that can be used in a wide range of class hierarchies. This lack of commitment makes adaptation easier. In some sense, an AP programmer programs in terms of the entire class hierarchy at once, rather than one class at a time. While both AP and AOP make programming more easily adaptable, they are not self-adaptive. We will develop aspect languages that support self-adaptation for performance. Both the programmer and the program will use this language as a medium of dialog. Treaty of Orlando: The two main styles of object-oriented programming are class based, such as Smalltalk, Common Lisp, and Java, and prototype based, such as Glyphic Script, Self, NewtonScript, and Kevo [PBL 94]. While class based languages are prevalent in commercial single-user applications rich in CPU and memory resources, prototype based languages survive in nitches where dynamism and persimony are important. For example, NewtonScript thrives in a "palmtop" environment where only several megabytes of memory are available. Thus NewtonScript objects minimize their space requirements by maximizing their opportunity to share resources. However, the stragegy for sharing of resources between objects must be chosen by the programmer. In our approach, such design decisions can be made by the program based on the selective pressures of the environment it finds itself in. Dynamic Languages: Self, Cecil and Common Lisp are dynamic languages that emphasize performance through late binding time. By committing to implementation at the latest possible time, high performance can be achieved. We extend this one notch by committing to implementation based on the dynamic characteristics of the application. Adaptive remote messaging: Bogle and Liskov describe a technique for batching message across domains that is similar to our approach. [Phillip Bogle and Barbra Liskov, Reducing cross domain call overhead using batched futures, OOPSLA'94, p 341-354.] By monitoring message statistics, we believe we can make effective message merging decisions. These can be as simple as collecting the frequency of each message, or by modeling (compressing) the sequence of messages, using the Sequitur technique, for example. [Sequitur http://dna.Stanford.EDU/sequitur/jair/] Adaptive collections: SETL [SETL 81] is a high level language that lets algorithms be described with specifying the details of its implementation. However, declarations can be added by the programmer that lets the language choose high performance implementations. Bartory [Bartory 98] has an interactive web page where the user can design a container class optimized for his needs. The requirements of the container class are described in a layered fashion and can include performance requirements. Our approach extends this by providing the performance requirements directly from the application. Cdt [Vo 97] is a container class library that can be dynamically reconfigured by the user to better match runtime requirements. Lortz and Shin [LS 94] describe a container class library based on contracts. The programmer specifies a container not by a class name, but by a contract it must satisfy. The contract is passed to a factory object that constructs a container that will satisfy the contract. We plan to use this same approach for our self-adaptive containers. H. List of key personnel Ken Anderson, Ph.D., BBN Technologies (Principal Investigator) Dr. Anderson is a senior developer of object-oriented applications. He is interested in making software self-aware using metaobject, machine learning, and source transformation techniques. Dr. Anderson helped standardize CLOS (the Common Lisp Object System). He studies the performance of high level programming languages such as C++, Common Lisp, and Java. Since 1990, Dr. Anderson has been a principle developer of military transportation planning software. Such systems include AMP (Analysis of Mobility Platform) and DART (Dynamic Analysis and Replanning Tool), sponsored by DARPA and USTRANSCOM. Dr. Anderson was a principle developer of DESIGNET, a network design tool and Spyglass, a network packet trace analyzer. The SpyGlass tool takes packet traces and visualizes the flow of information at each layer of the protocol including CORBA IIOP. SpyGlass generates code at runtime from description languages that is integrated into the running system. For example, in SpyGlass one command changes the definition of a protocol, generate a new parser, analyze the packet trace, redisplay the results. These tools are used to support the Quality Objects (QuO) project. With ALCOA, Dr. Anderson has developed Prosaic, a knowledgeable assistant for analysis and interpretation of signals from an aluminum rolling mill, as part of ALCOA's Process Control Improvement Program. This system is capable of parsing waveforms to diagnose out of control signals, and learning diagnostic rules from examples of out of control data. Prosaic has been in daily use since 1989. Dr. Anderson was the PI for the SMART BIT I and II projects which investigated the use of AI, pattern recognition, and neural network techniques to improve the false alarm rate of Built-In-Test (BIT) in actual aircraft avionics. Dr. Anderson helped develop the prototype for RS/Explore, the statistical expert advisor component of BBNTs RS/1. Dr. Anderson has developed several methods using AI and Pattern Recognition techniques for automatic waveform description and understanding that have been used in diverse areas such as aluminum manufacturing, torpedo data analysis, and seismology. John A. Zinky, Ph.D., BBN Technologies (Senior Scientist) Dr. Zinky has worked at BBN Technologies since 1983 on a variety of projects concerned with performance analysis of distributed systems. Dr. Zinky is currently studying the interaction between distributed applications and computer networks. He is the architect of the Quality Object (QuO) framework, which handles Quality of Service (QoS) issues at the Common Object Request Broker Architecture (CORBA) level. QuO allows distributed applications to adapt to extreme runtime variation in its environment. He the principle investigator for the DARPA funded DIRM project, which adds communication resource allocation techniques to QuO. Dr. Zinky is a domain expert on knowledge-based tools for troubleshooting performance problems in computer networks, including the SpyGlass protocol analysis environment and the ANT network path-modeling environment. Dr. Zinky was also a performance analyst for the ARPANET and developed techniques that stabilized load sensitive routing. Previous to BBN Technologies he worked at Lawrence Livermore National Laboratory. Karl Lieberherr, Ph.D., Northeastern University (Professor) His research group developed key ideas of adaptive and aspect-oriented software and implemented them in the Demeter Tools for a variety of programming languages. The results of this research are disseminated by the book \cite{karl:demeter}, 7 Ph.D. theses and numerous papers. The papers, theses and the software with documentation are available on the WWW, see World-Wide Web addresses: Home page: http://www.ccs.neu.edu/home/lieber Demeter's home page: hyperlink http://www.ccs.neu.edu/research/demeter/ http://www.ccs.neu.edu/research/demeter/. Prior to his Demeter work, Karl Lieberherr developed in the 1980's the concept of P-optimal algorithms (a theme currently researched at Microsoft research) and he developed the hardware description language Zeus which influenced the design of VHDL. Ibrahim Matta, Ph.D., Northeastern University (Assistant Professor) Ibrahim Matta's research involves the design of traffic control mechanisms for integrated-services networks with emphasis on routing and its interaction with other control functions, and the development of computationally efficient evaluation methods integrating numerical, analytical and experimental techniques. He has published in many refereed journals and conference proceedings, including Computer Networks and ISDN Systems, Journal of Telecommunication Systems, IEEE Journal on Selected Areas in Communications, Journal of Internetworking: Research and Experience, ACM SIGCOMM Computer Communication Review, ACM SIGMETRICS/PERFORMANCE, IEEE INFOCOM, IEEE ICNP. Ibrahim Matta received the National Science Foundation Career Award in1997. He has developed software tools for evaluating best-effort and real-time network systems. The tools are publicly available and are currently being used for research and education at several sites. See http://www.ccs.neu.edu/home/matta/software.html. He serves as a reviewer for numerous conferences and journals, including IEEE INFOCOM, IEEE/ACM Transactions on Networking, Journal of High Speed Networks. He has served on the technical program committee of the IEEE ICNP conference. URL: hyperlink http://www.ccs.neu.edu/home/matta http://www.ccs.neu.edu/home/matta Proposed Level of Effort Project TitleSr. Analyst Name% on Project Year 1% on Project Year 2% on Project Year 3Self Adaptive Dynamic DesignKen Anderson50%50%50%John Zinky25%25%25% Level of Effort on Proposed Contracts Project TitleSr. Analyst Name% on Project Year 1% on Project Year 2% on Project Year 3Agent Based Systems (ABS)Ken Anderson100%100%100%SpyglassJohn Zinky20%20%20% Level of Effort on Current Contracts Project TitleSr. Analyst Name% on Project Year 1% on Project Year 2% on Project Year 3Analysis Of Mobility Platform (AMP)Ken Anderson10%10%10%Dynamic Integrated Resource Management (DIRM)John Zinky50% 1. Project Name - Analysis of Mobility Platform (AMP) 2. Name of Contracting Organization - Rome Laboratory 3. Contract No. - F30602-95-C-0146 4. Total Contract Value - $4,245,046 5. Description of Requirement - Working for USTRANSCOM, BBN Technologies has developed AMP, a transportation planning tool that provides unified access to planning and transportation information required to support deployment of both forces and equipment in Joint Operations. AMP provides what-if capabilities in the transportation feasibility realm and establishes a common interface and input/output shell for transportation analysis. AMP will be part of the Future Operation portion of the Global Transportation Network. AMP makes possible automated comparison of deployment plans with the actual execution of these plans, thereby identifying trouble spots early while both triggering and enabling replanning. AMPs capabilities cover all aspects of strategic transportation. AMP also has some high level capabilities to project sustainment materiel requirements in order to account for sustainment transportation requirements. AMP utilizes a variety of Management Science and Operations Research techniques to model the transportation flow of a TPFDD. The AMP system incorporates DPG data, including TPFDDs. AMP analyzes TPFDDs in detail. 1. Project Name - Dynamic Integrated Resource Management (DIRM) 2. Name of Contracting Organization - SPAWARE Systems Center 3. Contract No. - N66001-96-C-0315 4. Total Contract Value - $1,519,287 5. Description of Requirement - DIRM investigates the use of reservation protocol (RSVP) to provide assured network bandwidth for distributed application mamagement of limited network resources. Subcontractor Proposed Level of Effort Project TitleSr. Analyst Name% on Project Year 1% on Project Year 2% on Project Year 3Self-Adaptive Dynamic DesignKarl Lieberherr20%50%50%Ibrahim Matta25%10%10% Subcontractor Level of Effort on Proposed Contracts None Subcontractor Level of Effort on Current Contracts Project TitleSr. Analyst Name% on Project Year 1% on Project Year 2% on Project Year 3Evolution of Software through Adaptive ProgrammingKarl Lieberherr10%50%50%Integrated Dynamic control for Robust Quality-of Service RoutingIbrahim Matta20%20%20% I. Description of facilities BBN Technologies is the research and development arm of GTE Internetworking. In addition to its R&D capability, BBN Technologies (BBNT) engages in significant technology transfer and systems development activities. Our 1150-member staff works in multiple, complementary technologies that span the physical, computer, and information sciences. BBNT's proposed effort will be performed at our offices in Cambridge, MA. GTE Internetworking's Cambridge campus houses the headquarters of BBN Technologies, and includes substantial facilities suited for the Dynamic Redesign effort. These facilities include 270,000 square feet of office, laboratory, and storage space distributed over several buildings, interconnected by a high-speed private network. BBNT enjoys the exceptional network connectivity and electronic commerce capabilities that are expected from one of the world's leading Internet service providers. BBNT's technical staff have access to these extensive network facilities and corresponding hardware and software capabilities, such as electronic mail, secure network communications, and audio and video conferencing. BBNT is also certified to conduct classified research and development for the U.S. Government. Our Cambridge facility holds Top Secret level facility clearance. Our computational facilities include numerous Apple Macintosh and IBM-compatible personal computers, a wide variety of desktop and desk-side scientific workstations, and a selection of larger computers that function as shared-use compute and file servers. Most of these computers are connected to each other via our facility-wide Ethernet and to the rest of the world via our corporate Internet connections. Our systems are well supported by a variety of peripherals and software. Central file and compute servers from Sun, SGI, DEC, BBNT, and other vendors are available at BBNT for computing and storage needs not satisfied by desktop or deskside workstations. BBNT has extensive experience in data networking. BBNT is equipped to conduct wide-area distributed system integration and testing through access to the facilities of our offices in Arlington, VA; San Diego, CA; and Columbia, MD that support DoD research, development and technology transfer efforts. J. Cost by task Appendix A. Bibliography [BBB] Gregor Kiczales, Beyond the Black Box: Open Implementation, IEEE Software, January 1996. [AOP] Gregor Kiczales, John Irwin, John Lamping, Jean-Marc Loingtier, Cristina Videria Lopes, Chris Maeda, and Anurag Mendhekar, Aspect-Oriented Programming, ACM Computing Surveys, 28(4es), December 1996, http://www.acm.org/pubs/citations/journals/surveys/1996-28-4es/a154-kiczales/. [ZBS] John A. Zinky, David E. Bakken, and Richard E. Schantz, Architectural Support for Quality of Service for CORBA Objects, Theory and Practice of Object Systems, 3(1), 1997. [GTE-Labs] http://www.ccs.neu.edu/research/demeter/evaluation/gte-labs/ [Success] hyperlink http://www.ccs.neu.edu/research/demeter/evaluation/success.html http://www.ccs.neu.edu/research/demeter/evaluation/success.html [Overview] hyperlink http://www.ccs.neu.edu/research/demeter/course/f97/projects/overview.html http://www.ccs.neu.edu/research/demeter/course/f97/projects/overview.html [BL 94] Phillip Bogle and Barbra Liskov, Reducing cross domain call overhead using batched futures, OOPSLA'94, p 341-354.] [Batory 98] Web-Advertised Generators and Design Wizards, hyperlink FTP://ftp.cs.utexas.edu/pub/predator/web.ps FTP://ftp.cs.utexas.edu/pub/predator/web.ps [SETL 81] Edmond Schonberg, Jacob T. Schwartz, and Micha Sharir, An Automatic Technique for Selection of Data Representations in SETL Programs, acm Transactions on Programming Languages and Systems, v3(2), p126-143, April 1981. [LS 94] Victor B Lortz and Kang G. Shin, Combing Contracts and Exemplar-Based Programming for Class Hiding and Customization, OOPSLA 94, v29 (10), p453-467, October 1994. [VO 97] K.P.Vo, A Container Data Type Library, Software Practice and Experience, v27(10), p1177-1198. [PBL 94] Randall B. Smith, Mark Lentczner, Walter B. Smith, Antero Taivalsaari, and David Ungar, Protype-Based Languages: Object Lessons from Class-Free Programming, OOPSLA 94, v29 (10), p102-112, October 1994. BBNT Technologies P98-STD-367 Page page 31 NOTICE: USE AND DISCLOSURE OF DATA The data in this proposal shall not be disclosed outside the Government and shall not be duplicated, used, or disclosed in whole or part for any purpose other than to evaluate this proposal; provided that if a contract is awarded to this offeror as a result of or in connection with the submission of these data, the Government shall have the right to duplicate, use, or disclose the data to the extent provided in the contract. This restriction does not limit the Governments right to use information contained in the data if it is obtainable from another source without restriction. A crisis has occurred. A major logistic task is underway to move equipment and personnel to the scene. People are working around the clock both on the logistics task at hand and at reconfiguring the logistics system itself. Parts of the system were moved to the field to be close to the task and are now loosely connected back via unreliable satellite connections. Other parts of the system were moved to high-speed hardware in hopes of improving performance. How can a complex distributed logistics system absorb all this change in usage pattern and resources and still operate effectively? There is no time to redesign the system, but the system could be designed to be self-adaptive. The "write once run everywhere" motto of Java only works in the sense of functionality, but not in performance. Our central claim is a novel paradigm, Aspect-Oriented Programming (with Strategies), to attack the problem of self-adaptive systems. We will produce a significantly enhanced version of Demeter/Java, which allows one to write self-adaptive programs. We argue that software for self-adaptive distributed systems should be aware of the physical distribution in all levels, raising new issues in the design of self-adaptive programs, e.g., object location and migration, object duplication, communication interface, security, robustness against crashes, failures, etc. Container problems are ubiquitous and show up unexpectedly. For example, we have observed excessive sluggishness when Java compilers when compiling several hundred files or inner classes. Problems like these are symptomatic of a poor choice of container classes. ࡱ *t:@D$^&RyK _Toc410634939t:@D$^&RyK _Toc410634940t:@D$^&RyK _Toc410634948t:@D$^&RyK _Toc410634949t:@D$^&RyK _Toc410634950t:@D$^&RyK _Toc410634951t:@D$^&RyK _Toc410634955t:@D$^&RyK _Toc410634956t:@D$^&RyK _Toc410634957:x1%  S&WordMicrosoft Word&Word   2 @@$Use Word 6.0c or later to 2 @$view Macintosh picture. @ @ ''UUUU1@UUUUHHN|HaaNNNN''''????rrrr1H 0(-UUUUHHN|IaaNNN?9'''???rrr1}: 0(-UUUUHHN|JaaNNNN''''????rrrr1Q 0(-UUUUHHN|KaaNNNN''''????rrrr1Q 0(-UUUUHHN|L>>>>||||1C 0(-UUUUHHN|M>>>>||||1C 0(-UUUUHHN|N>>>>||||1H  0(-UUUUHHN|O1: 0(-UUUUHHN|P1[ 0(-UUUUHHN|Q1 H( 0(-UUUUHHN|R1Z:b 0(-UUUUHHN|S1.:6 0(-,Times .+fO)r) i)g)i)n)a) l) )P)r) o)g)r) a) mUUUUHHN|TaaNNNN''''????rrrr1KCS 0(-UUUUHHN|UaaNNNN''''????rrrr1<LD 0(-UUUUHHN|V>>>㏏|>|||1: 0(-UUUUHHN|W>>>>||||1H 0(-UUUUHHN|X>>>㏏|>|||1x3 0(- +y1s)t)r)u) c)t)u) r)e)-)s)h) y(Gf)u) n) c)t)i)o) n) a) l)i)t)yUUUUHHN|YaaNNN?9'''???rrr13 0(-(Us)t)r)u) c)t)u) r)eUUUUHHN|Z1*3v 0(-(W9s)y) n) c)h) r)o) n) i)z) a) t)i)o) n (f8A)O)P) )P)r) o)g)r) a) mUUUU13 + 9C) o) m)p) o) n) e)n) t)s1(A)s)p) e)c)t) )11-I(BA)s)p) e)c)t) )2num F:M-+.>> S&WordMicrosoft Word&Word D  2 @@$Use Word 6.0c or later to 2 @$view Macintosh picture. D  '',  Helvetica .(8A) p)p)l)i)c)a)t)i)o)n($8D) e)v)e)l)o)p)e)r(o8Q) o)S(}8D) e)v)e)l)o)p)e)r(8M) e)c)h)a)n)i)s)m(8 )D) e)v)e)l)o)p)e)r %?">" +/ ))? b/"bO UqU^UU^^Uqeneennequ~uu~~uqqqqqqqqqqq%.%%..%q5>55>>5qENEENNEqU^UU^^Uqeneennequ~uu~~uqqqqqq /1'Q,Times(L)o)g)i)c)a)l) )M) e)t)h)o)d) )C)a)l)l)  (R7n"(R 8W"8- X{"zX" `s"r /q"/E6EE6/6p"/E6EE6/6+Y S)y)s)C)o)n)d =}K"J} a"ba( "z3 /q"p"(S)y)s)C)o)n)d \/"\P([ /"P-#`"# 1/ / /12S8(C)l)i)e)n)t12/8(O)b)j)e)c)tq"R kRJR JlkRJp"R kRJR JlkRJ(oD)e)l)e)g)a)t)e18+QS)p)e)c)i)a)l)i)z)e)d) )O)R)B1i8(S)p)e)c)i)a)l)i)z)e)d) )O)R)BQqQqQq                                 Qq                  Q0q0#$%&())*+,--../////..--,+*))(&%$#!  !##$%&()*+,-..//00000//..-,+*)(&%$#!  !#Q,Hq,H:;=>?AABCDEEFFGGGGGFFEEDCBAA?>=;:976543210//..-----..//012345679::;=>?ABCDEFFGGHHHHHGGFFEDCBA?>=;:97653210/..--,,,,,--../01235679:QDRqDRKLLMNNNNOOPPPQQQQQQQPPPOONNNNMLLKJJIHHHHGGFFFEEEEEEEFFFGGHHHHIJJKKLLMNNOOPPQQQRRRRRRRQQQPPOONNMLLKJJIHHGGFFEEEDDDDDDDEEEFFGGHHIJJKQHVqHVOPPQRRRRSSTTTUUUUUUUTTTSSRRRRQPPONNMLLLLKKJJJIIIIIIIJJJKKLLLLMNNOOPPQRRSSTTUUUVVVVVVVUUUTTSSRRQPPONNMLLKKJJIIIHHHHHHHIIIJJKKLLMNNOQRYqRYVVVWWWWWWWWXXXXXXXXXXXWWWWWWWWVVVUUTTTTTTTTSSSSSSSSSSSTTTTTTTTUUVVVVWWWWXXXXYYYYYYYYYYYXXXXWWWWVVVUUTTTTSSSSRRRRRRRRRRRSSSSTTTTUUVQHVqHVOPPQRRRRSSTTTUUUUUUUTTTSSRRRRQPPONNMLLLLKKJJJIIIIIIIJJJKKLLLLMNNOOPPQRRSSTTUUUVVVVVVVUUUTTSSRRQPPONNMLLKKJJIIIHHHHHHHIIIJJKKLLMNNOQAKqAKFGGGHHHHIIIIJJJJJJJJJIIIIHHHHGGGFEEEDDDDCCCCBBBBBBBBBCCCCDDDDEEEFFGGGHHIIJJJJKKKKKKKKKJJJJIIHHGGGFEEEDDCCBBBBAAAAAAAAABBBBCCDDEEEFQ3Eq3E<=>??@@AABCCCDDDDDDDCCCBAA@@??>=<;:998877655544444445556778899:;<<=>??@ABBCDDDEEEEEEEDDDCBBA@??>=<;:998766544433333334445667899:;<Q%7q%7./01122334555666666655543322110/.-,++**))('''&&&&&&&'''())**++,-../01123445666777777766654432110/.-,++*)(('&&&%%%%%%%&&&'(()*++,-.Q0q0&'()***+,--..///////..--,+***)('&$#"!!!  !!!"#$&&'()**+,-..//0000000//..-,+**)('&$#"!!  !!"#$&Q"q"  !!!!!!!    !!"""""""!!  Q q                                                               Qq                                       QqQqQqQqQqQV( N)e)t)w)o)r)kq8`8``88p8`8``88qDZDZZDDpDZDZZDDUUUUHH[qGMGMMGG pGMGMMGGUUUUHH[qRXRXXRR pRXRXXRR(CC)o)n)t)r)a)c)tqDZDZZDDpDZDZZDDUUUUHH\qGMGMMGG pGMGMMGGUUUUHH\qRXRXXRR pRXRXXRRq8#`87`#`q887p8#`87`#`q887qD,ZVD8Z,ZJDVD8pD,ZVD8Z,ZJDVD8UUUUHH]qG5MRG9M5MNGRG9 pG5MRG9M5MNGRG9UUUUHH]qR/XMR3X/XIRMR3 pR/XMR3X/XIRMR3)tC)o)n)t)r)a)c)tqDNZxDZZNZlDxDZpDNZxDZZNZlDxDZUUUUHH^qGWMtG[MWMpGtG[ pGWMtG[MWMpGtG[UUUUHH^qRQXoRUXQXkRoRU pRQXoRUXQXkRoRUq"jvrvvrjrvp"jvrvvrjrv+ 9S)y)s)C)o)n)dq"MMMgMp"MMMgM(RS)y)s)C)o)n)dq"*a>0a>a>0*w0ap"*a>0a>a>0*w0a(9bS)y)s)C)o)n)dq"R l R Rlp"R l R Rl(oD)e)l)e)g)a)t)eq"jqrqqrjrqp"jqrqqrjrq(|tS)y)s)C)o)n)d7:e7!x S&WordMicrosoft Word&Word G6  2 @@$Use Word 6.0c or later to 2 @$view Macintosh picture. 6FU1 U1 '' Q c"8################################################################ q&@@nn #>!@n!n#!#1Fv81:[81l:8 q&: '::' "##!####  ,Times .+ C) l)i)e)n)t (!C) l)i)e)n)t) )C) o)d)e ''1'5T8   (2R)e)f)e)r)e)n)c)e '' q"X}ZXCX}}CjZXC"XC#%#,###  (nD)e)l)e)g)a)t)e ''" c1 U8   ()P)r)o)x)y ''1W~8  (*zC) o)n)n)e)c)t +$C) a)l)l)b)a)c)k '' q&^u ^juuj ^^"^ # ## ###   (lF)a)c)t)o)r)y (RQ) u)O)  )K) e)r)n)e)l '' q""#?### #   (S)y)s)c)o)n)d '' q""#>### #  (S)y)s)c)o)n)d ''1v8   (O)R)B (dC) o)n)t)r)a)c)t( N) e)t)w) o)r)k ''1 Sl8" c q&;Nf;&DN&NPDf;P;&";& # #*####1S8  +|#Q) u)O)  )K) e)r)n)e)l ''1J8  (-C) o)n)t)r)a)c)t '' q""##### q"   " #####   (S)C)S)C ''"9 "81n8   (.O)R)B ''1 l8   (3O)R)B ''1 E^8   + P)r)o)x)y ''1 08  (P)r)o)x)y (D(O) b)j)e)c)t( % )1))) )C) l)i)e)n)t) )c)a)l)l)s) )d)e)l)e)g)a)t)e(%%2))) )D) e)l)e)g)a)t)e) )e)v)a)l)u)a)t)e)s) )c)o)n)t)r)a)c)t(=% )3))) )C) o)n)t)r)a)c)t) )s)e)n)d)s, Courier +p)r)e)_)m)e)t)h)o)d (=s)i)g)n)a)l) )t)o) )a)l)l(L%m) e)a)s)u)r)e)m) e)n)t) )s)y)s)t)e)m)  )c)o)n)d)i)t)i)o)n)s(d%4))) )C) o)n)t)r)a)c)t) )r)e)t)u)r)n)s) )c)u)r)r)e)n)t) )r)e)g)i)o)n(|% )5)))D) e)l)e)g)a)t)e) )s)e)l)e)c)t)s) )i)t)s) )b)e)h)a)v)i)o)r) )b)a)s)e)d) )o)n(%c)u)r)r)e)n)t) )r)e)g)i)o)n).(%6))) )R) e)m) o)t)e) )o)b)j)e)c)t) )i)s) )i)n)v)o)k)e)d),) )e)v)a)l)u)a)t)e)s) )i)t)s(%c)o)n)t)r)a)c)t),) )p)e)r)f)o)r)m) s) )i)t)s) )m) e)t)h)o)d),) )a)n)d) )r)e)t)u)r)n)s) )a(%v)a)l)u)e(%7))) )D) e)l)e)g)a)t)e) )r)e)-)e)v)a)l)u)a)t)e)s) )c)o)n)t)r)a)c)t(% )8))) )C) o)n)t)r)a)c)t) )s)e)n)d +p)o)s)t)_)m)e)t(h)o)d (s)i)g)n)a)l) )t)o) )a)l)l(%m) e)a)s)u)r)e)m) e)n)t) )s)y)s)t)e)m)  )c)o)n)d)i)t)i)o)n)s(%9))) )C) o)n)t)r)a)c)t) )r)e)t)u)r)n)s) )c)u)r)r)e)n)t) )r)e)g)i)o)n)s(2%1)0))) )D) e)l)e)g)a)t)e) )s)e)l)e)c)t)s) )i)t)s) )b)e)h)a)v)i)o)r(J%1)1))) )D) e)l)e)g)a)t)e) )r)e)t)u)r)n)s) )v)a)l)u)e) )c)l)i)e)n)t00 '' q1V11VV1"]### qO]!]O!O]q5<`K_<`=6K5J_<".M ### q.D=M.M:D=L.Mq:wz{~~~~}||}||{zyxxxxwwwxxxyz{||{|||}~~~~}}z"p### qp~p~zpqv:&w&v%w$x"y zz||{{{||~~}}}}~&((')*+--.///11133354577:966644233111//---+***(((&~~~~}|}}}}}{z{z!y"x$w&"C## # q6CC6;CQAQ"A################################################################  (K 1 '' QT]en"Tf################################################################  +W2 '' Qt"t################################################################  +B 3 '' Q$!52"$*################################################################  (/&6 '' QWph"Wx################################################################  (bt7 '' Qt"t################################################################  +E8 '' Q?IPZ"?R################################################################  (JJ1)100 '' q`El`EbElk`E"m### qf~nmfn~mqqPtsqrPtPs"sH### qoHwWsHwWoWsHQuUf"u^################################################################  + 64 '' Quhx"up################################################################  )9 '' q" C0e Y C0C0Y(e Y"!Y### ##   (*ID)e)l).00 '' q~<CSCRCS~>~<CR"w=### qw:Bw=:Bw=q'Y)'Y)Y)''Y"(### q$,($,(Ql |"l################################################################   (w5 '' QX+h;"X3################################################################  (b,1)0r:x1%  S&WordMicrosoft Word&Word w  2 @@$Use Word 6.0c or later to 2 @$view Macintosh picture. v@ @ ''UUUU1@|| 1n18,Times .+QI)m) p)l)e)m) e)n)t)a)t)i)o)n||11\81a8aa1o8aa18aa18(pC)D)L)S)D)L)R)D)L(cQ)D)Lq3#3#I#_3aaq..DZ.".R##w!.aaQ/"############################################################### #(;I)D)L+CQ)D)L) )+) )I)D)L(HC)o)m) p)i)l)e)r1*1^8aa1.oA8||1FoY8aa1.6Yj8 (B7A)d)a)p)t)a)b)l)e(O7S)y)s)t)e)m(=}Q)u)O) )R)u)n)t)i)m) e(UO)R)B""1UUUU``q 5!j 5 j!j!5 5q!5!j!5!j!j!5UUUU``q!5"j!5!j"j"5!5UUUU__q"5#j"5"j#j#5"5UUUU__q#5$j#5#j$j$5#5UUUU^^q$5%j$5$j%j%5$5UUUU]]q%5&j%5%j&j&5%5UUUU\\q&5'j&5&j'j'5&5UUUU[[q'5(j'5'j(j(5'5UUUUZZq(5)j(5(j)j)5(5UUUUYYq)5*j)5)j*j*5)5UUUUXXq*5+j*5*j+j+5*5UUUUXXq+5,j+5+j,j,5+5UUUUWWq,5-j,5,j-j-5,5UUUUWWq-5.j-5-j.j.5-5q.5/j.5.j/j/5.5 q 5/j D/5/j \ DUUUU``q 5!j 5 j!j!5 5q!5!j!5!j!j!5UUUU``q!5"j!5!j"j"5!5UUUU__q"5#j"5"j#j#5"5UUUU__q#5$j#5#j$j$5#5UUUU^^q$5%j$5$j%j%5$5UUUU]]q%5&j%5%j&j&5%5UUUU\\q&5'j&5&j'j'5&5UUUU[[q'5(j'5'j(j(5'5UUUUZZq(5)j(5(j)j)5(5UUUUYYq)5*j)5)j*j*5)5UUUUXXq*5+j*5*j+j+5*5UUUUXXq+5,j+5+j,j,5+5UUUUWWq,5-j,5,j-j-5,5UUUUWWq-5.j-5-j.j.5-5q.5/j.5.j/j/5.5 " D#5## (\C)o) n) t)r)a) c)t) )D)e)s)c)r)i)p) t)i)o) n)  )L) a) n) g) u) a) g) e(s()C) D)L) )) )-) )d) e)s)c)r)i)b) e)s) )e)x) p) e)c)t)a)t)i)o) n) s) )o) f(c)l)i)e)n) t)s) )a)n) d)  )s)e)r)v) e)r)s) )a)n) d)  )r)e)g) i)o) n) s) )a)n) d(t)r)a)n) s)i)t)i)o) n) s) )f)o) r) )a)d) a)p) t)i)n) g)  )t)o)  )c)h) a)n) g) i)n) g(l)e)v) e)l)s) )o) f) )s)e)r)v) i)c)e).(S) t)r)u) c)t)u) r)e) )D)e)s)c)r)i)p) t)i)o) n)  )L) a) n) g) u) a) g) e(()S) D)L) )) )-) )d) e)s)c)r)i)b) e)s) )s)t)r)u) c)t)u) r)e)s) )o) f( o) b) j)e)c)t)s) )a)n) d)  )t)h) e)i)r) )r)e)s)o) u) r)c)e) )u) s)a)g) e).(+R)e)s)o) u) r)c)e) )D)e)s)c)r)i)p) t)i)o) n)  )L) a) n) g) u) a) g) e(B()R) D)L) )) )-) )d) e)s)c)r)i)b) e)s) )a)v) a)i)l)a)b) l)e) )s)y) s)t)e)m(Yr)e)s)o) u) r)c)e)s) )a)n) d)  )t)h) e)i)r) )s)t)a)t)u) s).) :x1%  S&WordMicrosoft Word&Word {   2 @@$Use Word 6.0c or later to 2 @$view Macintosh picture.  z@ @ ''UUUU1@ 0i(-,Times .+GT) a) s)k)  )2) :(^S) e)l)f)-)A)d) a)p) t)i)v) e(uM)e)c)h) a)n      !"#$%&'()*+,-./0123456789:;<) i)s)m)s(R) e)s)e)a)r)c)h8('T) a) s)k)  )1) :(0A)O)P)  ( "R) e)s)e)a)r)c)h8+GT) a) s)k)  )5) :(gM)e)a)s)u) r)e(~I)m)p) r)o) v) e)m)e)n) t8(T) a) s)k)  )3) :(E) x) p) e)r)i)m)e)n) t8(T) a) s)k)  )4) :(A)u) t)o) m)a)t)e( T) o) o) l)s"#############"#########q"#############"#########q"v#############"N#########qJQJKQJ"q#############"#########q")#########":#######q7> >< 7>"%"#########"#######q"#########"#######q  ""#########"#######qwD:@D^$&R  S&WordMicrosoft Word&Word 3C  2 @@$Use Word 6.0c or later to 2 @$view Macintosh picture. C2i $$i $!"$l"l 5ll $l 5uu 5~~ 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5   5)) 522 5;; 5DD 5MM 5VV 5__ 5hh 5qq 5zz 5 5 5 5 5 q5"$5"5$$"5" 5!"H!K!H"W!K!W"l!K!l"|!K!|"!K!"!K!"!K!"!K!"!K! $!4l,  Helvetica .+4-A)c)t)i)v)i)t)y) )N)a)m)e $l4 ,l,",u",~",",",",",",",",",",",",",",",",",", ",)",2",;",D",M",V",_",h",q",z",",",",","$"$"$_ ,l4+O) N) D) J) F)M) A)M) J) J) A) S)O) N) D) J) F)M) A)M) J) J) A) S)O) N) D) J) F)M) A)M) J) J) A) S $l,(*s1)9)9)8);1)9)9)9)c2)0)0)0)U2)0)0)1 l"u"~"""""""""""""""""" ")"2";"D"M"V"_"h"q"z"""""(nO) N) D) J) F)M) A)M) J) J) A) S)O) N) D) J) F)M) A)M) J) J) A) S)O) N) D) J) F)M) A)M) J) J) A) S 5l q7l>7l7>>l7l 8m>(<mY)e)a)r)s) )1) )&) )2 5lq7B>i7B7i>i>B7B 8C>i)O)p)t)i)o)n) )Y)e)a)r) )3 5lH1AlBD8 q?jCn?lAnClAj?lp?jCn?lAnClAj?l q?ACE?CAECCAA?Cp?ACE?CAECCAA?C1ADB8 q?BCF?DAFCDAB?Dp?BCF?DAFCDAB?D q?C?ACA?p?C?ACA? H!Wl(M"E)x)p)e)r)i)m)e)n)t) )w)i)t)h(S"S)e)l)f)-)A)d)a)p)t)i)v)e) )S)y)s)t)e)m)s HlW1MlN8 qLjPnLlNnPlNjLlpLjPnLlNnPlNjLl qLPLNPNLpLPLNPNL W!ll(\"M)e)a)s)u)r)e) )I)m)p)r)o)v)e)m)e)n)t Wll1alb8 q`jdn`lbndlbj`lp`jdn`lbndlbj`l q`d`bdb`p`d`bdb`1ab8 q`d`bdb`p`d`bdb` q`d`bdb`p`d`bdb`1ab8 q`d`bdb`p`d`bdb` q`d`bdb`p`d`bdb`1b)cD8 qa'e+a)c+e)c'a)pa'e+a)c+e)c'a) qaAeEaCcEeCcAaCpaAeEaCcEeCcAaC1bDc_8 qaBeFaDcFeDcBaDpaBeFaDcFeDcBaD qa\e`a^c`e^c\a^pa\e`a^c`e^c\a^1bc8 qaeacecapaeaceca qaeacecapaeaceca l!|l(q"S)e)l)f)-)A)d)a)p)t)i)v)e) )M)e)c)h)a)n)i)s)m)s(w"R)&)D ll|1qlr8 qpjtnplrntlrjplppjtnplrntlrjpl qptprtrppptprtrp1tu8 qswsuwuspswsuwus qs wsuwu sps wsuwu s1vDwz8 qtBxFtDvFxDvBtDptBxFtDvFxDvBtD qtwx{tyv{xyvwtyptwx{tyv{xyvwty |!l("A)s)p)e)c)t)-)O)r)i)e)n)t)e)d("P)r)o)g)r)a)m)m)i)n)g) )()A)O)P))) )R)&)D |l18 qp qp1)8 qp q'+)+)')p'+)+)')1^8 q\`^`^\^p\`^`^\^ qp !l("A)u)t)o)m)a)t)e) )S)e)l)f)-)A)d)a)p)t)i)v)e("S)y)s)t)e)m)s l18 qp qp1D8 q  p   qAECECACpAECECAC1z8 qx|z|zxzpx|z|zxz qp !l("M)o)n)t)h)l)y) )T)e)c)h)n)i)c)a)l) )&) )F)i)n)a)n)c)i)a)l("R)e)p)o)r)t)s l qnsqsqnqpnsqsqnq qv{y{yvypv{y{yvy qp qp qp qp qp qp qp qp qp qp qp qp qp qp qp q     p      qp qp q"'%'%"%p"'%'%"% q+0-0-+-p+0-0-+- q3858535p3858535 q=B@B@=@p=B@B@=@ qEJHJHEHpEJHJHEH qNSPSPNPpNSPSPNP qX]Z]ZXZpX]Z]ZXZ q`ecec`cp`ecec`c qkpmpmkmpkpmpmkm qsxvxvsvpsxvxvsv q{~~{~p{~~{~ qp qp qp qp qp !l("D)e)m)o l qp q8=:=:8:p8=:=:8: qp !l("R)e)l)e)a)s)e l qp qAFDFDADpAFDFDAD qp !l("F)i)n)a)l) )R)e)p)o)r)t l qAFCFCACpAFCFCAC $! $!$ ! $!! $ 4!4 5!5 ! ! V q"""" " (S)e)l)f)-)A)d)a)p)t)i)v)e) )D)y)n)a)m)i)c) )D)e)s)i)g)n:@D$^&RyK )http://www.ccs.neu.edu/research/demeter/yK Rhttp://www.ccs.neu.edu/research/demeter/:@D$^&RyK "http://www.ccs.neu.edu/home/mattayK Dhttp://www.ccs.neu.edu/home/mattal:@D$^&RyK @http://www.ccs.neu.edu/research/demeter/evaluation/success.htmlyK http://www.ccs.neu.edu/research/demeter/evaluation/success.html:@D$^&RyK Jhttp://www.ccs.neu.edu/research/demeter/course/f97/projects/overview.htmlyK http://www.ccs.neu.edu/research/demeter/course/f97/projects/overview.html:@D$^&RyK ,FTP://ftp.cs.utexas.edu/pub/predator/web.psyK Xftp://ftp.cs.utexas.edu/pub/predator/web.ps0.$ >$  $ $($ $0R"n>"n n"n"("n$0(p# >p#  p# p#(p# $0Hp#>p# p#p#(p#$ࡱ; vSummaryInformation(k,@Microsoft Word 6.0.12; v9m;MNO\]rs  ' ( ) + , G H a b c e f ~   uD"C\cGuDd"C\cGuD!C\cGuD|!C\cGuD!C\cGuD C\cGuD C\cGuDUcUcC     $ % > ? @ B C F G Z b V_!#(   $'0'e(((((&)()X)----0/-000K1M1 22s2u2224(445m5{67-7w9Uc]]uD4$UbcbcbuD]aUcUc]cuD#C\cGuDuDL#C\cGLw9x99;r===FFFGHHMMMMxOyOzOOlPtPQQRR{V|V~VVXX_YlY>ZQZZZ\\\\]]]^^__$abcccceefggSkTkkAmNmemrmmmmmfnknnnoPUc P]bc PU]c P]cUbc]uDuD0zuD$4uD]aVcUcVcLo'o(o*o+oo(pssssst#tJt`ttttuu[uuuuuuuuy zXz8{{{{{{{{|2ͅ΅KAfg'aݚ?ַUU]uD]a PU]^c P]^c P]cUcVPPU]^bc]cPUc PU]c P]c P]bcHd "4wEFUéĩͩRhOPf̳ڳ۳Tyܶ2[!(C#6#$@ZmNOrsyz uDccUcUVU]h uD8cuDxU]c]cUcVSz !BCEo@\]y{c-.*+o|,B/Tbm@uDC\GV]]]c U]ckuDC\^bGPcuDPccUcP uDcuDC\GcJ@AMNk     <@BuUcPcuDPc P]cPc^cuDC\GPuD C\Gc uDc/%:OabuBUm+=(#(#   (#(#<    <     <    <    <      3!l  j,"3l ~ ,"33#=>L[jkw +?Ucuv 0 <    <    <    <    <    <       <    <    <    <  3l  j,"*0BCDEXhtMN  (#(#(#(#(#(#(#!3 x3!l pP,"3l  j,"3#- g  D E F Z V#     (#(#(#(#(#(#(#(#(#(#(# (#(#(#(#(#(#(#(#(#(#(#(#(#(#(# 3!" x3 4.3<<3" 3 4.3!3me "$'''0'e(((&)X)F+^,----0/I/f////"0-00K1 2s222(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#T(#T(#T(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#p(#`(#p(#p(#<3<<333<<33<<33'2445m55 6{67x9;r==[A,C"D#FFFFFFFFFFFGJJ(#(#(#(#(#@(#(#(#(#(#(#(# (#(#(#(#(#(#(#(#(#(#(#(#(#(#(# (#(#33# <3 4h% <<3 4h<<3JMMwOxOzOOOcPdPQRaSbSzV{V}V~VVVXXZZr[s[[J\\\(#(#(#(#(#L(#(#(#(#(#(# (#0(# (#(#|$|||(#(#(#(#(#(#@(#0(#0(#3 310 310& h3 4hh33 3& ' ( ) \\]]]]^^__#a$abbcccfh)iSkTk+ooo(#(#(#(#(#(#0(#0(#0(#(#(#(#(#(# (#(# (#(#(#(#(#!(#(#(#<<3<<333& ' ( ) 3 3!% h3 4hh" 3 4hh333oo(ppyrzrsstuuEwyyy zXzzz8{{{{{{{(#(#(#(#(#(#(#(#(#(#(#(#(#@(#@(#@(#(#@(#@(#(#(# d h%3<3 4h <<3 4h3 3!3<<3<3{{{{{{{{{|||"|*|0|1|C|N|U|Z|[|o|z||||||||||}~|2 N N N N N N(#(#(#(#(# (#<3<<33 d4h % 3$2.܇ˆK $-5@AKNS(#(#(#(#(#(#p(#p(#(#(#(#(#(#ff3!dt42 B d3<3 4h <<3 4h3<<3SWXknsvwxܑfgQD(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#@(#<3 4h <<3 4h<33<<33 d42 B 3?'aݚ?ўdɠN͡ Ѣ"4vw(#@(#@(#@(#(#@(#@(#@(#@(#(#(#(#@(#@(#@(#(#(#(#(#(#(#(#(#@(#(#(#(#33 <<3& ' ( ) 33 <<3 4h<<3<3 4hwNfEF)ZéĩST;<AOPf̳ͳ۳ Tyܶ2(#(#0(#@(#0(#0(#0(#(#(#@(#0(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#+3<<3<<333( 83 4h83!2\4"&'(Cxw(#(#(#(#(#(#(#(#(# (#(#(#0(#(# (# (#(#(#(#(#(#(#(#(#(#(#(#*x3)* 0x3 4.*x3*x33333<<3#e?@ZYZ34NOrsc(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#3333333<<3<3&DEFGHIJcdr 78FWk(#(#(#(#(#(#(#(#(#(# `n `n `n(#(#(#l 0`nl 2 ^3333$!2FZno&]+l 0`nl 0`n(#(#(#l 0`nl 0`nl 0`n(#(#(#(#(# (#333l  ^(+,n+?@]mquyz{&:N(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#^||3l j U@+"33(Nbc -.)*+bBkl ||^||||^||||(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#(#<<3333333l x t"3"    <@AB(#(#(#(#(#(#(#(#(#(#(#h(#(#(#h##""<#<#(#(#$$3$$3$$<<33x33333,K@Normal3]a 8@8 Heading 1 < U]ck2@2 Heading 2<<hUVc6@6 Heading 3P<]c8@8 Heading 4`p<U]c2@2 Heading 5P<c4@4 Heading 6P<Vc2@2 Heading 7<]4@4 Heading 8P<V]8 @8 Heading 9 0p<0 UV]c"A@"Default Paragraph Font* @*Footer!c O Body Text 3c @ Header !f0@"f List BulletF  4h]cf1@2f List NumberF  4h.]c)@A Page Numberc(@Q Line NumbercVObV Preformatted8 10) ` @`! %(+]OqStrongUcO z-HTML Tag]^bOCODE]c$B@$ Body Text<<cO Hyperlink^bc&O&FollowedHyperlink^b c(O( Proposal Body<]cZO1Z ReferencesAh 4 hh[]"O" Body Text 2c$O$ Document Map / ]$@$TOC 1 !# c@TOC 2"@TOC 3#@TOC 4$X@TOC 5% @TOC 6&@TOC 7'@TOC 8(x@TOC 9)@$O$a120*3 ]a c&"@&Caption +<<Uc)bloF   !                              F *m2"AxL{SYWb(lEtxџ#Q±)A  O    -Qr' !6 w9oz@=02J\o{2Sw2#+N  !"#$%&'()*+N\r (+Gbe~$?BFy B@M  %%%%%%%%%(.1!*C\tS _Toc410634610 _Hlt410635031 _Toc410634939 _Toc410634611 _Toc410634940 _Toc410634612 _Toc410634941 _Toc410634613 _Toc410634942 _Toc410634614 _Toc410634943 _Toc410634615 _Toc410634944 _Toc410634616 _Toc410634945 _Toc410634617 _Toc410634946 _Toc410634618 _Toc410634947 _947411595 _947411657 _947411699 _Toc410634619 _Toc410634948 _Toc410634620 _Toc410634949 _Toc410634621 _Toc410634950 _Toc410634622 _Toc410634951 _Toc410634623 _Toc410634952 _Toc410634624 _Toc410634953 _Toc410634625 _Toc410634954 _Toc410634626 _Toc410634955 _Hlt410443474 _Toc410634627 _Toc410634956 _Toc410634628 _Toc410634957rG%%%%&&&&--K.K. / /s/s/{S{S{S##QQ))##AA    !"#$%&'()*XX%%%&%&W&W&I.I. / /q/q///{S{S{S33eeBB YYC,,  , Ken AndersonMHD:Desktop Folder:98-12.wd6@ >jMTimes New RomanTimes Symbol"MArialHelvetica MTimes MCourier !Tahoma"h!!$AALP/JL ACTD BAA 97-32 Ken Anderson Ken Andersonࡱ; v