Computer Sciences Commons^™

Reasoning And Learning With Imperfect Casebases: An Agent Perspective With An Expert Model, Leen-Kiat Soh

School of Computing: Technical Reports

Traditionally, case-based reasoning (CBR) (e.g., Watson and Marir 1994) assumes that the cases in the casebase are correct, useful in both time and space. Otherwise, the cases would not have been stored in the casebase in the first place. Cases are supposed to be useful in guiding us to a successful solution, or in preventing us from repeating the same failure.

Survivable Traffic Grooming With Path Protection At The Connection Level In Wdm Mesh Networks, Wang Yao, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Survivable traffic grooming (STG) is a promising approach to provide reliable and resource-efficient multigranularity connection services in wavelength division multiplexing (WDM) optical networks. In this paper, we study the STG problem in WDM mesh optical networks employing path protection at the connection level. Both dedicated protection and shared protection schemes are considered. Given the network resources, the objective of the STG problem is to maximize network throughput. To enable survivability under various kinds of single failures such as fiber cut and duct cut, we consider the general shared risk link group (SRLG) diverse routing constraints. We first resort to the …

A Graph Model For Dynamicwaveband Switching In Wdm Mesh Networks, Mengke Li, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

We investigate the problem of waveband switching (WBS) in a wavelength-division multiplexing (WDM) mesh network with dynamic traffic requests. To solve the WBS problem in a homogeneous dynamic WBS network, where every node is a multi-granular optical cross-connect (MG-OXC), we construct an auxiliary graph. Based on the auxiliary graph, we develop two heuristic on-line WBS algorithms with different grouping policies, namely the wavelength-first WBS algorithm based on the auxiliary graph (WFAUG) and the waveband-first WBS algorithm based on the auxiliary graph (BFAUG). Our results show that the WFAUG algorithm outperforms the BFAUG algorithm.

Ilmda: Intelligent Learning Materials Delivery Agents, Leen-Kiat Soh, L.D. Miller, Todd Blank, Suzette Person

School of Computing: Technical Reports

In this paper, we describe an intelligent agent that delivers learning materials adaptively to different students, factoring in the usage history of the learning materials, the student static background profile, and the student dynamic activity profile. Our assumption is that through the interaction of a student going through a learning material (i.e., a topical tutorial, a set of examples, and a set of problems), our agent will be able to capture and utilize the student’s activity as the primer to select the appropriate example or problem to administer to the student. Even if the agent fails to do so, it …

On Cooperative Learning Teams For Multiagent Team Formation, Leen-Kiat Soh

School of Computing: Technical Reports

In this paper, we propose a team formation methodology based on cooperative learning teams, adopted from the area of educational research. Cooperative learning is a type of learning where students work in teams and learn through team-based interactions. In education, research in assigning students to appropriate teams and enforcing fair assessment of student performance in a team have generated useful policies and rules. In our multiagent systems project, we use these policies and rules as the underlying framework to evaluate and form teams. We have built a system called I-MINDS as an infrastructure to support cooperative learning among remote and …

Maximizing Resource Sharing In Wdm Mesh Networks With Path-Based Protection And Sparse Oeo Regeneration, Xi Yang, Byrav Ramamurthy, Lu Shen

School of Computing: Conference and Workshop Papers

We propose a resource-sharing scheme that supports three kinds of sharing scenarios in a WDM mesh network with path-based protection and sparse OEO regeneration. Several approaches are used to maximize the sharing of wavelength-links and OEO regenerators.

Distributed Hybrid Agent Based Intrusion Detection And Real Time Response System, Vaidehi Kasarekar, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Wireless LANs are growing rapidly and security has always been a concern. We have implemented a hybrid system, which will not only detect active attacks like identity theft causing denial of service attacks, but will also detect the usage of access point discovery tools. The system responds in real time by sending out an alert to the network administrator.

A Load-Balancing Shared-Protection-Path Reconfiguration Approach In Wdm Wavelength-Routed Networks, Lu Shen, Xi Yang, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Wavelength-routed networks (WRN) are very promising candidates for next-generation Internet and telecommunication backbones. In such a network, optical-layer protection is of paramount importance due to the risk of losing large amounts of data under a failure. To protect the network against this risk, service providers usually provide a pair of risk-independent working and protection paths for each optical connection. However, the investment made for the optical-layer protection increases network cost. To reduce the capital expenditure, service providers need to efficiently utilize their network resources. Among all the existing approaches, shared-path protection has proven to be practical and cost-efficient [1]. In …

Imsh: An Iterative Heuristic For Srlg Diverse Routing In Wdm Mesh Networks, Ajay Todimala, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Survivable routing of a connection involves computation of a pair of diverse routes such that at most one mute fails when failures occur in the network topology. A subset of links in the network that share the risk of failure at the same time are said to belong to a Shared Risk Link Group (SRLG) [3]. A network with shared risk link groups defined over its links is an SRLG network. A failure of an SRLG is equivalent to the failure of all the links in the SRLG. For a connection to he survivable in an SRLG network its working …

Survivable Traffic Grooming With Differentiated End-To-End Availability Guarantees In Wdm Mesh Networks, Wang Yao, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Traffic grooming is critical in WDM optical metropolitan area networks (MANS), where low-rate connections are packed onto high-rate wavelength paths (lightpaths). Various applications in the MAN demand different levels of reliability. Therefore, it is necessary to provision connections with differentiated reliability guarantees in the MAN. In this paper, we first present an analytical model to calculate the availability of connections using different protection schemes in WDM optical MANs with general mesh topologies. Then we propose and simulate two grooming algorithms which can provision availability guaranteed connections based on per-connection requirements.

A Gcd Attack Resistant Crthacs For Secure Group Communications, Xukai Zou, Byrav Ramamurthy, Spyros S. Magliveras

School of Computing: Conference and Workshop Papers

In this paper, we propose an improved CRTHACS scheme for secure group communications. The scheme resists several GCD attacks which exist in the original CRTHACS scheme [2] and were recently reported in [1].

Infrastructure Support For Controlled Experimentation With Software Testing And Regression Testing Techniques, Hyunsook Do, Sebastian Elbaum, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Where the creation, understanding, and assessment of software testing and regression testing techniques are concerned, controlled experimentation is an indispensable research methodology. Obtaining the infrastructure necessary to support such experimentation, however, is difficult and expensive. As a result, progress in experimentation with testing techniques has been slow, and empirical data on the costs and effectiveness of techniques remains relatively scarce. To help address this problem, we have been designing and constructing infrastructure to support controlled experimentation with testing and regression testing techniques. This paper reports on the challenges faced by researchers experimenting with testing techniques, including those that inform the …

An Extended Kernel For Generalized Multiple-Instance Learning, Qingping Tao, Stephen Scott, N. V. Vinodchandran, Thomas Takeo Osugi, Brandon Mueller

School of Computing: Conference and Workshop Papers

The multiple-instance learning (MIL) model has been successful in areas such as drug discovery and content-based image-retrieval. Recently, this model was generalized and a corresponding kernel was introduced to learn generalized MIL concepts with a support vector machine. While this kernel enjoyed empirical success, it has limitations in its representation. We extend this kernel by enriching its representation and empirically evaluate our new kernel on data from content-based image retrieval, biological sequence analysis, and drug discovery. We found that our new kernel generalized noticeably better than the old one in content-based image retrieval and biological sequence analysis and was slightly …

Evaluating Consistency Algorithms For Temporal Metric Constraints, Yang Shi, Anagh Lal, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

Focus: Networks of temporal metric constraints

Task: Evaluating the performance of algorithms for:

·Determining the consistency of the Simple Temporal Problem (STP)

·Finding the minimal network of the Temporal Constraint Satisfaction Problem (TCSP)

Future: Enhance triangulation-based algorithms with incrementality

A Study In Modeling Low-Conservation Protein Superfamilies, Chang Wang, Stephen Scott, Jun Zhang, Qingping Tao, Dmitri E. Fomenko, Vadim N. Gladyshev

School of Computing: Technical Reports

We present several algorithms for identification of new proteins in superfamilies with low primary sequence conservation. The low conservation of primary sequence in protein superfamilies such as Thioredoxin-fold (Trx-fold) makes conventional methods such as hidden Markov models (HMMs) difficult to use. Therefore, we use structural properties to build our classifiers. These structural properties include secondary structure patterns as well as various properties of the residues in the protein sequences. We use this information to model proteins via hidden Markov models, support vector machines and algorithms in the multiple-instance learning model. In 20-fold jack-knife tests, some of our models performed well, …

Variable Rate Execution, Steve Goddard, Xin Liu

School of Computing: Technical Reports

We present a task model for adaptive real-time tasks in which a task’s execution rate requirements are allowed to change at any time. The model, variable rate execution (VRE), is an extension of the rate-based execution (RBE) model. We relax the constant execution rate assumption of canonical realtime task models by allowing both the worst case execution time (WCET) and the period to be variable. The VRE model also supports tasks joining and leaving the system at any time. Another advantage of the new task model is that the exact execution rate need not be known for soft real-time or …

A Load-Balancing Spare Capacity Reallocation Approach In Service-Rich Sonet Metro Mesh Networks, Lu Shen, Xi Yang, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

The next-generation SONET metro network is evolving into a service-rich infrastructure. At the edge of such a network, multi-service provisioning platforms (MSPPs) provide efficient data mapping enabled by Generic Framing Procedure (GFP) and Virtual Concatenation (VC). The core of the network tends to be a meshed architecture equipped with Multi-Service Switches (MSSs). In the context of these emerging technologies, we propose a load-balancing spare capacity reallocation approach to improve network utilization in the next-generation SONET metro networks. Using our approach, carriers can postpone network upgrades, resulting in increased revenue with reduced capital expenditures (CAPEX). For the first time, we consider …

A Dynamic Real-Time Scheduling Algorithm For Reduced Energy Consumption, Rohini Krishnapura, Steve Goddard, Ala' Adel Qadi

School of Computing: Technical Reports

In embedded real-time systems, Dynamic Power Management (DPM) techniques have traditionally focused on reducing the dynamic power dissipation that occurs when a CMOS gate switches in a processor. Less attention has been given to processor leakage power or power consumed by I/O devices and other subsystems. I/O-based DPM techniques, however, have been extensively researched in non-real-time systems. These techniques focus on switching I/O devices to low power states based on various policies and are not applicable to real-time environments because of the non-deterministic nature of the policies. The challenge in conserving energy in embedded real-time systems is thus to reduce …

Survivable Virtual Topology Routing Under Shared Risk Link Groups In Wdm Networks, Ajay Todimala, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Network survivability is one of the most important issues in the design of optical WDM networks. In this work we study the problem of survivable routing of a virtual topology on a physical topology with Shared Risk Link Groups (SRLG). The survivable virtual topology routing problem against single-link failures in the physical topology is proved to be NP-complete in [1]. We prove that survivable virtual topology routing problem against SRLG/node failures is also NP-complete. We present an improved integer linear programming (ILP) formulation (in comparison to [1]) for computing the survivable routing under SRLG/node failures. Using an ILP solver, we …

Rerouting Schemes For Dynamic Traffic Grooming In Optical Wdm Mesh Networks, Wang Yao, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Traffic grooming in optical WDM mesh networks is a two-layer routing problem to effectively pack low-rate connections onto high-rate lightpaths, which, in turn, are established on wavelength links. In this work, we employ the rerouting approach to improve the network throughput under the dynamic traffic model. We propose two rerouting schemes, rerouting at lightpath level (RRAL) and rerouting at connection level (RRAC). A qualitative comparison is made between RRAL and RRAC. We also propose the critical-wavelength-avoiding one-lightpath-limited (CWA-1L) and critical-lightpath-avoiding one-connection-limited (CLA-1C) rerouting heuristics, which are based on the two rerouting schemes respectively. Simulation results show that rerouting reduces the …

Special Section On The Algorithmics Of Software Model Checking — Introductory Paper, Matthew Dwyer, Stefan Leue

School of Computing: Faculty Publications

The term “software model checking” has recently been coined to refer to a flourishing area of research in software verification – the formal, automated analysis of program source code. Software model checking is considered an important application of classical model checking, where the model of a software system is analyzed in an automated fashion for compliance with a property specification. While classical model checking assumes the existence of an abstract model of the software system to be analyzed, in software model checking the emphasis is on directly analyzing program code given in a standard programming language, such as Java or …

An Analysis Of Mcmc Sampling Methods For Estimating Weighted Sums In Winnow, Qingping Tao, Stephen Scott

School of Computing: Technical Reports

Chawla et al. introduced a way to use the Markov chain Monte Carlo method to estimate weighted sums in multiplicative weight update algorithms when the number of inputs is exponential. But their algorithm still required extensive simulation of the Markov chain in order to get accurate estimates of the weighted sums. We propose an optimized version of Chawla et al.’s algorithm, which produces exactly the same classifications while often using fewer Markov chain simulations. We also apply three other sampling techniques and empirically compare them with Chawla et al.’sMetropolis sampler to determine how effective each is in drawing good samples …

Using Source-Code Analysis To Help End-User Programmers Create Dependable Software, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Not long ago, most software was written by professional programmers, who could be presumed to have an interest in software engineering methodologies and in tools and techniques for improving software dependability. Today, however, a great deal of software is written not by professionals but by end-users, who create applications such as multimedia simulations, dynamic web pages, and spreadsheets. Applications such as these are often used to guide important decisions or aid in important tasks, and it is important that they be sufficiently dependable, but evidence shows that they frequently are not. For example, studies have shown that a large percentage …

Empirical Studies Of Test Case Prioritization In A Junit Testing Environment, Hyunsook Do, Gregg Rothermel, Alex Kinneer

School of Computing: Conference and Workshop Papers

Test case prioritization provides a way to run test cases with the highest priority earliest. Numerous empirical studies have shown that prioritization can improve a test suite’s rate of fault detection, but the extent to which these results generalize is an open question because the studies have all focused on a single procedural language, C, and a few specific types of test suites. In particular, Java and the JUnit testing framework are being used extensively in practice, and the effectiveness of prioritization techniques on Java systems tested under JUnit has not been investigated. We have therefore designed and performed a …

Evaluating Consistency Algorithms For Temporal Metric Constraints, Yang Shi, Anagh Lal, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

We study the performance of some known algorithms for solving the Simple Temporal Problem (STP) and the Temporal Constraint Satisfaction Problem (TCSP). In particular, we empirically compare the Bellman-Ford (BF) algorithm and its incremental version (incBF) by (Cesta & Oddi 1996) to the ΔSTP of (Xu & Choueiry 2003a). Among the tested algorithms, we show that ΔSTP is the most efficient for determining the consistency of an STP, and that incBF combined with the heuristics of (Xu & Choueiry 2003b) is the most efficient for solving the TCSP. We plan to improve ΔSTP by exploiting incrementality as in incBF and …

A Nonparametric Classifier For Unsegmented Text, George Nagy, Ashutosh Joshi, Mukkai Krishnamoorthy, Yu Lin, Daniel Lopresti, Shashank K. Mehta, Sharad C. Seth

School of Computing: Conference and Workshop Papers

Symbolic Indirect Correlation (SIC) is a new classification method for unsegmented patterns. SIC requires two levels of comparisons. First, the feature sequences from an unknown query signal and a known multi-pattern reference signal are matched. Then, the order of the matched features is compared with the order of matches between every lexicon symbolstring and the reference string in the lexical domain. The query is classified according to the best matching lexicon string in the second comparison. Accuracy increases as classified feature-and-symbol strings are added to the reference string.

Spatiotemporal Databases: Models For Attracting Students To Research, Ágnes Bércesné Novák, Peter Revesz, Zsolt Tuza

School of Computing: Conference and Workshop Papers

In higher education professors often make much effort to introduce their students to research. Unfortunately, the present standard database systems curriculum is composed of well-settled subjects that do not lead to research. The challenge is to bring the research frontier closer to students at beginner level. In this paper we describe how it can be done in the area of spatiotemporal databases. We propose a new database systems curriculum and illustrate its benefits by mentioning several highly succsesful student projects in some recent experimental introductory database systems courses that followed the new curriculum.

Constraint Datalog In Trust Management, Scot Anderson

School of Computing: Dissertations, Theses, and Student Research

Constraint Datalog holds an increasing role in Trust Management. We discuss several Trust Management systems and give a description of the environment and requirements for Trust Management. Constraint Datalog using addition constraints and approximation theory provides an expressive semantic with which to describe security policies for credentials, delegations and authorizations. Approximation theory allows halting in Constraint Datalog over addition constraints. We use the decision problem of Diophantine equations to show that Constraint Datalog over addition constraints is complete. Combining these two concepts provides an approximately complete, safe language. The problem of constant additions to closed languages provides reasons for using …

Flocking Over 3d Terrain, Joel Gompert

School of Computing: Technical Reports

A method is presented for animating herds of animals that can follow terrain while being efficient enough to run in real-time. This method involves making simple modifications to Reynolds’ agent-based flocking algorithm. The modifications use only local properties of the terrain, and thus have low complexity. This method focuses on using terrain that can be described as an elevation grid, but it may be extendible to arbitrary terrain. The flocking algorithm with these modifications produces naturally behaving herds that follow the terrain. They will swerve around hills and attempt to follow paths that reduce energy expenditure. The terrain-following rule added …

Middleware Infrastructure For Parallel And Distributed Programming Models In Heterogeneous Systems, Jameela Al-Jaroodi, Nader Mohamed, Hong Jiang, David Swanson

School of Computing: Faculty Publications

In this paper, we introduce a middleware infrastructure that provides software services for developing and deploying high-performance parallel programming models and distributed applications on clusters and networked heterogeneous systems. This middleware infrastructure utilizes distributed agents residing on the participating machines and communicating with one another to perform the required functions. An intensive study of the parallel programming models in Java has helped identify the common requirements for a runtime support environment, which we used to define the middleware functionality. A Java-based prototype, based on this architecture, has been developed along with a Java Object-Passing Interface (JOPI) class library. Since this …