Current Research Achievements

1. The Lowband Architecture.

We use active multimedia objects to adapt themselves to the available bandwidth and display characteristics. An active multimedia object is some form of multimedia such as an image or a video with an associated piece of code that can control various aspects of the object either at the point it is served, cached or displayed. These aspects are such things as the level of lossy compression in a JPEG image, the frame rate of video, or the colour depth and size of an image adapted to a specific display device. We use the obvious media hierarchy to represent the media, as in Figure 1, and provide control interfaces to the media, as in Table 1. These control interfaces can be remotely called across the network, transforming the media before it is downloaded. As long as the overhead of the remote calls plus transformed media size is less than the original media size, then the transformations may considerably reduce the time taken to download the media, yet be more suited to the display. The control interfaces are the Open Implementation of the components in our technology. Full details of the network aspects of the architecture can be found in Wakeman, I (1998) and a diagram of the archetecture is to be found in Figure 2 below.

Figure 1: A partial media hierarchy


Interface name	amp; Description	amp; Applicable classes
compress	amp; Apply a lossless compression to the media	amp; uncompressed media
scale	amp; reduce media to display in a smaller size	amp; Video, Images
reduce	amp; Apply lossy compression	amp; all
toAscii	amp; Translate media into some ASCII equivalent, typically a description of what the media represents	amp; all
toBmp	amp; Convert an image to an X-Bitmap	amp; image
toGiff	amp; Convert an image to a Giff	amp; image
toHtml	amp; Convert a media to some html representation	amp; all
toProgressive	amp; Convert a JPEG to a progressive scan representation	amp; JPEG
toBaseline	amp; describe JPEG using Huffman coding only	amp; JPEG

Table 1: Control interfaces A Diagram /Schematic of the lowband Image Proxy Arcitecture

Figure 2: Image Proxy Schematic

2. The Lowband Image Proxy Server.

To demonstrate the viability of the architecture, we have developed a test bed application that acts as an image proxy for web pages, providing similar functionality to Fox (1996). Image tags within pages requested by browsers are replaced by applets which talk to a proxy holding the image, applying the transformations before downloading the image.

The decision about what set of transformations to apply to a given piece of multimedia is made within the applet. This decision comes from the interpretation of an instance of what we have termed the Media Policy Language mpl. This script is at the heart of the configurability of our system it weaves the transformations and media together. As the name suggests, mpl defines policies on what to do to media in particular situations of bandwidth availability and display characteristics described in section below.

2.1 Run-time Policies: The Media Policy Description Language.

We have chosen to implement the policy of degradation at run-time for the following reasons:

The underlying technology has four main methods through which the implementation of the transferred media can be manipulated. The application thus has at least four degrees of freedom in which we can change the implementation, and so providing a wide choice of trajectories of degradation.
The application using the media is very generic - the Web model of documents is being pushed by Microsoft as others as the basic metaphor for the next generation of machine interfaces. Since the uses of the application are legion, we as designers cannot constrain the choice of policy degradation.
The ability to transform the media entirely across types implies an even wider implementation space. Since transformations may be chosen as more convenient by the user, eg. a partially sighted user may transform text to audio, we believe that allowing users to determine policies of adaptation will provide more exciting use of the technology.
In downloading a particular media instance, there are two associated actors who are interested in how the media is downloaded and displayed -- the person initiating the download and the author of the media. Each of these actors may have preferences about how media should arrive -- users may want download as fast as possible, yet authors may require a colour display. To allow each of these actors to define requirements, it is easier to resolve run-time resolution of policies.

Policy degradation objects are written in the Media Policy Language mpl and are interpreted within the application and the server. They can be combined with each other to form new policy objects representing the combined needs and experience of user, author and system designer.

The policy objects have been used to control the preferences users have in how images are viewed across the Web. However, the principle applies equally to other multimedia application (networked or otherwise) and indeed to any application that wants to scale it's interface. User, authorial and default policies could be devised to allow an application's widgets to present themselves in a sensible manner on differing platforms and visual displays.

The mpl is a rule based language that allow the mapping of certain actions or mutations to specific groups or subgroups of media according to the various current networking and display conditions.

The general format is:

path : condition : action [, submission]

Path means apply action to the specified media type if the condition is true and some rule belonging to a different rule group doesn't override the path. Conditions are legal boolean expressions.

We use environment variables to hold values of networking and display conditions and attributes of the media, as determined by the run-time environment (Sharples, 1997). Each environment variable has a unique name and has a type. Currently variables are:

FILESIZE - int
MEDIA-HEIGHT - int
MEDIA-WIDTH - int
MEDIA-DEPTH - int
DISPLAY-WIDTH - int
DISPLAY-HEIGHT - int
DISPLAY-DEPTH - int
BANDWIDTH - int (in Bytes/second)
RATE - int (flow rate for streams eg. frames per sec)
MIME - string (mime type of media object)
META - string (used for passing any other info)

Actions are compress (lossless), reduce (quality: lossy compression), scale (Dimension), and transform (from one media to another) etc, as in Table 1.

For instance, if a user wishes to compress all objects over 10k

media.* : SIZE >= 10*1024 : compress

or if a user has a monochrome browser

media.image.* : true : toMono

or for a more complicated expression when the browsers is always used over low bandwidth links.

media.image.jpeg : meta(progressive) == false : toProgressive, submit default
media.* : true : scale 75, submit author media.* : true : reduce 50, submit author
media.* : true : compress 10

Policies can be combined with information to the environment to select paths of degradation depending upon the available constraints, so if the user wishes to ensure that all download times are less than five seconds, they first attempt to reduce the quality, then if this fails, they scale the object, using the resolution process (described below),

media.* : SIZE/BANDWIDTH>5 : reduce 50
media.* : SIZE/BANDWIDTH>5 : scale 75
media.* : true : compress 10

An author's policy to make sure that a JPEG fits in the available space:

media.image.jpeg."www.site.org/pics/mypic.jpeg" : MEDIA-WIDTH > DISPLAY-WIDTH : scale (MEDIA-WIDTH / DISPLAY-WIDTH)

2.2 Policy Resolution

The policy scripts are compiled together to create a single executable policy. The policy can act on the multimedia object with which it is associated through the various interfaces discussed earlier: transformation, reduction, scaling and compression.

When the policy is activated (asked to transform its media), it goes through a number of parsing and resolution phases. These phases determine which rules are relevant to the associated multimedia object, which rules can be removed or overridden by others and they establish a definitive precedence order between rules from different policy sources.

Initially any rule which applies to media other than that of the attached multimedia object are removed. Then rules which clash are resolved according to the following criteria:

user rules have precedence over authorial and default rules, except when 3. or 4. is in place,
authorial rule have precedence over default rules, except when 3. is in place.
user and authorial rules can specify that they submit to default rules.
user rules can specify that they submit to authorial rules.

Four phases of multi-pass rule activation then take place:

\begin{description}

Transformation Transformation involves firing rules that transform the multimedia object from one type in the media hierarchy (figure 1). Rules that utilise the transformation interface are key to the writing of policies that cope with difficult display attributes and location dependant data.

Reduction Reduction involves firing rules that utilise the reduce interface thus reducing the quality of the attached multimedia object and so improving down load time. The reduction phase is a multi-pass operation. Each pass of the rules further reduces the multimedia object. Passes are repeated until no rule is fired, that is, all of the media's size and quality requirements are met. Of course this may never happen! So, the multi-pass mechanism is constrained by a set of heuristics which can identify looping, the exhaustive limits of compression and rules which reduce the multimedia object to the edge of our perception.

Scaling Scaling is the process of altering the dimension of the Media. Images are scaled in the X,Y dimension as are Video (although they also have the frames per second dimension). For some media types scaling is not meaningful or takes on a different meaning. For example it is not meaning to scale ASCII and it only meaning to scale audio in terms of amplitude or tone -- qualities that can be adjusted to suit the user, but do not effect the download time.

Compression Compression is a simple one-pass treatment of using non-lossy compression where possible. Media that benefit from this are those which, unlike JPEG and MPEG, do not support their own compression technique. Anything under the mime type mime:text/* can benefit from the use of non-destructive compression (The GZIP compression utility is used as a publically available non-destructive algorithm).

This multi-phase multi-pass process of resolution is at the heart of what makes the policy work. It combines the disparate needs of user, author and the system designers.

3. A Design Methodology for Adaptive Applications.

3.2 Adapting to Constraints: Choices in Application Design.

``An adaptive application is one in which the application changes its behaviour according to the perceived constraints in the environment, so as to maintain the semantics of the application for the user.''

Figure 3: A Layered View of the Adaptive Application

If we take the above definition as our starting point, then we can immediately break the problem of designing an adaptive application into various stages. The constraints in the environment for the application should first be determined. For mobile computing applications, the likely constraints are network quality of service, battery power and display capabilities.

We must next define the semantics of the application. What is the application trying to achieve? This is user and task specific, and can vary from context to context. As we will argue, the more generic the application, the more difficult it is to determine the application semantics. Having made a best guess at the semantics, a design goal is to ensure that the semantics of the application remain invariant across the constraint-reacting behaviours of the application. By doing so, we hope that the utility of the application to the user remains high.

In order to maintain the semantics, the changes in behaviour of the application should ensure that the application continues to work whilst adapting to the changing constraints. If the behaviour is changing to adapt to a restriction of some needed resource, such as bandwidth, the change should inflict the minimum damage upon the essential functionality of the application. This leads us to a solution in which the implementation of the application should be opened up so as to allow the choice of some equivalent but less resource-hungry implementation. We thus come to the first design point in our methodology -

Design Choice: Providing an Open Implementation of the components in the Underlying Technology

The concept of open implementation (Kiczales, 1996) from software engineering enables the designers of components to open up the implementation of their component so that it can be adjusted and adapted to suit various needs. The behaviour of a component should be described by its interface abstractions, but the implementation is generally hidden behind the interface. Following the design guidelines of open implementation (OI) (Maeda, 1997), the designer of the component will offer other meta interfaces through which the programmer can adjust the implementation of the component. If we are aiming to produce distributed applications which scale across network and display capabilities, then OI offers a suitable software engineering approach to enable this scalability. Simply put, the OI part of a software component exposes the network requirements of a particular implementation of a component. By allowing the adaptation controller to manipulate the implementation of a component, the controller can adjust the network requirements of the component and thus adapt the component to the prevailing network conditions. Following the guidelines in (Kiczales, 1997), the designer of an open implementation interface should attempt to:

Define the abstract black box interface, which instantiates the ``useful'' behaviour of the component.
Using the domain knowledge of both the inherent implementation of the component and of how clients will use the component, define interfaces which allow the client to control implementation strategies.

The inherent implementation of the component is based around the abstractions that will be used to implement the component. For the case of the file caching mechanism described in Maeda (1997), it is the disk buffers and caches of a file system. For the network retrieval architecture describedearlier, the abstractions are the compression schemes and representations of the various forms of multimedia. Since the abstractions used in understanding the implementation of a component are closer to the domain of the application, the designer will be able to better tune the adaptation of the application.

Design Choice: Determining the Degrees of Freedom in degradation trajectories

The OI interfaces of the components will normally provide a discrete set of implementations upon some variation. Imagine a simple speech tool which provided a set of encodings to use for speech. As the degree of compression in the encodings gets higher, the bandwidth requirements decrease but the quality of the resultant speech is decreased, thereby decreasing the utility of the application.

For more complex applications, each component may provide other choices of implementation which are orthogonal to each other in that they can reduce resource usage in different ways. If we can add redundancy to the speech encodings, using some of our bandwidth to provide data to repair lost packets at the expense of greater latency, then we provide another set of choices of about how to use valuable bandwidth.

If we regard each component as supplying an OI interface which can be adjusted independently of the other components, the designer thus has a choice over each component of an implementation. The number of independent axes which contain implementation choices is the degree of freedom of the application. Adjusting the Open Implementation of a component can be viewed as placing the component at some new point in the space of (implementation choice, resource usage, application utility) space. As we select a new set of implementation choices to decrease the resource usage of a component, we generally decrease the utility of the overall application.

Thus for each of the possible implementations of the component, we could theoretically measure the utility of the resultant application. The designer must understand this space of possible implementations, for it is from this set of implementation choices that the designer chooses a path of degradation in the face of resource constraints.

Design Choice: How transparent should the degradation be?

Having plotted the implementation space, the designer must next decide how the resource usage is to be monitored and controlled. For networked applications, this has generally been the congestion signal such as a packet loss, or for processor sensitive applications, by examining the process queue length (Kouvelas 1998). In our abstractions, the control is through a generic adaptation controller, but this is generally integrated with some other component. The designer must next decide what the resource availabilities upon which to switch implementations, and whether this should include the user within the loop or not. Systems which exclude the user and use closed loop feedback need to worry about the stability of the control loop, and the effect that varying application utility will have upon the user. Systems which include the user must be certain that the user is educated about the need for their collusion in adapting the application. Systems in the latter case include battery monitors querying the user about whether to close down applications, or video conferencing system in which adaptation would reduce the quality to less than the minimum demanded (Bolot, Wakeman and Turletti 1994).

Design Choice: Selecting Run-time versus Design-time Behaviour Specifications

Having investigated the implementation space and decided upon how degradation should be controlled, the designer must next decide when the possible trajectories through the implementation space are decided -- when designing the application or through interpreting some later set of instructions.

Design-time behaviours include the use of reactive protocols in the face of congestion, such as in the video conferencing tools vic and ivs. These are fixed policies of degradation, or fixed trajectories through the implementation space. In general design-time policies are easier to encode.

However, as the applications become more generic and are used for more disparate tasks, then the semantics of the application are increasingly determined by the context of use, and the utility of the application is difficult to pinpoint. An application which simply reports the state of some object has simple semantics and will only be used in a very limited set of contexts, and thus the behaviour can be pre-determined. The user can either have an update or not. On the other hand, a web browser is used by users in many different ways \cite{light98:_inter_web,marchionini96:_brows}, ( Light 1998 ;)and the semantics of the retrieved pages depend highly upon context. As designers, we can only make best guesses about the utility of various implementations, and so we can only select trajectories through implementation space that approximate the profile of some imaginary user. In real situations, we must allow users to override profiles to determine which aspects of the application semantics are important to them at run-time.

Design Choice: Selecting Fixed Trajectory Behaviours

Users of applications don't care about the subtleties of network and display performance -- they just want the software to work. Thus whether the behaviours are fixed at design-time or run-time, the user should be able to use the application without fiddling with editors to set values up. So the designer must determine and install a set of trajectories through the implementation space that correspond to some expected path through resource availability. We thus provide some fixed trajectories which give the application a behaviour when degrading in the face of resource shortage. In doing so, the designer has to determine the likely contexts in which the application is to be used, so that they can guess at the likely semantics, and then experiment and select appropriate behaviours.

The choice of fixed trajectories has a large impact on whether users will use an application and so is a very important part of the design process. We believe that the context and associated semantics can only be determined by users, so as designers we must bring users into the design process. If possible, we should study them \emph{in situ}, but if this is not feasible due to project budgetary constraints they should at least be used in experimental mock-ups.

Design Choice: Designing Appropriate Interfaces for Customisation

Traditionally, customisation of networking and distributed applications has been via dialogues which provide direct access to actual variables within the program. However, this is is of limited use when the abstractions are themselves complex and of no meaning within the experience of the user.

The open implementation of the components provides abstractions within the application domain to allow manipulation of behaviour. However, these abstractions may be far removed from the experience and understanding of the user. In particular, the various nuances and abstractions of networked and distributed applications are rarely understood by programmers, so it is unlikely the the user will be able to comprehend behaviour specification in terms of networking abstractions.

Instead, the abstractions of the application must be mapped from the system image onto metaphorical controls which build upon the experiences of the user. By using metaphors from the experience of the user, we can educate the user to have an appropriate mental model of the application (Clarke and Sasse, 1997).

Malcolm McIlhagga

Last modified: Mon. Jun 1 11:55:24 BST 1998
page master copy