Steve Goddard
Department of Computer Science and Engineering
University of Nebraska-Lincoln
September 2003
My research activities focus on two areas: high assurance systems and distributed geospatial decision support systems. My most significant, and largest body of work, has been in the area of high assurance systems. In 2000, I began to broaden my research activities to include distributed geospatial decision support systems and the application of computer science to the fields of climatology and agronomy. The following subsections summarize my research, its significance, and its impact.
Research in High Assurance Systems. My research in high assurance systems is focused on providing deterministic methods for building reliable, predictable, and robust systems that must execute in unpredictable environments. This work can be further divided into the categories of real-time systems and high assurance network-clustered servers.
Real-Time Systems. My research in real-time systems has been driven by my 13 years of industry experience before joining the faculty at UNL. During that time, it became apparent that the theory of real-time systems available to practitioners was extremely restrictive. Most real-time task models assumed a fixed, periodic set of tasks, or allowed only slight variations of that model (e.g., the sporadic task model). Thus, my research goal in this area has been to develop flexible, dynamic task models and scheduling theory that guarantees temporal requirements will be met under specified conditions. I have made significant progress supported by grants from NSF and NASA, but there is much work to be done as I continue to relax assumptions about the workload to allow even more flexibility.
One of my most notable publications in the area of real-time systems [28] presents a task model, scheduling algorithm, and polynomial-time schedulability test for systems that must execute both hard real-time and non-real-time applications with shared resources. The task model, which was first presented in [21], is a generalization of the rate-based execution model [27]. The knowledge gained in these progressively more flexible task models is currently being used to develop a new Variable Rate Execution task model that will form the basis of Xin Liu’s Ph.D. dissertation under my supervision. These significant papers have been presented in top-tier, peer-reviewed conferences,[1] and I have begun to submit this work to journals (e.g., [29]). It should be noted, however, that the conference versions of these papers will remain widely recognized by the community as the defining work.
My quest for new, flexible task models and scheduling algorithms began with my research into the synthesis of real-time systems from processing graphs. Processing graphs are a standard design aid in the development of complex digital signal processing systems. These directed graphs consist of nodes and graph edges depicting the flow of data from one node to the next. When sufficient data arrives, a node executes its function from start to finish in isolation (i.e., without synchronization). During my years of industry work, I helped to build signal processing systems that were based on processing graphs. At that time, however, none of the real-time task models in the literature could be applied to these systems. Using an early form of the task model presented in [27], I published a series of papers that address latency [14, 15, 16, 17] and memory buffer management [15, 18, 19] in the synthesis of real-time systems from processing graphs [14, 15, 16, 17, 18, 19].
Prior to this work, latency and memory needs were evaluated using queuing theory and no hard, deterministic bounds could be provided. My research provided the first deterministic scheduling algorithms and analysis techniques that could be applied to the U.S. Navy’s Processing Graph Method. My most significant paper from this body of research is [14], which describes the overall process of converting a processing graph into a hard-real-time system. The details of these steps, however, are actually presented in conference papers [16, 17, 18, and 19].
High Assurance Network Clustered Servers. My work in high assurance networked-clustered servers has had direct and immediate impact on industry:
1. Six U.S. patents have been filed and published [3, 5, 6, 8, 9, 11];
2. Four international patents have been filed and published [4, 7, 10, 12];
3. Three patent disclosures have been recommended for patenting by the Research Triangle Institute (RTI), which was hired by UNL’s Office of Technology Transfer (OTT) to perform a detailed market analysis;
4. Flextel S.p.A., of Italy, has licensed this technology for integration into their secureVision 3000 and webVision 4000 products.
My research in this area began with the development of two network-clustered Web server prototypes based on different server architectures [1, 2]: OSI layer two dispatching (LSMAC) and OSI layer three dispatching (LSNAT). Both network-clustered server systems were implemented as application-space programs running on commodity hardware. Building on my basic LSNAT and LSMAC prototypes, I developed a scalable, application-space, highly-available network-clustered web server, called SASHA, that demonstrates high performance and fault tolerance using application-space software and Commercial-Off-The-Shelf (COTS) hardware and operating systems [22].
The significance of this work is that it removed the dispatcher as a single-point of failure in the cluster without using a dedicated standby unit. Instead, the cluster uses a simple protocol to detect the failure of any server and automatically reconfigures the cluster without the failed server. If the failed server was the dispatcher, a new dispatcher is elected from the pool of servers. This technique (and others developed for SASHA) led to my research in fault-tolerant firewall sandwiches [9, 10, 20] and handling overload conditions in servers [3, 4, 5, 6, 7, 8].
The most cited paper from this body of research [31] provides an overview of network-clustering technologies and is used in numerous distributed systems courses. Following the advice of UNL’s patent lawyers, however, I have not published the most significant research results from this area in normal scientific venues. The technology, however, has been published as patents, which are available from the United States Patent and Trademark Office (USPTO) Web site. Of my patents filed, [5, 6, 7, 8] are the most significant with the potential for the largest impact; they describe a method of queuing and dispatching requests to a Web server that has the potential to nearly triple its throughput (results range from a 50% to 175% increase in throughput, depending on hardware configuration and request types).
Research in Distributed Geospatial Decision Support Systems and Applied CS. In 2000, I began interdisciplinary work with scientists from the Computer Science and Engineering Department, the National Drought Mitigation Center (NDMC) and the High Plains Regional Climate Center (HPRCC). These collaborations have resulted in the National Agricultural Decision Support System (NADSS) and over $2,300,000 in NSF and USDA research grants for which I am the principal investigator.
My most significant contribution to the area of distributed geospatial decision support systems is the design and implementation of a new system architecture consisting of four distinct layers: data, information, knowledge, and presentation. Each layer contains an integrated cache system. An overview of the architecture and the NADSS project goals is presented in [13]. The details of the system are presented in [23, 25, 36, 37]. Two journal papers on this work are near completion, but they have not yet been submitted.
As part of my interdisciplinary research on the NADSS project, I have applied computer science techniques and technologies to the fields of climatology and agronomy. This has resulted in publications in the use of data mining to identify associations between El Nino/La Nina events and droughts in Nebraska [24, 25, 32, 33], and in new methods to quantify the impact and severity of droughts [34, 35].
The most significant result of my interdisciplinary research is the creation of the Self-Calibrating Palmer Drought Severity Index (SC-PDSI) [35]. The SC-PDSI represents the most significant change to the computation of the Palmer Drought Severity Index (PDSI) since its inception in 1965. Working with one of my undergraduate students, Nathan Wells (selected to USA Today’s 2002 Academic Second Team), we were able to develop a method of self-calibration for the index that results in a more spatially comparable PDSI than ever before.
Future Research. My past research results have created a solid foundation for future research. I am excited by the research my students and I are continuing to do in high assurance systems and applied computer science.
Xin Liu and I are nearing the completion of a paper presenting the Variable Rate Execution (VRE) task model. The VRE extends the rate-based execution (RBE) task model [27] by allowing tasks to enter and leave the system at anytime, change their execution rates, or even change their execution durations, while providing temporal guarantees of hard real-time tasks. This is a significant result as it is the next step in providing flexible, dynamic real-time task models and scheduling algorithms.
My research in high-assurance systems will continue in two primary directions. First, I plan to further explore the role of rate-based resource allocation in various environments and at various levels of the operating system. Second, I have begun to research energy-aware resource allocation methods in high-assurance systems with students Ala˘ Qadi and Rohini Krishnapura. My first paper in this area, “A Dynamic Voltage Scaling Algorithm for Sporadic Tasks” will be presented in RTSS’03 (Real-Time Systems Symposium 2003) [30]. This paper presents the first Dynamic Voltage Scaling (DVS) algorithm for the canonical sporadic task model. The next steps in this line of research are to develop techniques that also support resource sharing and to relax the assumptions of the sporadic task model until we are able to support variable-rate tasks. We are also working on new ways to schedule I/O devices such that energy consumption is minimized while still providing temporal guarantees.
My future research in distributed geospatial decision support systems and applied computer science will focus on the integration of parallel and grid computing concepts with our existing CORBA-based architecture as we add more simulation and modeling tools to NADSS. To make the system as useful as possible to natural scientists, the tools must be interactive and provide the scientist the opportunity to guide computations. This requires a much more advanced distributed system architecture, new computational algorithms, and more sophisticated resource allocation methods. In other words, many new research opportunities and a lot of fun!
[1] X. Gan, T. Schroeder, S. Goddard, and B. Ramamurthy, “LSMAC vs. LSNAT: Scalable Cluster-based Web Servers,” Cluster Computing: The Journal of Networks, Software Tools and Applications, Vol. 3, No. 3, 2000, pp. 175-185.
[2] X. Gan, T. Schroeder, S. Goddard, and B. Ramamurthy, “LSMAC and LSNAT: Two Approaches for Cluster-based Scalable Web Servers,” Proceedings of ICC 2000, New Orleans, Louisiana, June 2000.
[3] S. Goddard, “Assured Quality-of-Service Request Scheduling,” U.S. Patent Application Serial No. 10/008024, filed November 5, 2001, U.S. Patent Publication No. 20020083117, published June 27, 2002; patent pending.
[4] S. Goddard, “Assured Quality-of-Service Request Scheduling,” International Application No. PCT/US01/46854, filed November 5, 2001, International Publication No. WO 02/39696 A2, published May 16, 2002; patent pending.
[5] S. Goddard, “Computer Server Having Non-Client-Specific Persistent Connections,” U.S. Patent Application Serial No. 09/008035, filed November 5, 2001, U.S. Patent Publication No. 20020055983, published May 9, 2002; patent pending.
[6] S. Goddard, “Controlled Server Loading,” U.S. Patent Application Serial No. 09/930014, filed August 15, 2001, U.S. Patent Publication No. 20020055980, published May 9, 2002; patent pending.
[7] S. Goddard, “Controlled Server Loading,” International Application No. PCT/US01/47013, filed November 5, 2001, International Publication No. WO 02/37799 A2, published May 10, 2002; patent pending.
[8] S. Goddard, “Controlled Server Loading Using L4/3 Dispatching,” U.S. Patent Application Serial No. 09/965526, filed September 26, 2001, U.S. Patent Publication No. 20020055982, published May 9, 2002; patent pending.
[9] S. Goddard, “Fault-Tolerant Firewall Sandwiches,” U.S. Patent Application Serial No. 10/274344, filed October 18, 2002, U.S. Patent Publication No. 20030131262, published July 10, 2003; patent pending.
[10] S. Goddard, “Fault-Tolerant Firewall Sandwiches,” International Patent Application No. (Attorney Docket No. 2186-000007/WO/POA), filed October 18, 2002; patent pending.
[11] S. Goddard, X. Gan, and B. Ramamurthy, “System and Method for an Application-Space Server Cluster,” U.S. Patent Application Serial No. 09/878787; filed June 11, 2001, U.S. Patent Publication No. US-2003-0046394-A1, published March 6, 2003; patent pending.
[12] S. Goddard, X. Gan, and B. Ramamurthy, “System and Method for an Application-Space Server Cluster,” International Application No. PCT/US01/49863, filed October 29, 2001, International Publication No. WO 02/43343 A2, published May 30, 2002; patent pending.
[13] S. Goddard, S.K. Harms, S.E. Reichenbach, T. Tadesse, and W.J. Waltman, “Geospatial Decision Support for Drought Risk Management,” Communications of the ACM, Vol. 46, No. 1, 2003, pp. 35-37.
[14] S. Goddard and K. Jeffay, “Analyzing the Real-Time Properties of a U.S. Navy Signal Processing System,” International Journal of Reliability, Quality and Safety Engineering, Special Issue for top ranked HASE’99 papers, Vol. 8, No. 4, 2001, pp. 301-322.
[15] S. Goddard and K. Jeffay, “Managing Latency and Buffer Requirements in Processing Graph Chains,” The Computer Journal, special Issue on High Assurance Systems, Vol. 44, No. 6, 2001, pp. 486-503.
[16] S. Goddard and K. Jeffay, “The Synthesis of Real-Time Systems from Processing Graphs,” Proceedings of the Fifth IEEE International Symposium on High Assurance Systems Engineering, Albuquerque, New Mexico, November 2000, pp. 177-186.
[17] S. Goddard and K. Jeffay, “Analyzing the Real-Time Properties of a U.S. Navy Signal Processing System,” Proceedings of the Fourth IEEE International Symposium on High Assurance Systems Engineering, Washington, D.C., November 1999, pp. 141-150.
[18] S. Goddard and K. Jeffay, “Managing Memory Requirements in the Synthesis of Real-Time Systems from Processing Graphs,” Proceedings of the IEEE Real-Time Technology and Applications Symposium, Denver, Colorado, June 1998, pp. 59-70.
[19] S. Goddard and K. Jeffay, “Analyzing the Real-Time Properties of a Dataflow Execution Paradigm using a Synthetic Aperture Radar Application,” Proceedings of the IEEE Real-Time Technology and Applications Symposium, Montreal, Canada, June 1997, pp. 60-71.
[20] S. Goddard, R. Kieckhafer, and Y. Zhang, “An Unavailability Analysis of Firewall Sandwich Configurations,” Proceedings of the Sixth IEEE International Symposium on High Assurance Systems Engineering, Boca Raton, Florida, October 2001, pp. 139-148.
[21] S. Goddard and X. Liu, “Scheduling Aperiodic Requests under the Rate-Based Execution Model,” Proceedings of the 23rd IEEE Real-Time Systems Symposium, Austin, Texas, December 2002, pp. 15-25.
[22] S. Goddard and T. Schroeder, “The SASHA Architecture for Network-Clustered Web Servers,” Proceedings of the Sixth IEEE International Symposium on High Assurance Systems Engineering, Boca Raton, Florida, October 2001, pp. 163-172.
[23] S. Goddard, S. Zhang, W.J. Waltman, D. Lytle, and S. Anthony, “A Software Architecture for Distributed Geospatial Decision Support Systems,” Proceedings of the Second National Conference on Digital Government Research, Los Angeles, California, May 2002, pp. 45-52.
[24] S.K. Harms, J. Deogun, S. Goddard, and T. Tadesse, “Building Knowledge Discovery into a Geo-spatial Decision Support System,” Proceedings of the 2003 ACM Symposium on Applied Computing, Melbourne, Florida, March 2003, pp. 445-449.
[25] S.K. Harms, S. Goddard, S.E. Reichenbach, W.J. Waltman, T. Tadesse, “Data Mining in a Geospatial Support System for Drought Risk Management,” Proceedings of the First National Conference on Digital Government Research, Los Angeles, California, May 2001, pp. 9-16.
[26] W. He and S. Goddard, “Capturing an Application’s Temporal Properties with UML for Real-Time,” Proceedings of the Fifth IEEE International Symposium on High Assurance Systems Engineering, Albuquerque, New Mexico, November 2000, pp. 65-74.
[27] K. Jeffay and S. Goddard, “A Theory of Rate-Based Execution,” Proceedings of the 20th IEEE Real-Time Systems Symposium, Phoenix, Arizona, December 1999, pp. 304-314.
[28] X. Liu and S. Goddard, “Resource Sharing in an Enhanced Rate-Based Execution Model,” Proceedings of the 15th Euromicro Conference on Real-Time Systems, Porto, Portugal, July 2003, pp. 131-140.
[29] X. Liu and S. Goddard, “Scheduling Legacy Multimedia Applications,” Journal of Systems and Software, to appear in July 2004.
[30] A. Qadi, S. Goddard, and S. Farritor, “A Dynamic Voltage Scaling Algorithm for Sporadic Tasks,” to appear in Proceedings of the 24th IEEE Real-Time Systems Symposium, Cancun, Mexico, December 2003.
[31] T. Schroeder, S. Goddard, and B. Ramamurthy, “Scalable Web Server Clustering Technologies,” IEEE Network: Special Issue on Web Performance, Vol. 14, No. 3, 2000, pp. 38-45.
[32] T. Tadesse, D.A. Wilhite, S.K. Harms, M.J. Hayes, and S. Goddard, “Drought Monitoring Using Data Mining Techniques,” Natural Hazards, accepted with revisions for publication in 2004.
[33] T. Tadesse, D.A. Wilhite, M.J. Hayes, S.K. Harms, and S. Goddard, “Discovering Associations Between Climatic and Oceanic Parameters to Monitor Drought Using Data Mining Techniques in Nebraska,” in submission to Journal of Climate, 2003.
[34] W.J. Waltman, S. Goddard, S.E. Reichenbach, M.D. Svoboda, M.J. Hayes, and J.S. Peake, “Patterns and Trends of Soil Climate Regimes and Drought Events in the Northern Great Plains,” to appear in Proceedings of the Applied Geography Conference, Colorado Springs, Colorado, November 2003.
[35] N. Wells, S. Goddard, and M.J. Hayes, “A Self-Calibrating Palmer Drought Severity Index,” in submission to Journal of Climate, 2003.
[36] S. Zhang and S. Goddard, “OpenGIS Conforming Map-Feature Server Implementation Specifications in Component-Based Distributed Systems,” Proceedings of the 2003 International Society for Environmental Information Sciences Conference, Regina, Canada, July 2003.
[37] S. Zhang and S. Goddard, “3CoFramework: A Component-Based Framework for Distributed Applications,” Proceedings of the International Conferences on Software Engineering Research and Practice, Volume I, Las Vegas, Nevada, June 2003, pp. 398-404.
[1] In the area of real-time systems (high assurance systems that require temporal guarantees), the Real-Time Systems Symposium (RTSS) is regarded as the top conference. The Real-Time Technology and Applications Symposium (RTAS) and the Euromicro Conference on Real-Time Systems (ERCTS) are widely recognized as the second and third ranked conferences in real-time systems, with their ranking relative to each other changing over the years.