Verification of Compositional Software Architectures

Diana Lee and Robert Filman
Microelectronics and Computer Technology Corporation
November 4, 1997
Microelectronics and Computer Technology Corporationís (MCC) Object Infrastructure Project (OIP) is developing a reference architecture to automate implementation of system-wide requirements in a system assembled from components [1]. To verify such a claim, a test application that can be used to explore issues in a component-based, distributed, real-time environment is needed. To be useful as an evaluation of the reference architecture, the test application should be: In response to these needs, the Object Infrastructure Project has developed a test application, Vendoom. This paper discusses the features of Vendoom that make it a valuable exploration and evaluation tool for a component-based, distributed, real-time computing environment, and this paper provides an example of how Vendoom is being used to evaluate the Object Infrastructure reference architecture.

Vendoom, a "Game" and Model of Business Drivers

The first goal of Vendoom is to create an abstract application that is easily understood and is able to model key business drivers in the real world. Business drivers include issues of:

The goal is to capture these business drivers in a test application environment without descending to the details of particular applications. It is preferable for the test application to remain general and flexible enough to abstractly model many different industries.

The result is a "game" called Vendoom , a game based on teams of players who wander a maze of rooms searching for treasures and destroying their enemies. The team earns points when its players find and claim treasures and shoot the opposing teamís (enemy) players; the team is penalized points when its players pick up traps and shoot members of their own team.

The element that elevates Vendoom from being a game with bad graphics to a test application that addresses business drivers is a network of controllers and sensors. Players, while in the maze of rooms, have limited vision. They can see other players and other objects, but they cannot determine if other players are on their team or the opposing team or if objects are treasures or traps. Each room has a sensor that can provide that information, but to obtain it, the players must "call" the appropriate sensor. The call is routed through a network of controllers. The contest between two players of opposing teams thus becomes a question of whose network will route the call to the sensor first, enabling the player to kill before being killed. By varying the player and controller algorithms, different elements of the distributed coordination space can be explored. This relationship is illustrated in Figure 1.

The quality of service business driver is modeled by overloading the network of controllers and sensors. By doing so, it is possible to have a number of tasks waiting on the limited controller resource. We can test quality of service by varying the point value of different players. Since its better not to have higher-valued players shot, a clever network will give their requests higher priority.

The network of sensors and controllers model the communications network business driver. In fact, one can characterize Vendoom as "competitive cell phoning." By dynamically making controllers fail, we can test the ability of controller network algorithms to respond to failure. By including network control algorithms with routing information, data replication can become more important. By allowing networks to "spy" on each other and inject alternative messages permits issues of security to be addressed.

Figure 1: Beware the Dragon

The dynamic component invocation can be modeled by viewing the network of controllers as successive processing functions of a multi-step-processing problem. Possibilities for their processing functions range from algorithms that determine network paths to algorithms that coordinate the activities of all the players and sensors on a team.

A Vendoom Scenario

A Vendoom scenario might play as follows: Sir Lancelot of the blue team enters the Throne Room and sees Player A, Player B, and an object T. He also sees the blue teamís sensor whose number is 555-1234. Sir Lancelot calls his controller asking to be connected to 555-1234 for a detailed description of the room. Sir Lancelotís controller routes the request to the blue teamís sensor and relays the reply: in the Throne Room there is Sir Lancelot of the blue team worth Ė10 points, King Arthur of the blue team worth Ė 35 points, the Wicked Mordred of the red team worth 15 points, the blue teamís sensor, the Holy Grail worth 45 points, and exits to the north, south, and east. (In the meantime, King Arthur and the Wicked Mordred are calling their sensors to get information). Sir Lancelot shoots The wicked Mordred (earning 15 points for the blue team) and picks up the Holy Grail (earning another 45 points).

Vendoom: Quantitative, and Flexible

Vendoom produces quantitative data useful for evaluation. Because the ability of the team to win is dependent on their ability to get messages through their network, the teamsí score becomes a quantitative measure of effective use of the network. This feature makes Vendoom valuable in evaluating distribution and network issues.

Vendoom is flexible enough to adapt to evolving and changing business drivers. This flexibility comes with the ability to change the rules of the game and the ability to change the behaviors of the players. This feature of Vendoom was used early as the project honed the telecommunications business drivers. For example, it turns out that an effective strategy in Vendoom can be a "Rambo" strategy in which a player shots all other players, including members of his own team. This strategy can be countered in the game design by introducing a team of civilians who are expensive in penalty points to kill. A more interesting variation became clear in the first large-scale competitions: teams that were behind caught up as the losing team lost players; the congestion on the losing teamís network declined enabling better response for the remaining players. This artifact was especially inappropriate as a model for telecommunications, where failure to complete a call is likely to provoke another attempt, not permanent destruction of the cell phone. The rules were extended to allow a version where shot players were merely rendered ineffective while they remained in the same room (a trivial but successful extension). These examples illustrate the flexibility of the underlying model and guiding modeling principle that if the current rules do not capture the business model, change the rules.

Vendoom can be used to evaluate network path algorithms, network failure detection and recovery algorithms, queue triage mechanisms that purge tasks in the queue whose due date has expired, queuing algorithms, and central planning algorithms that coordinate the activities of all the players and sensors on a team.

The Object Infrastructure Projectís Reference Architecture

MCCís Object Infrastructure Project is using Vendoom to evaluate its architecture for component-based applications. Specifically, the Object Infrastructure Project is addressing the problem of imbuing a system assembled from software components with system-wide properties such as security, reliability, consistency, managability, and real-time quality of service, the "ilities". Because the scope of these properties extends beyond a single component and cannot be encapsulated, it is difficult to implement these "ilities" without interleaving and tangling "ility" code within the components and thereby destroying the "component-ness" of the system.

To address this difficulty, the Object Infrastructure is developing a reference architecture (Object Infrastructure Framework) that enables "ilities" with minimal disruption to the components.

The Framework and the Real-Time Quality of Service "ility"

The first experiments of the Object Infrastructure Project include a version of the Object Infrastructure Framework, an implementation of Vendoom on the Object Infrastructure Framework, and a demonstration that the framework itself could be used to control quality of service of the overriding Vendoom application. For real-time quality of service, the project chooses to address issues in soft real time systems. Soft real-time systems are characterized by "higher priority" tasks being given preferential allocation of computational resources. The Object Infrastructure Framework implements this preferential treatment in a queue control mechanism that selects, from the available tasks waiting for processor time, the highest priority task to execute next.

Using Vendoom to Explore Quality of Service Issues

Inserting quality of service behavior into Vendoom required only two small (one line of code) changes to the Vendoom application:

The project ran several test cases with the blue team modified by these changes. The red team was designated the control group and was given a first-in-first-out queue. Figure 2 illustrates the results:

In the figure, the dark gray line, a 45-degree line, represents the points in time that the blue team score is equal to the red team score. Points below the 45 degree lines represent when the blue team score is greater than the red team score. Points above the 45-degree line represent when the red team score is greater than the blue team score. The figure shows in these 8 trials, points are below the 45 degree line where the blue team with the priority based queue control, is winning the vase majority of the time.

From the figure, one concludes the Object Infrastructure Framework is successful at impacting the quality of service. The blue team that implemented the priority queue quality of service gained a definite advantage by allowing their more valuable players better access to the network of controllers. What is significant about these trials is that the Object Infrastructure Framework, with minimal impact or disturbance to the Vendoom components, achieves quality of service in Vendoom. Quality of service is achieved and the components remain independent and reusable. Our next planned experiments will contrast scheduling by due date versus priority.

Vendoom is a Success as a Test-bed

In the case of the Object Infrastructure Project, Vendoom is able to give quantitative data that can be used as a measure of effectiveness of the Object Infrastructure Frameworkís ability to address quality of service. Vendoomís scenario captures many key business drivers such as: quality of service for an overloaded resource, communications network issues, and tasks requiring multiple steps of processing. Furthermore, the scenario captures these drivers in an abstract application that is flexible and general enough to model many different industries. By changing rules of the Vendoom game and behaviors of the players, the Vendoom model is also flexible enough to adapt to evolving and changing business models. Lastly, the rules of the Vendoom game are easy to understand, and the game and quantitative results make for great demonstrations of a projectís achievements.