Tech Reports in Computer Science and Engineering

Permanent URI for this communityhttp://hdl.handle.net/1903/5

The technical reports collections in this community are deposited by the Library of the Computer Science department. If you have questions about these collections, please contact library staff at library@cs.umd.edu

Browse

Now showing 1 - 20 of 20

An Accurate Time-Management Unit for Real-Time Processors
(1998-10-15) Kailas, Krishnan K.; Agrawala, Ashok K.
Time management is an important aspect of real-time computation. Traditional high performance processors provide little or no support for management of time. In this report, we propose a time-management unit which can greatly help improve the performance of a real-time system. The proposed unit can be added to any processor architecture without affecting its performance. We also explain how the unit helps to solve the clock synchronization problems in a real-time network. (Also cross-referenced as UMIACS-TR-97-28)
AD (Attacker Defender) Game
(2002-01-31) Kochut, Andrzej; Agrawala, Ashok K.; Larsen, Ronald L.; Shankar, A. Udaya
Information Dynamics is a framework for agent-based systems that gives a central position to the role of information, time, and the value of information. We illustrate system design in the Information Dynamics Framework by developing an intelligence game called AD involving attackers, defenders and targets operating in some space of locations. The goal of the attackers is to destroy all targets. Target destruction takes place when the number of attackers in the target's neighborhood exceeds the number of defenders in this neighborhood by a value WINNING_DIFFERENCE. The goal of defenders is to prevent attackers from achieving their goal. (Also UMIACS-TR-2001-45)
Allocation and Scheduling of Real-Time Periodic Tasks with Relative Timing Constraints
(1998-10-15) Cheng, Sheng-Tzong; Agrawala, Ashok K.
Allocation problem has always been one of the fundamental issues of building the applications in distributed computing systems (DCS). For real-time applications on DCS, the allocation problem should directly address the issues of task and communication scheduling. In this context, the allocation of tasks has to fully utilize the available processors and the scheduling of tasks has to meet the specified timing constraints. Clearly, the execution of tasks under the allocation and schedule has to satisfy the precedence, resources, and other synchronization constraints among them. Recently, the timing requirements of the real-time systems emerge that the relative timing constraints are imposed on the consecutive executions of each task and the inter-task temporal relationships are specified across task periods. In this paper we consider the allocation and scheduling problem of the periodic tasks with such timing requirements. Given a set of periodic tasks, we consider the least common multiple (LCM) of the task periods. Each task is extended to several instances within the LCM. The scheduling window for each task instance is derived to satisfy the timing constraints. We develop a simulated annealing algorithm as the overall control algorithm. An example problem of the sanitized version of the Boeing 777 Aircraft Information Management System is solved by the algorithm. Experimental results show that the algorithm solves the problem in a reasonable time complexity. (Also cross-referenced as UMIACS-TR-95-6)
The Challenges of Real-Time AI
(1998-10-15) Musliner, David John; Hendler, James; Agrawala, Ashok K.; Durfee, Edmund H.; Strosnider, Jay K.; Paul, C. J.
The research agendas of two major areas of computer science are converging: Artificial Intelligence (AI) methods are moving towards more realistic domains requiring real-time responses, and real-time systems are moving towards more complex applications requiring intelligent behavior. Together, they meet at the crossroads of interest in "real-time intelligent control," or "real-time AI." This subfield is still being defined by the common interests of researchers from both real-time and AI systems. As a result, the precise goals for various real-time AI systems are still in flux. This paper describes an organizing conceptual structure for current real-time AI research, clarifying the different meanings this term has acquired for various researchers. Having identified the various goals of real-time AI research, we then specify some of the necessary steps towards reaching those goals. This in turn enables us to identify promising areas for future research in both AI and real-time systems techniques. (Also cross-referenced as UMIACS-TR-94-69)
Design & Performance Study of a Flexible Traffic Shaper for High Speed Networks
(1998-10-15) Radhakrishnan, S.; Raghavan, S. V.; Agrawala, Ashok K.
In networks supporting distributed multimedia, maximizing bandwidth utilization and providing performance guarantees are two incompatible goals. Heterogeneity of the multimedia sources calls for effective congestion control schemes to satisfy the diverse Quality of Service (QoS) requirements of each application. These include admission control at connection set up, traffic control at the source ends and efficient scheduling schemes at the switches. The emphasis in this paper is on traffic control at the source ends. Traffic control schemes have two functional roles. One is traffic enforcement as a supplement to the admission control policy. The other is shaping the input traffic so that it becomes amenable to the scheduling mechanism at the switches for providing the required QoS guarantees. Studies on bursty sources have shown that burstiness promotes statistical multiplexing at the cost of possible congestion. Smoothing the traffic helps in providing guarantees at the cost o f bandwidth utilization. The need for a flexible scheme which can provide a reasonable compromise between the utilization and guarantees is imminent. We present the design and performance study of a flexible traffic shaper which can adjust the burstiness of input traffic to obtain reasonable utilization while maintaining statistical service guarantees. The performance of the traffic shaper for bursty sources is studied using simulation. (Also cross-referenced as UMIACS-TR-95-72)
Designing Dynamic Temporal Controls for Critical Systems
(1998-10-15) Choi, Seonho; Agrawala, Ashok K.; Shi, Leyuan
Traditional control systems have been designed to exercise control at regularly spaced time instants. When a discrete version of the system dynamics is used, a constant sampling interval is assumed and a new control value is calculated and exercised at each time instant. In this paper, we propose a new control scheme, {\it dynamic temporal control}, in which we not only calculate the control value but also dynamically decide the time instants when the new control computations have to be calculated. Taking a discrete, linear, time-invariant system, and a cost function which reflects a cost for computation of the control values, as an example, we show the feasibility of using this scheme. We implement the dynamic temporal control scheme in a rigid body satellite control example and demonstrate the significant reduction in cost. The scheme proposed here can be implemented using real-time operating system, such as {\em Maruti}, which schedules activities along the time axis. The reduced computations for control permit the use of the same processor for higher level functions resulting in a significant improvement in the performance of the overall system. (Also cross-referenced as UMIACS-TR-97-51)
Designing Temporal Controls
(1998-10-15) Agrawala, Ashok K.; Choi, Seonho; Shi, Leyuan
Traditional control systems have been designed to exercise control at regularly spaced time instants. When a discrete version of the system dynamics is used, a constant sampling interval is assumed and a new control value is calculated and exercised at each time instant. In this paper we formulate a new control scheme, {\it temporal control}, in which we not only calculate the control value but also decide the time instants when the new values are to be used. Taking a discrete, linear, time-invariant system, and a cost function which reflects a cost for computation of the control values, as an example, we show the feasibility of using this scheme. We formulate the temporal control scheme as a feedback scheme and, through a numerical example, demonstrate the significant reduction in cost through the use of temporal control. (Also cross-referenced as UMIACS-TR-95-81)
Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Constraints
(1998-10-15) Choi, Seonho; Agrawala, Ashok K.
In some hard real-time systems, relative timing constraints may be imposed on task executions, in addition to the release time and deadline constraints. A periodic task may have jitter constraints between the start or finish times of any two consecutive executions. Relative constraints such as separation or relative deadline constraints may be given between start or finish times of tasks (4). One approach is to find a total order on a set of n jobs in a scheduling window, and cyclically use this order at run time to execute the jobs. However, in the presence of the relative constraints, if the job execution times are nondeterminiistic with defined lower and upper bound, it is not always possible to statically assign start times at pre-runtime without sacrificing the schedulability(4). We develop a technique called dynamic cyclic dispatching to enforce relative constraints along with release time and deadline constraints. An ordered set of N jobs is assumed to be given within a scheduling window and this schedule (ordering) is cyclically repeated at runtime. An off-line algorithm is presented to check the schedulability of the job set and to obtain parametric lower and upper bounds on the start times of jobs, if the job set is schedulable. Then, these parametric bounds are evaluated at runtime to obtain a valid time intervals during which jobs can be started. The complexity of this off-line component is shown to be O(n2N3) where n is the number of jobs in a scheduling window that have relative constraints with jobs in the next scheduling window. An online algorithm can evaluate these bounds in O(N3+n5) computation time. Unlike static approached which assign fixed start times to jobs in the scheduling window, our approach not only allows us to flexibly manage the slack times with the schedulability of a task set not affected, but also yields a guaranteed schedulability in the sense that, if other dispatching mechanism can schedule the job sequences satisfying all given constraints, then our mechanism can also schedule them. (Also cross-referenced as UMIACS-TR-97-300
A Flexible Traffic Shaper for High Speed Networks: Design and Comparative Study with Leaky Bucket
(1998-10-15) Radhakrishnan, S.; Raghavan, S. V.; Agrawala, Ashok K.
Maximizing bandwidth utilization and providing performance guarantees, in the context of multimedia networking, are two incompatible goals. Heterogeneity of the multimedia sources calls for effective traffic control schemes to satisfy their diverse Quality of Service (QoS) requiremnets. These include admission control at connection set up, traffic control at the source ends and efficient scheduling schemes at the switches. The emphasis in this paper is on traffic control at the source end. Most multimedia sources are bursty in nature. Traffic shapers have been mainly studied hitherto from the point of view of their effectiveness in smoothing the burstiness. Leaky Bucket (LB) scheme, to cite an example, is a mean rate policer smoothing at the token generation rate. Studies on bursty sources show that burstiness promotes statistical multiplexing at the cost of possible congestion. Smoothing, on the other hand, helps in providing guarantees at the cost of utilization. Thus need for a flexible scheme which can provide a reasonable compromise between utilization and performance is imminent. Recent studies [10, 12] have also questioned the suitability of LB for policing real-time traffic due to the excessive delays. We argue for a policy which is less stringenton short term burstiness than the LB. We propose a new traffic shaper which can adjust the burstiness of the input traffic to obtain reasonable bandwidth utilization while maintaining statistical service guarantees. The performance study is conducted in two parts. In the first part, we study the effect of varying the shaper parameters on the input characteristics. In the second part, we dimension our scheme and a LB equivalently and compare the mean and peak rate policing behavior with delay and loss as the performance parameters. Adopting a less stringent attitude towards short term burstiness is shown to result in considerable advantage while policing real-time traffic. Future research possibilities in this topic are explored. (Also cross-referenced as UMIACS-TR-95-71)
A Generic Architecture for Programmable Traffic Shaper for High Speed Networks
(1998-10-15) Kailas, Krishnan K.; Agrawala, Ashok K.; Raghavan, S. V.
Traffic shapers by preventing congestion and smoothing the traffic, play an important role in realizing the traffic control schemes employed in high speed networks to ensure the Quality of Service (QoS) requirements of the application. In this report, we present a generic architecture for programmable traffic shaper for high speed networks. The programmability of the proposed architecture is illustrated by implementing some of the existing traffic shaping schemes. The architectural design issues of the proposed scheme are described and discussed. (Also cross-referenced as UMIACS-TR-95-75)
Information Dynamics Applied to Link-State Routing
(2002-01-31) Eom, Hyeonsang; Agrawala, Ashok K.; Noh, Sam H.; Shankar, A. Udaya
Information Dynamics is an information-centric framework that provides a sufficient understanding of the characteristics of information used in systems for better system design and implementation. In this paper, we describe how to improve link-state routing based on this framework. Link-state routing protocols such as OSPF (Open Shortest Path First) are currently used in many networks. In link-state routing, routes are determined based on link-delay estimates, which are periodically flooded throughout the network. This flooding of link-delay estimates is done without considering the relevance of these estimates to routing quality, i.e. without taking into account the usefulness of the link-delay information. We have developed a new approach that improves link-state routing by estimating future link delays and flooding these estimates only to the extent that they are relevant. This means that we consider the dynamics of the link-delay information and its usefulness. Simulation studies suggest that our approach can lead to significant reductions in routing traffic with noticeable improvements of routing quality in high-load conditions, demonstrating the effectiveness of the framework. We plan to further investigate the conditions where our information-dynamics approach is better than the standard approach. (Also UMIACS-TR-2001-75)
Information Dynamics: An Information-Centric Approach to System Design"
(2000-05-17) Agrawala, Ashok K.; Larsen, Ronald L.; Szajda, Douglas
Acquisition, distribution, management, and analysis of information are the fundamental purposes behind most complex constructed systems and infrastructures, and yet a process centric approach is fundamental to the design and implementation of such systems. Since information is the essential commodity in these endeavors, we believe that an effective design should take into account the fundamental properties of information: it's characteristics, its fusion, its distillation, etc. Information Dynamics is an attempt to bring a degree of rigor to the understanding of the nature of information itself and how it is used in pursuit of system objectives. (Also cross-referenced as UMIACS-2000-08)
NetDyn Revisited: A Replicated Study of Network Dynamics
(1998-10-15) Pointek, Julie; Shull, Forrest; Tesoriero, Roseanne; Agrawala, Ashok K.
In 1992 and 1993, a series of experiments using the NetDyn tool was run at the University of Maryland to characterize network behavior. These studies identified multiple design and implementation faults in the Internet. Since that time, there has been a wide array of changes to the Internet. During the Spring of 1996, we conducted a replication of the NetDyn experiments in order to characterize end-to-end behavior in the current environment. In this paper, we present and discuss the latest results obtained during this study. Although the network seems to be stabilizing with respect to transit times, our current results are similar to the results from past experiments. That is, networks often exhibit unexpected behavior. The data suggest that while there has been improvement, there are still problem areas that need to be addressed. (Also cross-referenced as UMIACS-TR-96-69)
Notes on Symbol Dynamics
(1998-10-15) Agrawala, Ashok K.; Landauer, Christopher
This paper introduces a new formulation of dynamic systems that subsumes both the classical discrete snd differential equation models as well as current trends in hybrid models. The key idea is to express the system dynamics using symbols to which the notion of time is explicitly attached. The state of the system is described using symbols which are active for a defined period of time. The system dynamics is then represented as relations between the symbolic representations . We describe the notation and give several examples of its use. (Also cross-referenced as UMIACS-TR-95-15)
Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications
(1998-10-15) Cheng, Sheng-Tzong; Agrawala, Ashok K.
We consider the replication problem of series-parallel (SP) task graphs where each task may run on more than one processor. The objective of the problem is to minimize the total cost of task execution and interprocessor communication. We call it, the minimum cost replication problem for SP graphs (MCRP-SP). In this paper, we adopt a new communication model where the purpose of replication is to reduce the total cost. The class of applications we consider is computation-intensive applications in which the execution cost of a task is greater than its communication cost. The complexity of MCRP-SP for such applications is proved to be NP-complete. We present a branch-and-bound method to find an optimal solution as well as an approximation approach for suboptimal solution. The numerical results show that such replication may lead to a lower cost than the optimal assignment problem (in which each task is assigned to only one processor) does. The proposed optimal solution has the complexity of O(n22nM), while the approximation solution has O(n4M2), where n is the number of processors in the system and M is the number of tasks in the graph. (Also cross-referenced as UMIACS-TR-93-4.1)
Real-time Communication
(1998-10-15) Cilingiroglu, Ardas; Lee, Sung; Agrawala, Ashok K.
Recent advances in networking technology has enabled new multimedia and process control applications. These applications require real-time communication services with stringent performance guarantees expressed in terms of delay, delay jitter, throughput and loss rate. Current network architectures and protocols are designed to support best-effort services and they are inefficient in supporting real-time services. In this paper, we survey real-time communication architectures and protocols both in packet-switching networks and in multiple-access networks. For each network a service model is presented as a general framework. Specifically, the service model for a packet-switching network is composed of a specification for traffic characterization and performance requirements, a routing protocol, a resource reservation protocol and a packet service discipline at switching nodes. The model for a multiple-access network, on the other hand, includes a basic traffic characterization and a MAC-layer real-time scheduling algorithm. This paper surveys the recent developments in each component of the service models with comparisons of alternative techniques. (Also cross-referenced as UMIACS-TR-97-04)
Scheduling Aperiodic and Sporadic Tasks in Hard Real-Time Systems
(1998-10-15) Choi, Seonho; Agrawala, Ashok K.
The stringent timing constraints as well as the functional correctness are essential requirements of hard real-time systems. In such systems, scheduling plays a very important role in satisfying these constraints. The priority based scheduling schemes have been used commonly due to the simplicity of the scheduling algorithm. However, in the presence of task interdependencies and complex timing constraints, such scheduling schemes may not be appropriate due to the lack of an efficient mechanism to schedule them and to carry out the schedulability analysis. In contrast, the time based scheduling scheme may be used to schedule a set of tasks with greater degree of schedulability achieved at a cost of higher complexity of off-line scheduling. One of the drawbacks of currently available scheduling schemes, however, is known to be their inflexibility in dynamic environments where dynamic processes exist, such as aperiodic and sporadic processes. We develop and analyze scheduling schemes which efficiently provide the flexibility required in real-time systems for scheduling processes arriving dynamically. This enables static hard periodic processes and dynamic processes(aperiodic or sporadic) to be jointly scheduled. (Also cross-referenced as UMIACS-TR-97-44)
Scheduling of Periodic Tasks with Relative Timing Constraints
(1998-10-15) Cheng, Sheng-Tzong; Agrawala, Ashok K.
The problem of non-preemptive scheduling of a set of periodic tasks on a single processor has been traditionally considering the ready time and deadline on each task. As a consequence, a feasible schedule finds that in each period one instance of each task starts the execution after the ready time and completes the execution before the deadline . Recently, the timing requirements of the real-time systems emerge that the relative timing constraints are imposed on the consecutive executions of each task. In this paper, we consider the scheduling problem of the periodic tasks with the relative timing constraints imposed on two consecutive executions of a task. We analyze the timing constraints and derive the scheduling window for each task instance. Based on the scheduling window, we present the time-based approach of scheduling a task instance. The task instances are scheduled one by one based on their priorities assigned by the proposed algorithms in this paper. We conduct the experiments to compare the schedulability of the algorithms. (Also cross-referenced as UMIACS-TR-94-135)
Temporal accuracy and modern high performance processors: A case study using Pentium Pro
(1998-10-15) Kailas, Krishnan K.; Trinh, Bao; Agrawala, Ashok K.
Real-time systems must be able to ensure temporally determinate execution of real-time tasks at run-time. By temporal accuracy, we refer to the timing accuracy with which the execution of a task can be started at a predetermined time. Temporally determinate execution of tasks on modern high performance processors is becoming more and more difficult because of the techniques used by these processors to boost their average performance. This report describes the experiments we have conducted to measure the temporal accuracy that can be achieved with the Pentium Pro processor. We present the results of these experiments and analyze these results to highlight the limitations of temporally determinate execution of programs on modern high performance processor architectures. (Also cross-referenced as UMIACS-TR-97-60)
Temporally Determinate Disk Access: An Experimental Approach
(1998-10-15) Aboutabl, Mohamed; Agrawala, Ashok K.; Decotignie, Jean-Dominique
Disk drives are the most commonly used secondary storage devices in computer systems. The way operating systems access these devices leads to a wide range of variability in access time. In this report we study the detailed temporal characteristics of disk drives. We describe a comprehensive set of experiments designed to build a model for the disk drive. Simulation is used to validate the model. This disk model will help design a device driver which can achieve a high degree of temporal determinacy. (Also cross-referenced as UMIACS-TR-97-14)