Real-time systems comprise computers that must generate correct results in a timely manner. This involves a wide spectrum of computing systems found in our everyday life ranging from computers in rockets to our mobile phones. The criticality of producing timely results defines the different types of realtime systems. On one hand, we have the so-called hard real-time systems, where failing to meet deadlines may result in a catastrophe. In this thesis we are, however, concerned with firm and soft real-time systems, where missing deadlines is acceptable at the expense of degraded system performance. The usage of firm and soft real-time systems has increased rapidly during the last years, mainly due to the advent of applications in multimedia, telecommunication, and e-commerce. These systems are typically data-intensive, with the data normally spanning from low-level control data, typically acquired from sensors, to high-level management and business data. In contrast to hard real-time systems, the environments in which firm and soft real-time systems operate in are typically open and highly unpredictable. For example, the workload applied on a web server or base station in telecommunication systems varies according to the needs of the users, which is hard to foresee. In this thesis we are concerned with quality of service (QoS) management of data services for firm and soft real-time systems. The approaches and solutions presented aim at providing a general understanding of how the QoS can be guaranteed according to a given specification, even if the workload varies unpredictably. The QoS specification determines the desired QoS during normal system operation, and the worst-case system performance and convergence rate toward the desired setting in the face of transient overloads. Feedback control theory is used to control QoS since little is known about the workload applied on the system. Using feedback control the difference between the measured QoS and the desired QoS is formed and fed into a controller, which computes a change to the operation of the real-time system. Experimental evaluation shows that using feedback control is highly effective in managing QoS such that a given QoS specification is satisfied. This is a key step toward automatic management of intricate systems providing real-time data services.

This paper deals with differentiated services in real-time systems. Tasks submitted to a real-time system are differentiated with respect to importance and QoS requirements. We use feedback control to enforce the requirements in QoS and ensure a hierarchical admission policy based on the importance of the tasks. The results show that the requirements are met during steady state when the workload is constant. The feedback control approach does not satisfactorily manage QoS when there is a sudden and significant workload change (transient state) due to the time-variant nature of the system. To address this, we present preliminary and promising results using adaptive control, and report on some challenges we are facing when applying the theory.

The intricacy of real-time data service management increases mainly due to the emergence of applications operating in open and unpredictable environments, increases in software complexity, and need for performance guarantees. In this paper we propose an approach for managing the quality of service of real-time databases that provide imprecise and differentiated services, and that operate in unpredictable environments. Transactions are classified into service classes according to their level of importance. Transactions within each service class are further classified into subclasses based on their quality of service requirements. In this way transactions are explicitly differentiated according to their importance and quality of service requests. The performance evaluation shows that during overloads the most important transactions are guaranteed to meet their deadlines and that reliable quality of service is provided even in the face of varying load and execution time estimation errors.

In the control of continuous and physical systems, the controlled system is sampled sufficiently fast to capture the dynamics of the system. In general, this property cannot be applied to the control of computer systems as the measured variables are often computed over a data set, e.g., deadline miss ratio. In this paper we quantify the disturbance present in the measured variable as a function of the data set size and the sampling period, and we propose a feedback control structure that suppresses the measurement disturbance. The experiments we have carried out show that a controller using the proposed control structure outperforms a traditional control structure with regard to performance reliability.

In the control of continuous and physical systems, the controlled system is sampled sufficiently fast to capture the system dynamics. In general, this property cannot be applied to the control of computer systems as the measured variables are often computed over a data set, e.g., deadline miss ratio. In this paper we quantize the disturbance present in the measured variable as a function of the sampling period and we propose a measurement disturbance suppressive control structure. The experiments we have carried out show that a controller using the proposed control structure outperforms a traditional control structure with regard to performance reliability and adaptation.

Lately the demand for real-time data services has increased in applications where it is desirable to process user requests within their deadlines using fresh data. The real-time data services are usually provided by a real-time database (RTDB). Here, since the workload of the RTDBs cannot be precisely predicted, RTDBs can become overloaded. As a result, deadline misses and freshness violations may occur. To address this problem we propose a QoS-sensitive approach to guarantee a set of requirements on the behavior of RTDBs. Our approach is based on imprecise computation, applied on both data and transactions. We propose two algorithms to dynamically balance the workload and the quality of the data and transactions. Performance evaluations show that our algorithms give a robust and controlled behavior of RTDBs, in terms of transaction and data quality, even for transient overloads and with inaccurate run-time estimates of the transactions.

In applications such as web-applications, e-commerce, and engine control, the demand for real-time data services has increased. In these applications, requests have to be processed within their deadlines using fresh data. Since the workload of these systems cannot be precisely predicted, they can become overloaded and as a result, deadline and freshness violations may occur. To address this problem we propose a QoS-sensitive approach based on imprecise computation, applied on transactions and data objects. We propose two algorithms FCS-HEF and FCS-HEDF that give a robust and controlled behavior of RTDBs in terms of transaction and data preciseness, even for transient overloads and with inaccurate run-time estimates of the transactions. Further, performance experiments show that the proposed algorithms outperform a set of baseline algorithms including FCS-EDF, which schedules the transactions using EDF.

Real-time applications such as e-commerce, flight control, chemical and nuclear control, and telecommunication are becoming increasingly sophisticated in their data needs, resulting in greater demands for real-time data services. Since the workload of real-time databases RTDBs, providing real-time data services, cannot be precisely predicted, they can become overloaded and thereby cause temporal violations, resulting in a damage or even a catastrophe. Imprecise computation techniques address this problem and allow graceful degradation during overloads. In this paper, we present a framework consisting of a model for expressing QoS requirements in terms of data and transaction preciseness, an architecture based on feedback control scheduling, and a set of algorithms implementing different policies and behaviors. Our approach gives a robust and controlled behavior of RTDBs, even for transient overloads and with inaccurate run-time estimates of the transactions. Further, performance experiments show that the proposed algorithms outperform a set of baseline algorithms, including FCS-EDF that schedules the transactions using EDF and feedback control.

Real-time applications such as e-commerce, flight control, chemical and nuclear control, and telecommunication are becoming increasingly sophisticated in their data needs, resulting in greater demands for real-time data services that are provided by real-time databases. Since the workload of real-time databases cannot be precisely predicted, they can become overloaded and thereby cause temporal violations, resulting in damage or even a catastrophe. Imprecise computation techniques address this problem and allow graceful degradation during overloads. In this paper, we present a framework for QoS specification and management consisting of a model for expressing QoS requirements, an architecture based on feedback control scheduling, and a set of algorithms implementing different policies and behaviors. Our approach gives a robust and controlled behavior of real-time databases, even for transient overloads and with inaccurate runtime estimates of the transactions. Further, performance experiments show that the proposed algorithms outperform a set of baseline algorithms that uses feedback control.

In recent years a new class of soft real-time applications operating in unpredictable environments has emerged. Typical for these applications is that neither the resource requirements nor the arrival rates of service requests are known or available a priori. It has been shown that feedback control is very effective to support the specified performance of dynamic systems that are both resource insufficient and exhibit unpredictable workloads. To efficiently use feedback control scheduling it is necessary to have a model that adequately describes the behavior of the system. In this paper we experimentally evaluate the accuracy of four linear time-invariant models used in the design of feedback controllers. We introduce a model (DYN) that captures additional system dynamics, which a previously published model (STA) fails to include. The accuracy of the models are evaluated by validating the models with regard to measured data from the controlled system and through a set of experiments where we evaluate the performance of a set of feedback control schedulers tuned using these models. From our evaluations we conclude that second order models (e.g., DYN) are more accurate than first order models (e.g. STA). Further we show that controllers tuned using second order models perform better than controllers tuned using first order models.

In this paper we propose an architecture consisting of a particular type of node, namely a communication server that collects and aggregates data, and establishes a link between the users and the sensor nodes through satellite communication. A key challenge with satisfying a lifetime requirement of the communication server is the unpredictability of the sensor data volume arriving at the communication server and the transmission power of the satellite terminal. To provide lifetime predictability we propose an approach that automatically adjusts the quality of the data such that the specified lifetime if achieved. We have shown through an extensive evaluation that the approach manages to provide an actual lifetime within 2% of the specified lifetime despite variations in workload and communication link quality.

Updating real-time system software is often needed in response to errors and added requirements to the software. Stopping a running application, updating the software, and then restarting the application is not suitable for systems with high availability requirements. On the other hand, dynamically updating a system may increase the execution time of the tasks, thus, degrading the performance of the system. Degradation is not acceptable for performance-critical real-time systems as there are strict requirements on the performance. In this paper we present an approach that enables dynamic reconfiguration of a real-time system, where the performance of the system during a reconfiguration satisfies a given worst-case performance specification. Evaluation shows that the presented method is efficient in guaranteeing the worst-case performance of dynamically reconfigurable firm real-time systems. 

Real-time systems is a topic that one cannot overlook in an engineer's education. However, teaching real-time systems in an undergraduate syllabus is a challenging experience due to conflicting constraints placed on such a course. In this paper we present a new setup for laboratories in the real-time systems course that successfully meets the constraints of mass education, stable environment management, short time span for the labs, and still enables deep involvement of students in the central topic of resource allocation with high motivation.

The Aim of this thesis is to implement the "Opportunistic DTN Routing with Window-aware Adaptive Replication" (ORWAR) protocol on the Android platform.Delay-Tolerant Networks (DTNs) are particular mobile ad-hoc network (MANET) architectures that try to solve the issues related to the lack of point to point connectivity between the nodes of the network or between its sub-networks (partitions). The general approach is based on techniques of store-carry-forward of the messages whereby delivery can be achieved even in partitioned networks, though with mobility-dependent delays. DTNs can be considered as a means of communication for scenarios where infrastructure-based networks cannot be deployed or get dysfunctional for some reasons, such as in the case of a natural disaster or highly overloaded infrastructure. ORWAR is a DTN protocol that tries to exploit knowledge about the context of mobile nodes (speed, direction of movement and radio range) to estimate the size of a contact window in order to avoid the energy waste deriving from partial transmissions. This report presents the design and the implementation of the protocol on the Android platform. It then describes some functional tests together with an analysis of the energy consumption and the performance reachable on our test device Android Development Phone 1.

This thesis is concerned with exploring methods for making computing systems more resilient to problems in the network communication, both in the setting of existing infrastructure but also in the case where no infrastructure is available. Specifically, we target a situation called network partitions which means that a computer or device network is split in two or more parts that cannot communicate with each other.

The first of the two tracks in the thesis is concerned with upholding system availability during a network partition even when there are integrity constraints on data. This means that the system will optimistically accept requests since it is impossible to coordinate nodes that have no means of communicating during finite intervals; thus requiring a reconciliation process to take place once the network is healed.

We provide several different algorithms for reconciling divergent states of the nodes, one of which is able to allow the system to continue accepting operations during the reconciliation phase as opposed to having to stop all invocations.  The algorithms are evaluated analytically, proving correctness and the conditions for termination.  The performance of the algorithms has been analysed using simulations and as a middleware plugin in an emulated setting.

The second track considers more extreme conditions where the network is partitioned by its nature. The nodes move around in an area and opportunistically exchange messages with nodes that they meet. This as a model of the situation in a disaster area where the telecommunication networks are disabled. This scenario poses a number of challenges where protocols need to be both partition-tolerant and energy-efficient to handle node mobility, while still providing good delivery and latency properties.

We analyse worst-case latency for message dissemination in such intermittently connected networks. Since the analysis is highly dependent on the mobility of the nodes, we provide a model for characterising connectivity of dynamic networks. This model captures in an abstract way how fast a protocol can spread a message in such a setting. We show how this model can be derived analytically as well as from actual trace files.

Finally, we introduce a manycast protocol suited for disaster area networks. This protocol has been evaluated using simulations which shows that it provides very good performance under the circumstances, and it has been implemented as a proof-of-concept on real hardware.

The software industry is facing a great challenge. While systems get more complex and distributed across the world, users are becoming more dependent on their availability. As systems increase in size and complexity so does the risk that some part will fail. Unfortunately, it has proven hard to tackle faults in distributed systems without a rigorous approach. Therefore, it is crucial that the scientific community can provide answers to how distributed computer systems can continue functioning despite faults.

Our contribution in this thesis is regarding a special class of faults which occurs whennetwork links fail in such a way that parts of the network become isolated, such faults are termed network partitions. We consider the problem of how systems that have integrity constraints on data can continue operating in presence of a network partition. Such a system must act optimistically while the network is split and then perform a some kind of reconciliation to restore consistency afterwards.

We have formally described four reconciliation algorithms and proven them correct. The novelty of these algorithms lies in the fact that they can restore consistency after network partitions in a system with integrity constraints and that one of the protocols allows the system to provide service during the reconciliation. We have implemented and evaluated the algorithms using simulation and as part of a partition-tolerant CORBA middleware. The results indicate that it pays off to act optimistically and that it is worthwhile to provide service during reconciliation.

In search and rescue scenarios local information on victims and other finds needs to be disseminated rapidly toother rescue workers and team leaders. However, post disaster scenarios may imply the collapse of informationinfrastructure including cellular communication and Internet connectivity. Even if we consider wireless ad hoccommunication as a means of information dissemination we should count on frequent loss of connectivity in thenetwork due to unpredictable mobility and sparse network topologies. In this paper we present the realization ofan existing manycast protocol (random walk gossip) on commodity handheld devices running the Androidplatform. This communication mode is used to demonstrate the potential for distributed informationdissemination on victims and finds. The application layer is an adaptation of an existing surveying informationtool (POSIT) which is now fully decentralized and relies on text communication to achieve energy efficiency.

Information dissemination in disaster scenarios requires timely and energy-efficient communication in intermittently connected networks. When the existing infrastructure is damaged or overloaded, we suggest the use of a manycast algorithm that runs over a wireless mobile ad hoc network, and overcomes partitions using a store-and-forward mechanism. This paper presents a random walk gossip protocol that uses an efficient data structure to keep track of already informed nodes with minimal signalling. Avoiding unnecessary transmissions also makes it less prone to overloads. Experimental evaluation shows higher delivery ratio, lower latency, and lower overhead compared to a recently published algorithm.

This book brings together 19 papers focusing on the application of rigorous design techniques to the development of fault-tolerant, software-based systems. It is an outcome of the REFT 2005 Workshop on Rigorous Engineering of Fault-Tolerant Systems held in conjunction with the Formal Methods 2005 conference at Newcastle upon Tyne, UK, in July 2005.

This paper addresses design exploration for protocols that are employed in systems with availability-consistency trade-offs. Distributed data is modelled as states of objects replicated across a network, and whose updates require satisfaction of integrity constraints over multiple objects. Upon detection of a partition, such a network will continue to provide delivery of services in parallel partitions; but only for updates with non-critical integrity constraints. Once the degraded mode ends, the parallel network partitions are reconciled to arrive at one partition. Using a formal treatment of the reconciliation process, three algorithms are proposed and studied in terms of their influence on service outage duration. The longer the reconciliation time, the lower is system availability; since the interval in which no services are provided is longer. However, the reconciliation time in turn is affected by the time to construct the post-partition system state. The shorter the construction time the higher is the number of updates that took place in the degraded mode but that will not be taken up in the reconciled partition. This will lead to a longer interval for rejecting/redoing these operations and thereby increase reconciliation time.

Replicated systems that run over partitionable environments, can exhibit increased availability if isolated partitions are allowed to optimistically continue their execution independently. This availability gain is traded against consistency, since several replicas of the same objects could be updated separately. Once partitioning terminates, divergences in the replicated state needs to be reconciled. One way to reconcile the state consists of letting the application manually solve inconsistencies. However, there are several situations where automatic reconciliation of the replicated state is meaningful. We have implemented replication and automatic reconciliation protocols that can be used as building blocks in a partition-tolerant middleware. The novelty of the protocols is the continuous service of the application even during the reconciliation process. A prototype system is experimentally evaluated to illustrate the increased availability despite network partitions.

  In this paper we describe how to include high level semantic information, such as aesthetics and emotions; into Content Based Image Retrieval. We present a, color-based emotion-related image descriptor that can be used for describing the emotional content of images. The color emotion metric used is derived from psychophysical experiments rind based oil three variables: activity, weight and teat. It was originally designed for single-colors, bill, recent research has shown that the salve emotion estimates call be applied in the retrieval of multi-colored images. Here we describe a new approach, based oil the assumption that perceived color emotions in images are mainly affected by homogenous regions, defined by the emotion metric; and transitions between regions. RGB coordinates are converted to emotion coordinates, mid for each emotion channel, statistical measurements of gradient magnitudes within a. stack of low-pass filtered images are used for finding interest; points corresponding to homogeneous regions and transitions between regions. Emotion characteristics are derived for patches surrounding cacti interest, point, and saved in a, bag-of-emotions; that for instance, can be used for retrieving images based oil emotional content.

Replicated distributed object systems are deployed to provide timely and reliable services to actors at distributed locations. This paper treats applications in which data updates are dependent on satisfaction of integrity constraints over multiple objects. Network partitions, caused by occasional link failures, overload or attacks create problems in keeping both consistency and availability in such networks. We propose a means of achieving higher availability by providing partition-awareness in middleware. The general approach has been illustrated by implementing a number of CORBA extensions that trade consistency for availability during network partitions. This paper contains a thorough experimental evaluation that presents the gains and costs of our approach. The experiments clearly illustrate the benefit of our protocols in terms of significantly higher availability and the number of performed operations.

Energy economy in mobile devices is becoming an increasinglyimportant factor as the devices become more advancedand rich in features. A large part of the energy footprint of amobile device comes from the wireless communication module,and even more so as the amount of trac increases.In this paper we study the energy footprint of a mobilebroadband hardware module, and how it is aected by software,by performing systematic power consumption measurements.We show that there are several cases where thesoftware does not properly take into account the eect thatdata communication has on the power consumption. Thisopens up for potential energy savings by creating better applicationsthat are aware of the energy characteristics of thecommunication layer.

Anomaly detection, detection of deviations from what is considered normal, is an important complement to misuse detection based on attack signatures. Anomaly detection in real-time places hard requirements on the algorithms used, making many proposed data mining techniques less suitable. ADWICE (Anomaly Detection With fast Incremental Clustering) uses the first phase of the existing BIRCH clustering framework to implement fast, scalable and adaptive anomaly detection. We extend the original clustering algorithm and apply the resulting detection mechanism for analysis of data from IP networks. The performance is demonstrated on the KDD data set as well as on data from a test network at a telecom company. Our experiments show a good detection quality (95 %) and acceptable false positives rate (2.8 %) considering the online, real-time characteristics of the algorithm. The number of alarms is then further reduced by application of the aggregation techniques implemented in the Safeguard architecture.

Malware in smartphones is growing at a significant rate. There are currently more than 250 million smartphone users in the world and this number is expected to grow in coming years.

 In the past few years, smartphones have evolved from simple mobile phones into sophisticated computers. This evolution has enabled smartphone users to access and browse the Internet, to receive and send emails, SMS and MMS messages and to connect devices in order to exchange information. All of these features make the smartphone a useful tool in our daily lives, but at the same time they render it more vulnerable to attacks by malicious applications.

 Given that most users store sensitive information on their mobile phones, such as phone numbers, SMS messages, emails, pictures and videos, smartphones are a very appealing target for attackers and malware developers.

The need to maintain security and data confidentiality on the Android platform makes the analysis of malware on this platform an urgent issue.

 We have based this report on previous approaches to the dynamic analysis of application behavior, and have adapted one approach in order to detect malware on the Android platform. The detector is embedded in a framework to collect traces from a number of real users and is based on crowdsourcing. Our framework has been tested by analyzing data collected at the central server using two types of data sets: data from artificial malware created for test purposes and data from real malware found in the wild. The method used is shown to be an effective means of isolating malware and alerting users of downloaded malware, which suggests that it has great potential for helping to stop the spread of detected malware to a larger community. 

This thesis project shows that it is feasible to create an Android malware detection system with satisfactory results. 

 branch of green networking research is consoli- dating. It aims at routing traffic with the goal of reducing the network energy consumption. It is usually referred to as Energy- Aware Routing. Previous works in this branch only focused on pure IP networks, e.g., assuming an Open Shortest Path First (OSPF) control plane, and best effort packet forwarding on the data plane. In this work, we consider instead Generalized Multi- Protocol Label Switching (GMPLS) backbone networks, where optical technologies allow to design “circuit switching” network management policies with strict bandwidth reservation policies.

We define a simple and generic framework which generates a family of routing algorithms, based on an energy-aware weight assignment. In particular, routing weights are functions of both the energy consumption and the actual load of network devices. Using such weights, a simple minimum-cost routing allows finding the current least expensive circuit, minimising the additional energy cost. Results obtained on realistic case studies show that our weight assignment policy favours a consistent reduction of the network power consumption, without significantly affecting the network performance. Furthermore, the framework allows to trade energy efficiently and network performance, a desirable property at which ISPs are looking for. Simple and robust parameter settings allow reaching a win-win situation, with excellent performance in terms of both energy efficiency and network resource utilization. 

From the first steps of the mobile agent technology, the main concerns have been its security and interoperability. At the contrary, its performance has been usually relegated to a second place. The main contribution of this article is the proposal of a new agent transfer protocol, called Fragment Transfer Protocol (FrTP), for the Inter-Platform Mobility Architecture (IPMA) that improves the agent migration performance. The new protocol has been designed because a poor agent migration performance is observed in some Agent Middlewares, such as JADE, when large sized code and data agents are transferred. The reason is that the existing IPMA protocols encapsulate too much data in a single IEEE-FIPA ACL message and these Agent Middlewares do not deal well with this situation. Therefore, FrTP proposes to transfer the agent by sending its code and data split into several messages. The new protocol approach is fully compliant with the IEEE-FIPA interoperability agent standards and IPMA framework. Furthermore, it has been integrated into the IPMA implementation for JADE and it has been extensively validated through a set of performance tests carried out on different scenarios. Hence, its usage will strongly improve the performance of agents with large sized codes or data.

One of the most challenging applications of wireless networking are in disaster area networks where lack of infrastructure, limited energy resources, need for common operational picture and thereby reliable dissemination are prevalent.In this paper we address anomaly detection in intermittently connected mobile ad hoc networks in which there is little or no knowledge about the actors on the scene, and opportunistic contacts together with a store-and-forward mechanism are used to overcome temporary partitions. The approach uses a statistical method for detecting anomalies when running a manycast protocol for dissemination of important messages to k receivers. Simulation of the random walk gossip (RWG) protocol combined with detection and mitigation mechanisms is used to illustrate that resilience can be built into a network in a fully distributed and attack-agnostic manner, at a modest cost in terms of drop in delivery ratio and additional transmissions. The approach is evaluated with attacks by adversaries that behave in a similar manner to fair nodes when invoking protocol actions.

This paper proposes a scheme for bandwidth allocation in wireless ad hoc networks. The quality-of-service (QoS) levels for each end-to-end flow are expressed using a resource-utility function, and our algorithms aim to maximize aggregated utility. The shared channel is modeled as a bandwidth resource defined by maximal cliques of mutual interfering links. We propose a novel resource allocation algorithm that employs an auction mechanism in which flows are bidding for resources. The bids depend both on the flow's utility function and the intrinsically derived shadow prices. We then combine the admission control scheme with a utility-aware on-demand shortest path routing algorithm where shadow prices are used as a natural distance metric. As a baseline for evaluation, we show that the problem can be formulated as a linear programming (LP) problem. Thus, we can compare the performance of our distributed scheme to the centralized LP solution, registering results very close to the optimum. Next, we isolate the performance of price-based routing and show its advantages in hotspot scenarios, and also propose an asynchronous version that is more feasible for ad hoc environments. Further experimental evaluation compares our scheme with the state of the art derived from Kelly's utility maximization framework and shows that our approach exhibits superior performance for networks with increased mobility or less frequent allocations. © 2008 IEEE.

Wireless communication networks are facing a paradigm shift. From providing only voice communication, new generations of wireless networks are designed to provide different types of multimedia communications together with different types of data services and aim to seamlessly integrate in the big Internet infrastructure. Some of these applications and services have strong resource requirements in order to function properly (e.g. videoconferences), others are flexible enough to adapt to whatever is available (e.g. FTP). Also, different services (or different users), might have different importance levels, and should be treated accordingly. Providing resource assurance and differentiation is often referred to as quality of service (QoS). Moreover, due to the constrained and fluctuating bandwidth of the wireless link, and user mobility, wireless networks represent a class of distributed systems with a higher degree of unpredictability and dynamic change as compared to their wireline counterparts.

In this thesis we study how novel resource allocation algorithms can improve the behaviour (the offered QoS) of dynamic unpredictable distributed systems, such as a wireless network, during periods of overload. This work concerns both low level enforcement mechanisms and high-level policy dependent optimisation algorithms.

First, we propose and evaluate adaptive admission control algorithms for controlling the load on a processor in a radio network controller. We use feedback mechanisms inspired by automatic control techniques to prevent CPU overload, and policy-dependent deterministic algorithms to provide service differentiation.

Second, we propose and evaluate a QoS-aware bandwidth admission control and allocation algorithm for the radio link in a network cell. The acceptable quality levels for a connection are specified using bandwidth dependent utility functions, and our scheme aims to maximise system-wide utility. The novelty in our approach is that we take into account bandwidth reallocation, which arise as a consequence of the dynamic environment, and their effects on the accumulated utility of the different connections.  

From providing only voice communications, wireless networks aim to provide a wide range of services in which soft real-time, high priority critical data, and best effort connections seamlessly integrate. Some of these applications and services have firm resource requirements in order to function properly (e.g. videoconferences), others are flexible enough to adapt to whatever is available (e.g. FTP). Providing differentiation and resource assurance is often referred to as providing quality of service (QoS). In this thesis we study how novel resource allocation algorithms can improve the offered QoS of dynamic, unpredictable, and resource constrained distributed systems, such as a wireless network, during periods of overload.

We propose and evaluate several bandwidth allocation schemes in the context of cellular, hybrid and pure ad hoc networks. Acceptable quality levels for a connection are specified using resource-utility functions, and our allocation aims to maximise accumulated systemwide utility. To keep allocation optimal in this changing environment, we need to periodically reallocate resources. The novelty of our approach is that we have augmented the utility function model by identifying and classifying the way reallocations affect the utility of different application classes. We modify the initial utility functions at runtime, such that connections become comparable regardless of their flexibility to reallocations or age-related importance.

Another contribution is a combined utility/price-based bandwidth allocation and routing scheme for ad hoc networks. First we cast the problem of utility maximisation in a linear programming form. Then we propose a novel distributed allocation algorithm, where every flow bids for resources on the end-to-end path depending on the resource ``shadow price'', and the flow's ``utility efficiency''. Our periodic (re)allocation algorithms represent an iterative process that both adapts to changes in the network, and recalculates and improves the estimation of resource shadow prices.

Finally, problems connected to allocation optimisation, such as modelling non-critical resources as costs, or using feedback to adapt to uncertainties in resource usage and availability, are addressed.

This paper proposes a scheme for bandwidth allocation in wireless ad hoc networks. The Quality of Service (QoS) levels for each end-to-end flow are expressed using resource-utility functions, and our algorithms aim to maximise the aggregated utility of the flows. The scheme differentiates between applications with flexible resource requirements and rigid (real-time) requirements. As an abstract notion of resource, we use maximal cliques of mutual interfering links. Using concave piece-wise linear utility functions we present a linear programming (LP) formulation of the problem that can serve as an optimal though unrealistic solution. Then we replace this centralised approach with a distributed low complexity solution. A key concept, borrowed from the dual of the optimal allocation problem, is the shadow price of a resource. The contributions of the paper are twofold: (1) a distributed algorithm that allocates the bandwidth based on bids that are calculated using the shadow price of the resources and the flows utility function, (2) a utility-aware on-demand shortest path routing algorithm in which the shadow prices are used a natural distance metric. We compare the performance of the distributed allocation scheme with the centralised, optimal linear programming solution. We also compare with a non-utility-based QoS allocation scheme, that uses hop-based shortest path routing followed by highest possible bandwidth accommodation of the flow.

This paper presents a time-aware admission control and resource allocation scheme in the context of a future generation mobile network. The quality levels (and their respective utility) of the different connections are specified using discrete resource-utility (R-U) functions. The scheme uses these R-U functions for allocating and reallocating bandwidth to connections, aiming to maximise the accumulated utility of the system. However, different applications react differently to resource reallocations. Therefore at each allocation timepoint we take into account the following factors: the age of the connection, a drop (disconnection) penalty and the sensitiveness to reallocation frequency. Finally, we show the superior performance of our approach compared to a recent adaptive bandwidth allocation scheme.

This paper presents a time-aware admission control and resource allocation scheme in wireless networks in the context of a future generation cellular network. The quality levels (and their respective utility) of different connections are specified using discrete resource-utility (R-U) functions. The scheme uses these R-U functions for allocating and reallocating bandwidth to connections, aiming to maximize the accumulated utility of the system. However, different applications react differently to resource reallocations. Therefore, at each allocation time point, the following factors are taken into account: the age of the connection, a disconnection (drop) penalty, and the sensitiveness to reallocation frequency. The evaluation of our approach shows a superior performance compared to a recent adaptive bandwidth allocation scheme (RBBS). In addition, we have studied the overhead that performing a reallocation imposes on the infrastructure. To minimize this overhead, we present an algorithm that efficiently reduces the number of reallocations while remaining within a given utility bound.

Service availability in wireless networks is highly dependent on efficient resource allocation and guaranteed Quality of Service (QoS) amid overloads and failures. This paper addresses optimal bandwidth allocation in a hybrid network (cellular and ad hoc), where added reach through an ad hoc overlay is combined with the stability and essential services of a cellular network. The paper builds on a near optimal approach in which Resource-Utility functions are used as a means of adaptive delivery of QoS, user differentiation, and maximisation of system level utility. It distinguishes between non-adaptive, semi-adaptive, and fully adaptive applications. First, the global cellular bandwidth allocation (in the presence of multiple routes through ad hoc relays) is cast in terms of a Linear Programming problem. Second, a heuristic algorithm that has far lower computational overhead and accrues at worse 12% less than the utility of the optimal solution is presented. Both algorithms are implemented within a model of a hybrid network on top of the Jsim simulation environment. Comparative tudies are made to show effective load balancing and crash tolerance in the presence of a high traffic overload.

With the increasing complexity in software and electronics in safety-critical systems new challenges to lower the costs and decrease time-to-market, while preserving high assurance have emerged. During the safety assessment process, the goal is to minimize the risk and particular, the impact of probable faults on system level safety. Every potential fault must be identified and analysed in order to determine which faults that are most important to focus on. In this paper, we extend our earlier work on formal qualitative analysis with a quantitative analysis of fault tolerance. Our analysis is based on design models of the system under construction. It further builds on formal models of faults that have been extended for estimated occurence probability allowing to analyse the system-level failure probability. This is done with the help of the probabilistic model checker PRISM. The extension provides an improvement in the costly process of certification in which all forseen faults have to be evaluated with respect to their impact on safety and reliability. We demonstrate our approach using an application from the avionic industry: an Altitude Meter System.

Abstraction is the most basic principle of software engineering. Abstractions are provided by models. Modeling and model transformation constitute the core of model-driven development. Models can be refined and finally be transformed into a technical implementation, i.e., a software system.

The aim of this book is to give an overview of the state of the art in model-driven software development. Achievements are considered from a conceptual point of view in the first part, while the second part describes technical advances and infrastructures. Finally, the third part summarizes experiences gained in actual projects employing model-driven development.

Beydeda, Book and Gruhn put together the results from leading researchers in this area, both from industry and academia. The result is a collection of papers which gives both researchers and graduate students a comprehensive overview of current research issues and industrial forefront practice, as promoted by OMG’s MDA initiative.

Failure mode and effects analysis (FMEA) is a well-known technique widely used for safety assessment in the area of safety-critical systems. However, FMEA is traditionally done manually which makes it both time-consuming and costly, specially for large and complex systems. Also, small modifications in the design may result in a complete revision of the initial FMEA. This paper presents a tool support for automated incremental component-based FMEA of SW and HW. It is based on component safety interfaces and a formal compositional safety analysis method. This tool support enables engineers to focus on more important steps in the safety assessment process. Also, during system upgrades, the tool incrementally registers the changes and identifies possible effects in the FMEA which enables the use of earlier safety analysis results. Finally, this formal approach based on design models of the components and the system always creates FMEAs which are consistent with the system design.