Kaur, Jasleen and Harrick M. Vin. "Effect of Higher Priority EF Traffic and TCP Throughput and Fairness." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-01. January 2001. 14 pages.
In this paper, we study the effect on TCP of assigning higher-priority to traffice requesting Expedited Forwarding (EF) service in a Differentiated Services network. We analyze networks in which (1) EF traffice occupies different fractions of link bandwidth and is bursty at different time-scales; and (2) multiple TCP flows with heterogeneous round trip times share the network with the EF traffic. We find that even in the presence of bursty EF traffic, statistical multiplexing gains allow TCP to utilize most of the available bandwidth. Further, the presence of bursty EF traffic improves the fairness of bandwidth allocation among TCP flows; smaller more frequent bursts yield larger improvements in TCP fairness.
Sankaralingam, Karthikeyan, Ramadass Nagarajan, Steven W. Keckler, and Doug Burger. "A Technology-Scalable Architecture for Fast Clocks and High ILP." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-02. February 2001. 15 pages.
CMOS technology scaling poses challenges in designing dynamically scheduled cores that can sustain both high instruction-level parallelism and aggressive clock frequencies. In this paper, we present a new architecture that maps compiler-scheduled blocks onto a two-dimensional grid of ALUs. For the mapped window of execution, instructions execute in a dataflow-like manner, with each ALU forwarding its result along short wires to the consumers of the result. We describe our studies of program behavior and a preliminary evaluation that show that this architecture has the potential for both high clock speeds and high ILP, and may offer the best of both the VLIW and dynamic superscalar architectures.
Gorinsky, Sergey and Harrick Vin. "The Utility of Feedback in Layered Multicast Congestion Control." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-04. March 2001. 6 pages.
Layered multicast is a common approach for dissemination of audio and video in heterogeneous network environments. Layered multicast schemes can be classified into two categories - feedback-based and feedback-free - depending on whether or not the scheme delivers feedback to the sender of the multicast session. Advocates of feedback-based schemes claim that the feedback is necessary to match the heterogeneous receiver capabilities efficiently. Supporters of feedbackfree schemes believe that feedback introduces significant complexity and that a moderate amount of additional layers can balance any benefit the feedback provides. Surprisingly, there has been no systematic evaluation of these claims. This paper compares feedback-based and feedback-free schemes quantitatively with respect to their abilities to align the provided service to the capabilities of the heterogeneous receivers. We believe that such an evaluation supplies valuable insights and guidelines to the designers of future multicast congestion control protocols.
Dhillion, Inderjit S. "Co-clustering Documents and Words Using Bipartite Spectral Graph Partitioning." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-05. March 2001. 22 pages.
Both document clustering and word clustering are important and well-studied problems. By using the vector space model, a document collection may be represented as a word-document matrix. In this paper, we present the novel idea of modeling the document collection as a bipartite graph between documents and words. Using this model, we pose the clustering problem as a graph partitioning problein and give a new spectral algorithm that simultaneously yields a clustering of documents and words. This co-clustering algorithm uses the second left and right singular vectors of an appropriately scaled word-document matrix to yield good bipartitionings. In fact, it can be shown that these singular vectors give a real relaxation to the optimal solution of the graph bipartitioning problem. We present several experimental results to verify that the resulting co-clustering algorithm works well in practice and is robust in the presence of noise.
Pierce, Evelyn and Lorenzo Alvisi. "A Framework for Semantic Reasoning about Byzantine Quorum Systems." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-06. March 2001. 17 pages.
We present a set of definitions and theorems that allow us to reason about the semantics of quorum system variables, including Byzantine quorum system variables, as a class. Using these tools, we present a formal proof that the problem of atomic semantics for such variables can be reduced to the simpler problem of regular semantics for such systems. Specifically, any regular masking quorum system protocol can be combined with a writeback mechanism to produce an atomic protocol. We then describe a subclass of TS-variables for which the latter problem is not solvable by traditional approaches in an asynchronous environment. Finally, for such variables we define the notion of pseudoregular and pseudoatomic semantics, and show briefly that the same reduction holds for these concepts.
Pierce, Evelyn Tumlin. "Self-Adjusting Quorum Systems For Byzantine Fault Tolerance." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-07. March 2001. 76 pages.
The purpose of this work has been to design protocols for a data service that tolerates Byzantine server faults by shifting between multiple tolerance modes at run time, monitoring itself for faulty server behavior and dynamically adjusting its own tolerance capabilities accordingly. Our goal is a system that runs in an efficient low-fault mode most of the time, but can adjust itself to cope with new faults as they occur. Our approach is based on the masking quorum systems of Malkhi and Reiter. Like the protocols originally proposed for these systems, our techniques are relatively economical in that updates and reads need to be performed only at a subset ("quorum") of data servers, thus decreasing the workload on individual servers and simplifying the recovery process when failures occur. However, our protocols implement the following additional capabilities: 1. Strengthened read and write protocols for serializability of completed operations. 2. Protocols for dynamically adjusting the threshold (and thus quorum size) of threshold masking quorum systems in response to information about the number and/or probability of faults in the system. 3. Protocols for detecting Byzantine server behavior in threshold masking quorum systems. As a subsidiary goal, we have sought to make our methods not only effective against random faulty server behavior, but also resistant to sabotage by a deliberate adversary. To this end, we have limited our use of standard assumptions, such as independence of failures and a priori limits on the number of faults, that restrict the applicability of many Byzantine fault tolerance techniques to questions of security.
Bajaj, Chandrajit L. and Guoliang Xu. "Anisotropic Diffusion of Subdivision Surfaces and Functions on Surfaces." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-08. April 2001. 26 pages.
In this paper we treat discrete data (2-manifold) in IR 3 and function data defined on the surface. A surface and a k-3 dimensional function vector data on the surface can be considered as a discretization of a 2-manifold embedded in IRk. We establish a unified anisotropic diffusion model for such manifolds aiming at smoothing (fairing) out noise both in the 2-manifold in IR3 and the 2-manifold in IRk, while enhancing curve features on both 2-manifolds. We combine the C1 limit function representation of Loop's subdivision for triangular surface meshes and vector functions on the surface mesh with anisotropic diffusion in a parameterized time setting, to arrive at a sparse linear system of equations. Iteratively, solving the sparse linear system, yields a sequence of faired (smoothed) meshes as well as faired function with specified feature curves, enhanced.
Xu, Guoliang, Chandrajit L. Bajaj, and Susan Evans. "C1Modeling with Hybrid Multiple-sided A-patches." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-09. April 2001. 25 pages.
We propose a new scheme for modeling a smooth interpolatory surface, from a surface discretization consisting of triangles, quadrilaterals and pentagons, by algebraic surface patches which are subsets of real zero contours of trivariate rational functions defined on a collection of tetrahedra and pyramids. The rational form of the modeling function provides enough degrees of freedom so that the number of the surface patches is significantly reduced, and the surface has quadratic recover property.
Zhang, Xiaoyu, Chandrajit L. Bajaj, William Blanke, and Donald Fussell. "Scalable Isosurface Visualization of Massive Datasets on COTS Clusters." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-10. April 2001. 9 pages.
Our scalable isosurface visualization solution on a COTS cluster is an end-to-end parallel and progressive platform, from the initial data access to the final display. In this paper we focus on the back end scalability by introducing a fully parallel and out-of-core isosurface extraction algorithm. It partitions the volume data according to its workload spectrum for load balancing and creates an I/0-optimal external interval tree to minimize the number of I/0 operations of loading large data from disk. It achieves scalability by using both parallel processing and parallel disks. Interactive browsing of extracted isosurfaces is made possible by using parallel isosurface extraction and rendering in conjunction with a new specialized piece of image compositing hardware called Metabuffer. We also describe an isosurface compression scheme that is efficient for isosurface transmission.
Bajaj, Chandrajit L., Joe Warren, and Guoliang Xu. "A Smooth Subdivision Scheme for Hexahedral Meshes." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-11. April 2001. 21 pages.
In a landmark paper, Catmull and Clark described a simple generalization of the subdivision rules for bi-cubic B-splines to arbitrary quadrilateral surface meshes. This smooth subdivision scheme has become a mainstay of surface modeling systems. Joy and MacCracken described a generalization of this surface scheme to volume meshes. Unfortunately, little is known about the smoothness and regularity of this scheme due to the complexity of the subdivision rules. This paper presents an alternative subdivision scheme for hexahedral volume meshes that consists of a simple split and average algorithm. Along extraordinary edges of the volume mesh, the scheme provably converges to a smooth limit volume. At extraordinary vertices, the authors supply strong experimental evidence that the scheme also converges to a smooth limit volume. The scheme automatically produces reasonable rules for non-nianifold topology and can easily be extended to incorporate boundaries and embedded creases expressed as Catmull-Clark surfaces and
Pettie, Seth and Vijaya Ramachandran. "Computing Undirected Shortest Paths with Comparisons and Additions." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-12. April 2001. 15 pages.
We study undirected shortest paths problems in a natural model of computation, namely one which gives us two numerical operations: comparisons and additions. This is the model assumed by such standards as Dijkstra's algorithm, the Bellman-Ford algorithm, and the Floyd-Warshall algorithm, and is the usual model for proving lower bounds on shortest path problems. We present an algorithm for undirected single source shortest paths (SSSP) with arbitrary real edge weights which performs O(SSSP(m, n) + m log a(m, n) +n log log r) comparisons and additions. Here SSSP is the comparison-addition complexity of the problem, r the ratio of the maximum-to-minimum edge length, and a Tarjan's inverse-Ackermann function. By the usual convention, m and n are the number of edges and vertices respectively. Our algorithm is implementable on a pointer machine with time complexity O(ma (m, n) + n log log r). This represents an improvement over Dijkstra's algorithm so long as r is less than 2 n o(1). For the undirected all pairs shortest paths (APSP) problem we present an algorithm that runs in time O(mna(m,n) while performing O(mn log a,(m,n)) comparisons and additions. This time bound improves on the best results known for this problem when the input graph is sparse, i.e., when m = o(n log n). Our algorithms make extensive use of the graph's minimum spanning tree in order to compute SSSP quickly. and our approach is based on a refinement of Thorup's component hierarchy data structure, which was developed under the more powerful RAM model.
Venkataramani, Arun, Praveen Yalagandula, Ravindranath Kokku, Sadia Sharif, and Mike Dahlin. "The Potential Costs and Benefits of Long-term Prefetching for Content Distribution." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-13. June 2001. 22 pages.
This paper examines the costs and potential benefits of long-term prefetching for content distribution. In contrast with traditional short-term prefetching, in which caches use recent access history to predict and prefetch objects likely to be referenced in the near future, long-term prefetching uses long-term steadystate object access rates and update frequencies to identify objects to replicate to content distribution locations. Compared to demand caching, long-term prefetching increases network bandwidth and disk space costs but may benefit a system by improving hit rates. Using analytic models and trace-based simulations, we examine several algorithms for selecting objects for long-term prefetching. We find that although the web's Zipf-like object popularities makes it challenging to prefetch enough objects to significantly improve hit rates, systems can achieve significant benefits at modest costs by focusing their attention on long-lived objects.
Warshaw, Lane Bradley. "Facilitating Hard Active Database Applications." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-14. May 2001. 161 pages.
Active database technology enhances traditional databases with rules that are executed in response to database events. Tills enhancement promises exceptional returns. Useful applications of the technology include view maintenance, workflow, and real-time decision control systems. Unfortunately, penetration of active databases has largely been restricted to simple rule systems. This narrowed focus can be attributed to all explicit connection of the active rules to the underlying concurrency control system. Although tills explicit Connection provides a level of flexibility, it becomes semantically intractable in more complex applications. Furthermore, rule execution is computationally intensive. Since rules spawn the execution of many queries over the contents of the database. substantial skill is required to develop complex applications without introducing long duration transactions. This dissertation addresses three issues surrounding application development that inhibits the feasibility of active databases. First, a quantitative evaluation is performed on the semantics of VenusDB, a modular active database Ianguage that executes within the nested transaction model. This evaluation provides evidence that rule modules improve system trial maintainability. Second, the most general contribution of this dissertation is the identification and study of Log Monitoring Applications (LMAs). LMAs are expert system applications that analyze logs maintained in a database. This dissertation develops the formal execution semantics and correctness proofs of concurrency schemes for applications within the LMA class. The results show that only a minimal number of coupling modes are necessary for the database integration of hard rule systems obeying the LMA restrictions. Third, the architecture and evaluation of an active database optimizer is presented. This optimizer uses database statistics to optimize rules as well as suggest physical schema optimizations. The optimizer is integrated within VenueDB to improve system scalability.
Srinivasan, Sridhar. "An Inductive Solution to a Domino Tiling Problem." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-15. May 2001. 2 pages.
An inductive method of covering a mutilated chessboard (with two cells of opposite colors removed) with 2 X 1 dominoes is shown.
Pacheco, Carlos. "Reasoning about TLA Actions." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-16. May 2001. 196 pages.
We use the ACL2 theorem prover to verify invariants of a distributed algorithm specified in TLA (Temporal Logic of Actions). The algorithm, Disk Synod, achieves consensus among a set of processors communicating through disks. We discuss the translation of TLA specifications into a finite set theory framework in ACL2, as well as the proof of two invariant properties of Disk Synod.
Mettu, Ramgopal R. and C. Greg Plaxton. "Optimal Time Bounds for Approximate Clustering." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-17. May 2001. 18 pages.
We give randomized constant-factor approximation algorithms for the k-median problem and an intimately related clustering problem. The input to each of these problems is a metric space with n weighted points and an integer k, 0 < k < = n. For any such input, let Rd denote the ratio between the maximum and minimum nonzero interpoint distances, and let Rw denote the ratio between the maximum and minimum nonzero point weights. We analyze the running time of our algorithms in terms of the parameters n, k, Rd and Rw. We prove that over a wide range of parameter settings, the complexity of both problems is Theta(nk).
Hanson, Heather. "Static Energy Reduction Techniques in Microprocessor Caches." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-18. May 2001. 52 pages.
Managing power and energy consumption has become a primary consideration for microprocessor design. This report examines the effect of technology scaling on static power and energy dissipation and evaluates three techniques to reduce static energy in primary and secondary microprocessor caches. We examine the energy and performance tradeoffs associated with each technique and represent the leakage-reduction configurations that minimize the energy-delay product. Our experimental results show that in the best case, the energy-delay product is reduced by 2% in the level-1 instruction cache, 7% in the level-1 data cache, and a factor of 50 in the level-2 unified cache. This technical report is an updated edition of a Masters Report submitted in May, 2001 by Heather Hanson to the Department of Electrical and Computer Engineering at The University of Texas at Austin.
Gunnels, John A. and Robert A. van de Geijn. "Developing Linear Algebra Algorithms: A Collection of Class Projects." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-19. May 2001. 206 pages.
In this document we present a new approach to developing sequential and parallel dense linear algebra libraries. Given a linear algebra operation, we demonstrate how formal techniques can be used to derive a family of algorithms. Due to the systematic approach used, correctness of the algorithms can be asserted. Next, we introduce a library of routines that hides the manipulation of indices and allows the code to mirror the algorithms as they are naturally presented. The idea is that by having the code mirror the algorithm, the opportunity for introducing indexing errors is minimized. Thus, the correctness assertions regarding the algorithms carry over to the implementations. The philosophy behind the approach is that one should start by systematically deriving the algorithms. The recipe for derivation is given in Chapter 2. Moreover, this derivation should be carefully documented. To facilitate this, we provide a set of LaTeX macros, given in an appendix. Once one or more algorithms have been developed, they are translated to implementations using a library of C routines, as part of the Formal Linear Algebra Methods Environment (FLAME). This library allows the code to look much like the algorithms as written using LaTeX. For all examples in the report we demonstrate that high performance can be attained on an Intel Pentium (R) III processor. We illustrate the techniques with a large number of case studies, most of which were carried out by teams of computer science undergraduate students as part of a class taught in Spring 2001 at UT-Austin titled High-Performance Parallel Algorithms. The names of the members of the teams are given as the authors of the chapter on the operation assigned to that team. Thus we show that the approach makes the development and implementation of high-performance sequential and parallel algorithms for dense linear algebra operations accessible to novices. It is important to realize that this document is meant to capture the progress of the project during a single semester. Thus, the document is incomplete in many ways. For example, the review of the literature is sparse at best. Many sections and chapters are missing or incomplete. Typographical errors are scattered throughout. For each operation, only a few algorithms are derived and implemented. The performance results are limited to a single architecture. While high-performance parallel implementations were also created using our Parallel Linear Algebra Package (PLAPACK), the discussion of these implementations did not make it into the document. It is our hope that there is value in this document despite these shortcomings.
Chandra, Bharat Baddepudi. "Web Workloads Influencing Disconnected Service Access (Masters Thesis)." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-20. May 2001. 82 pages.
Disconnected operation, in which a client accesses a service without relying on network connectivity, is crucial for improving availability, supporting mobility, and providing responsive performance. Because many web services are not cachable, disconnected access to web services may require mobile service code to execute in client caches. Furthermore as web workloads access large amounts of data, disconnected access must require prefetching data that will later be used on demand. Unfortunately, this can significantly increase the total amount of data fetched by a service. In this thesis we present an argument thaat aggressive prefetching is feasible. A study of the web workload characteristics at typical clients suggests a need for a flexible, automated resource management system to prevent denial of service attacks by these potentially unreliable mobile service codes that prefetch at the clients. We therefore present and evaluate a Popularity based resource management policy for such an environment.
Yang, Yang Richard, Steve Li, X. Brian Zhang, and Simon S. Lam. "Reliable Group Rekeying: A Performance Analysis." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-21. June 2001. 48 pages.
In secure group communications, users of a group share a common group key. A key server sends the group key to authorized new users as well as performs group rekeying for group users whenever the key changes. In this paper, we investigate scalability issues of reliable group rekeying, and provide a performance analysis of our group key management system (called keygem) based upon the use of key trees. Instead of rekeying after each join or leave, we use periodic batch rekeying to improve scalability and alleviate out-of-sync problems among rekey messages as well as between rekey and data messages. Our analyses show that batch rekeying can achieve large performance gains. We then investigate reliable multicast of rekey messages using proactive FEC. We observe that rekey transport has an eventual reliability and a soft real-time requirement, and that the rekey workload has a sparseness property, that is, each group user only needs to receive a small fraction of the packets that carry a rekey message sent by the key server. We also investigate tradeoffs between server and receiver bandwidth requirements versus group rekey interval, and show how to determine the maximum number of group users a key server can support.
Gunnels, John A., Greg M. Henry, and Robert A. van de Geijn. "High-Performance Matrix Multiplication Algorithms for Architectures with Hierarchical Memories." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-22. June 2001. 12 pages.
During the last half-decade, a number of research efforts have centered around the development of software for generating automatically tuned matrix multiplication kernels. These include the PHiPAC project and the ATLAS project. The software products of both projects employ brute force to search a parameter space for blockings that accommodate multiple levels of memory hierarchy. We take a different approach. Using a simple model of hierarchical memories we employ mathematics to determine a locally-optimal strategy for blocking matrices. The theoretical results show that, depending on the shape of the matrices involved, different strategies are locally-optimal. Rather than determining a blocking strategy at library generation time, the theoretical results show that ideally one should pursue a heuristic that allows the blocking strategy to be determined dynamically at run-time as a function of the shapes of the operands. When the resulting family of algorithms is combined with a highly optimized inner-kernel for a small matrix multiplication, the approach yields performance that is superior to that of methods that automatically tune such kernels. Preliminary results, for the Intel Pentium (R) III processor, support the theoretical insights.
Desikan, Rajagopalan, Doug Burger, Stephen W. Keckler, and Todd Austin. "Sim-alpha: a Validated, Execution-Driven Alpha 21264 Simulator." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-23. 2001. 18 pages.
Perez-Bergquist, Andres Santiago. "Applying ESP and Region Specialists to Neuro-Evolution for Go." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-24. May 2001. 23 pages.
Go is one notable board game where computer competence still trails behind that of human experts. In the past, neural-network-based approaches have shown promise. In this paper, the ESP variant of the SANE neuro-evolution algorithm was applied to go, and an alternate network architecture featuring subnetworks specialized for certain board regions was implemented. ESP produced simpler networks that performed just as well as the more complex ones produced by SANE in other studies. Having region-specialist subnetworks improved the already great performance marginally. However, both the simple network and the network with specialists failed to scale up to board sizes larger than 7x7.
Pettie, Seth and Vijaya Ramachandran. "Minimizing Randomness in Minimum Spanning Tree, Parallel Connectivity, and Set Maxima Algorithms." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-25. July 2001. 21 pages.
There are several fundamental problems whose deterministic complexity remains unresolved, but for which there exist randomized algorithms whose complexity is equal to known lower bounds. Among such problems are the minimum spanning tree problem, the set maxima problem, the problem of computing connected components and (minimum) spanning trees in parallel, and the problem of performing sensitivity analysis on shortest path trees and minimum spanning trees. However, while each of these problems has a randomized algorithm whose performance meets a known lower bound, all of these randomized algorithms use a number of random bits which is linear in the number of operations they perform. We address the issue of reduucing the number of random bits used in these randomized algorithms. For each of the problems listed above, we present randomized algorithms that have optimal performance but use only a polylogarithmic number of random bits; for some of the problems our optimal algorithms use only log* n random bits. Our results represent an exponential savings in the amount of randomness used to achieve the same optimal performance as in the earlier algorithms. Our techniques are general and could likely be applied to other problems.
Klingner, Jeff. "Visualizing Sets of Evolutionary Trees." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-26. May 2001. 19 pages.
One of the problems with current methods for phylogenetic reconstruction is the large number of equally parsimonious trees that are often found during a tree search; understanding these large sets of trees is a challenge for biologists. I explored the utility of a data visualization technique in creating 2D and 3D images of tree sets in order to improve researchers' understanding of the sets. I used multidimensional scaling based on Robinson-Foulds inter-tree distances to construct the visualizations. Direct visualization of taxa differences was also explored. I found that structure in the tree sets was reflected in the visualizations. Visual clustering in our pictures corresponds to islands of phylogenetic trees in the set and also reveals additional structure. Direct visualization of taxa differences provides a good alternative to displaying divergence with branch lengths and may be useful in a divide-and-conquer approach to phylogenetic reconstruction. I integrated all of the computational steps needed for building the visualizations into a module for the phylogeny software package Mesquite.
Porter, George. "A Commuting Diagram Relating Threaded and Non-threaded JVM Models." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-27. July 2001. 68 pages.
We establish a commuting diagram that relates two models of the Java Virtual Machine (JVM). The first model, M3, supports much of Java, including classes, objects, and dynamic method resolution. The second model, M4, builds upon M3 by adding threads, monitors, and synchronized methods. We describe a theorem, Main, that asserts that running certain "single-threaded" states on M4 is equivalent to transforming those states to the domain of M3, running the transformed state there, and translating the result back to the domain of M4. We define the criteria we use to determine if the resulting states are equivalent, and we define our notion of "single-threaded". We then discuss a few lessons learned during the development of Main.
Guyer, Samuel Z. and Calvin Lin. "A Case Study in Exploiting Layers to Optimize Scientific Software." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-28. 10 pages.
This paper presents a case study in improving the performance of layered scientific software using library-level optimization. We augment our previous work to include a notion of layers, and apply the technique to the three layers that make up the PLAPACK parallel linear algebra library -- a global application level, an internal layer, and an MPI message passing layer. We show how significant performance improvements of 10% to 180% for large matrices and 36% to 600% for small matrices are possible for four PLAPACK applications. Our approach works because it first exploits layer boundaries to facilitate high-level program analysis and optimization, and then systematically dissolves layer boundaries to expose new optimization opportunities. This work is presented in the context of the Broadway compiler system, which uses an annotation language to capture semantic information about the abstractions present in software libraries.
. "REPORT NEVER PUBLISHED." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-29.
Yalagandula, Praveen, Amit Garg, Mike Dahlin, Lorenzo Alvisi, and Harrick Vin. "Transparent Mobility with Minimal Infrastructure." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-30. July 2001. 14 pages.
In this paper, we introduce VIP -- a virtual IP layer -- that applies the principle of virtual addressing to Internet naming. VIP's goal is to support mobility in a way that is incrementally deployable and that requires little installation or configuration effort. VIP achieves this goal by following two design principles (1) transparent mobility: the system virtualizes the IP level of the protocol stack -- the "neck (of the protocol hourglass" to avoid modifying higher-level network protocols and applications, and (2) minimal infrastructure: the system takes advantage of and minimizes changes to existing network infrastructure. In particular, VIP relies on widely-deployed infrastructure -- DHCP for dynamic IP assignment, Dynamic Secure DNS for updating name-to-IP mappings, and IPSec for secure communication -- rather than requiring deployment of new translation infrastructure. Overall, we find that VIP efficiently supports transparent mobility in a way that an individual
Gorinsky, Sergey and Harrick Vin. "Effairness: A Metric for Congestion Control Evaluation in Dynamic Networks." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-31. August 2001. 12 pages.
This paper examines the problem of congestion control evaluation in dynamic networks. We determine a source of deficiencies for existing metrics of congestion control performance - the existing metrics are defined with respect to ideal allocations that do not represent short-term efficiency and fairness of network usage in dynamic environments. We introduce the concept of an effair allocation, a dynamic ideal allocation that specifies optimal efficiency and fairness at every timescale. This concept has a general applicability; in particular, it applies to networks that provide both unicast and multicast services. Another desirable property of the effair allocation is its dependence on the communication needs and capabilities of applications. We design an algorithm that accounts for network delays and computes the effair allocation as a series of static ideal allocations. Using the notion of effair allocation as a foundation, we define a new metric of effairness that shows how closely the actual delivery times match the delivery times under the effair allocation.
Venkatachalam, Muthaiah, Jasleen Kaur, and Harrick M. Vin. "End-to-end Model for a Flow in the Internet." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-32. August 2001. 16 pages.
We develop an end-to-end model for packet inter-arriival times of flows in the Internet. Our model illustrates that under asymptotic conditions of high network utilization, (1) packet inter-arrival times of flows become heavy-tailed after they traverse a largeenumber of hops, and (2) the aggregate of such flows is a long-range dependent self-similar process. We validate our model through extensive simulations and derive the region of applicability-with respect to non-asymptotic settings of network utilization, heterogeneity in traffic composition, and number of hops that a flow traverses-of our model. We find that for flows that contribute significant amount (approx. equal to 10%) to the cumulative bit rate of the aggregate, the observations yielded by the model hold at relatively low levels of network utilization (30-40%), small number of network hops (4-6), and moderate levels of heterogeneity in packet sizes and bandwidth requirements of flows.
Kumar, Alok, Jasleen Kaur, and Harrick M. Vin. "End-to-end Proportional Loss Differentiation." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-33. February 2001. 21 pages.
Serrvice differentiation is at the core of designing- next- generation Internet. In this paper, we present a buffer management framework for achieving end-to-end proportional loss differentiation in networks. There are two main facets of our buffer management framework. First, it decouples the decisions of when to drop a packet from which packet to drop. This allows the framework to utilize existing single-class buffer management techniques such as RED-to determine when to drop a packet; in fact, when instantiated with RED, the framework extends the primary advantages of single-class RED-namely, early notification of congestion and maintenance of average buffer occupancy at low, configurable levels-to a multi-class workload. Second, at each router, the framework governs the selection of which packet to drop based on the number of packets of a flow transmitted by its source, rather than the number of packets that arrive at a router. The framework achieves this by encoding information about the losses observed by a flow at a router in packet headers. This allows the framework to provide end-to-end proportional loss differentiation, unlike most existing schemes that provide loss differentiation only on a per-hop basis. We evaluate the efficacy of this approach under various network settings. We describe an implementation of our framework and discuss its complexity.
Xie, Fei, Vladimir Levin, and James C. Browne. "Model Checking for an Executable Subset of UML." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-34. September 2001. 10 pages.
This paper presents an approach to model checking software system designs specified in an executable subset of UML, xUML. The approach is enabled by the execution semantics of xUML and is based on automatic translation from xUML to S/R, the input language of the COSPAN model checker. Translation algorithms are defined and described, which cover class models, state models of classes, actions associated with states in state models, execution semantics, etc. The translation attempts to reduce the state space of the resulting S/R model that is to be verified by COSPAN. An xUML level logic for specifying properties to be verified is defined. Automated support is provided for translating properties specified in the logic into S/R notation and mapping error traces generated by COSPAN to xUML representation. The approach is illustrated by some results from a verification study of a simplified robot control system.
Quintana-Orti, Enrique S. and Robert A. van de Geijn. "Formal Derivation of Algorithms: The Triangular Sylvester Equation." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-35. September 2001. 29 pages.
In this paper we apply a formal approach for the derivation of dense linear algebra algorithms to the triangular Sylvester equation. The result is a large family of provably correct algorithms. By using a coding style that reflects the algorithms as they are naturally presented, the correctness of the algorithms carries through to the correctness of the implementations. Analytically motivated heuristics are used to subsequently choose members from the family that can be expected to yield high performance. Finally, we report performance on the Intel (R) Pentium III processor that is superior to that reported previously in the literature for this operation
Desikan, Rajagopalan, Stephen W. Keckler, Doug Burger, and Todd Austin. "Assessment of MRAM Technology Characteristics and Architectures." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-36. 2001. 11 pages.
Pettie, Seth, Vijaya Ramachandran, and Srinath Sridhar. "Experimental Evaluation of a New Shortest Path Algorthm." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-37. December 2001. 13 pages.
We evaluate the practical efficiency of a new shortest path algorithm for undirected graphs which was developed by the first two authors. This algorithm works on the fundamental comparison-addition model. Theoretically, this new algorithm out-performs Dijkstra's algorithm on sparse graphs for the all-pairs shortest path problem, and more generally, for the problem of computing single-source shortest paths from (1) different sources. Our extensive experimental analysis demonstrates that this is also the case in practice. We present results which show the new algorithm to run faster than Dijkstra's on a variety of sparse graphs when the number of vertices ranges from a few thousand to a few million, and when computing single-source shortest paths from as few as three different sources.
Liu, Huaiyu and Marian Nodine. "On Applying Mobile Agents to Network Management." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-38. October 2001. 13 pages.
The inscalability and inflexibility problems suffered by the traditional Network Management System(NMS) have been addressed in many research projects. Mobile agent technology is a promising approach to the design of a distributed NMS. In this report, we first investigated the benefits of applying mobile agents to network management. After evaluating several popular mobile agent platforms, we selected the JADE system and upon it, designed a general architecture of a NMS based on mobile agents.
Beg, Mirza. "A Memory Accounting Interface for The Java Programming Language." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-40. October 2001. 8 pages.
Widespread use of the Internet infrastructure for deploying services creates new issues and raises serious concerns regarding the security of their execution environment. Ideas of employing dynamic distributed systems for mounting e-services on the web are gaining strength. The main idea behind their proposed design is the use of distributed extensions. This permits execution of un-trusted service code at clients, content distribution service machines or proxies, in order to make the dynamic services more effective. Over the past few years Java has surfaced as an attractive option for constructing web services and programming their execution environment. Java provides the capability of automatic memory operations but fails to
provide an accounting interface. In order to make the services more secure the language needs a robust resource accounting interface. This paper discusses the design and implementation of a memory accounting interface as a key component of resource management. We discuss the design, implementataion and issues regarding the implementation of this system. To consider its practical application, we evaluate the performance and accuracy of this system.
Barbancon, Francois and Daniel Miranker. "Compiling Higher Order Federating Queries For Execution on Relational Systems." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-41. February 2001. 25 pages.
Higher order languages extend traditional database query languages. They allow quantification of meta-variables over schema labels: relations and attributes. They were developed to federate heterogeneous databases and show promise in providing global information services in DBMS systems. The primary motivation for that work is the availability on the network of an increasing amount of data sources, with emerging exchange standards like XML. This paper develops a method to compile higher order queries into a first order representation. The number of queries output by compilation, are in the worst case, a quadratic function of the data size. By leveraging existing primary indexes in database tables, exponential complexity can be avoided and existing join optimizers can handle expressions with a large number of meta-variables. The resulting queries may be executed on existing database systems without modification. This guarantees system independence, practical in Internet database
Barbancon, Francois and Daniel Miranker. "An Architecture for Building Federated Databases by Example." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-42. November 2001. 11 pages.
We define an architecture for an easy to use graphical system to query data from multiple heterogeneous sources. The contemporary development of computer networks and relational database systems immediately revealed the difficulties of integrating data from multiple heterogeneous sources. After nearly 30 years of extensive research efforts and hundreds of commercially developed tools, this integration remains a complex and labor intensive tasks. In an informal proof, Krishnamurthy, Litwin and Kent demonstrated that merging data from multiple sources requires higher order syntactic constructs to overcome schematic inconsistencies across data sources. They deduce that first order relational languages such as SQL or Datalog can be extended with a higher order syntax. Then become expressive enough to describe the necessary class of transformation. We put forth an architecture which directly contemplates the issues of data integration with respect to the precise nature of the schematic inconsistencies that must resolved. The primary focus is on designing a system in a way that a naive database user may specify and effect a solution.
Gunnels, John Andrew. "A Systematic Approach to the Design and Analysis of Linear Algebra Algorithms." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-44. December 2001. 131 pages.
Over the last two decades, much progress has been made in the area of the high-performance sequential and parallel implementation of dense linear algebra operations. At what time can we confidently state that we truly understand this problem area and what form might evidence in support of this assertion take? It is our thesis that if we focus this question on the software architecture of libraries for dense linear algebra operations, we can claim to have reached the point where, for a restricted class of problems, we understand this area. In this dissertation, we provide evidence in support of this assertion by outlining a systematic and partially automated approach to the derivation and high-performance implementation of a large class of dense linear algebra operations. We have arrived at a conclusion that the answer is to apply formal derivation techniques from Computing Science to the development of high-performance linear algebra libraries. The resulting approach has resulted in an aesthetically pleasing, coherent code that facilitates performance analysis, intelligent modularity, and the enforcement of program correctness via assertions. In this dissertation, we illustrate this observation by looking at the development of the Formal Linear Algebra Methods Environment (FLAME) for implementing linear algebra algorithms. We believe that traditional methods of implementation do not reflect the natural manner in which an algorithm is either classified or derived. To remedy this discrepancy, we propose the use of a small set of abstractions that can be used to design and implement linear algebra algorithms in a simple and straightforward manner. These abstractions may be expressed in a script language that can be compiled into efficient executable code. We extend this approach to parallel implementations without adding substantial complexity. It should also be possible to translate these scripts into analytical equations that reflect their performance profiles. These profiles may allow software designers to systematically optimize their algorithms for a given machine or to meet a particular resource goal. Given the more systematic approach to deriving and implementing algorithms that is facilitated by better abstraction and classification techniques, this sort of analysis can be shown to be systematically derivable and automated.
Berger, Emery D., Benjamin G. Zorn, and Kathryn S. McKinley. "Reconsidering Custom Memory Allocation." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-45. December 2001. 10 pages.
Many programmers use custom memory allocators hoping to achieve performance improvements. This first in-depth study examines eight applications that use custom allocators. Surprisingly, for six of these applications, a state-of-the-art general-purpose allocator performs as well as or better than the custom allocators. The two exceptions use regions, which deliver higher performance (up to 44% faster). Regions also reduce programmer burden and help eliminate a source of memory leaks. We show, however, that the inability of programmers to free individual objects within regions can lead to a substantial increase in memory consumption (up to 230% more). To eliminate this excessive memory consumption, we develop the Reap extended general-purpose memory allocator, which combines region semantics with individual object deletion. Reap outperforms similar allocators and comes close to matching region performance while providing the potential for reduced memory consumption. We thus demonstrate an implementation of an extended memory allocation interface that eliminates the need for most custom memory allocators and the programmer effort needed to build and maintain them.
Henry, Greg. "Flexible High-Performance Matrix Multiply via a Self-Modifying Runtime Code." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-46. December 2001. 14 pages.
With the advent of architectures with multiple levels of memory hierarchies, the quest for high performance implementation of commonly used linear algebra operations has become progressively more complex. Fortunately, recent research has shown that a large class of such operations can be implemented in a relatively portable fashion provided a high-performance matrix-matrix multiplication routine is available for a given architecture. More recently yet it has been shown that the matrix-matrix multiplication itself can be implemented in a portable fashion provided a high-performance "inner kernel" is available. This inner kernel performs the matrix-matrix multiplication of small submatrices in such a way that data movement between caches and registers is carefully amortized. In recent years, approaches like those pursued in the ATLAS and PHiPAC projects have used automatic generation, at build time, of matrix-matrix multiply inner kernels. In this paper, we present the idea of using an inner kernel that, at run-time, is self-modifying. The advantages of using a self-modifying inner kernel at run-time include performance gains, minimizing the amount of code to maintain, and a reduction in the memory footprint of the executable. In addition to a thorough discussion of the issues affecting the inner kernel we present performance results for an implementation on the Intel Pentium (R) III processor.
Ahmed, Nabeel. "An Efficient Disk Resource Management Mechanism for Scalable Disconnected Access to Web Services." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-48. January 2002. 11 pages.
This paper examines the importance of requiring a disk resource management mechanism for disconnected services and presents a robust system that embodies several features that are required of such a disconnected framework. Disconnected services in which clients access services in degraded mode (i.e without relying on network connectivity) are i mportant for providing greater service availability to potential clients. Because much of the content that requires connectivity is not cacheable, there is a trend towards downloading code that is "un-trusted", one that may place limitless demands on the resources available to the client. Although such resource management has a broad area of application, this paper takes a look at disk resource management for write buffering, where data are stored for disconnected services with the intent that they will be evacuated at a later time. In this paper we explore a per-service popularity algorithm to address the write buffering problem effectively. In doing so, we present a system that implements an 'automatic' disk resource management policy and examine how it performs relative to the more rudimentary techniques already in use. As a result, we discuss how our system provides greater service availability by allowing flexibility in the introduction of new services while also providing greater disk access to existing ones.
Greer, Brian. "Numerical Optimization with Neuroevolution." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-49. December 2001. 10 pages.
Neuroevolution techniques have been successful in many sequential decision tasks such as robot control and game playing. This paper aims at establishing whether they can be useful in numerical optimization more generally, by comparing neuroevolution to Linear Programming in a manufacturing optimization domain. It turns out that neuroevolution can learn to compensate for uncertainty in the data and outperform Linear Programming when the number of variables in the problem is small and the required accuracy is low, but the current techniques do not (yet) provide an advantage in problems where many variables must be optimized with high accuracy.
Jiménez, Daniel A. and Calvin Lin. "Neural Methods for Dynamic Branch Prediction." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-50. 2001. 78 pages.
This paper presents a new method for branch prediction that is highl.y accurate. The key idea is to use one of the simplest possible neural methods, the perceptron as an alternative to the commonly used two-bit counters. The source of our predictor's accuracy is its ability to use long history lengths, because the hardware resources for our method scale linearly, rather than exponentially, with the history length. We describe two versions of perceptron predictors, and we evaluate these predictors with respect to five well known predictors. We show that for a 4K byte hardware budget, a simple version of our method that uses a global history achieves a misprediction rate of 1.94% on the SPEC 2000 integer benchmarks, an improvement of 53% over gshare. We also describe a globat/local version of our predictor that is 36% more accurate than the McFarling-style hybrid predictor of the Alpha 21264. Because this variant of the perceptron predictor is more accurate than Evers' multi-component predictor for hardware bbudgets of up to 256KB, we conclude that ours is the most accurate dynamic predictor currently available. To explore the.feasibility of our ideas, we provide a circuit-level design of the perceptron predictor and describe techniques that allow our complex predictor to operate quickly. Finally, we show how the relatively complex perceptron predictor can be used in modern CPUs by having it override a simpler, quicker Smith predictor providing IPC improvements of 15.8% over gshare and 5.7% over the McFarling hybrid predictor.
Sastry, Nishanth R. "Application Specific Unicast Congestion Control." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-51. December 2001. 44 pages.
Some new Internet-based applications such as streaming media cannot function well with TCP's decrease-by-half response to congestion indications from the network. However, to prevent congestion collapse, it is imperative that all applications use some form of congestion control. Furthermore, for such a mechanism to be feasible, it must converge to fairness and efficiency, just as TCP does. This thesis presents a framework that allows an application to choose an aggressive or smooth congestion response from a wide family of window-based protocols called CYRF (for Choose Your Response Function) that are designed to converge to fairness. We also give a simple rule for smooth CYRF flows to be TCP-friendly. We first derive a sufficient, condition that ensures convergence to fairness. We then present the surprising result that an application can satisfy this fairness condition arid construct a congestion response tailored to its needs by choosing from almost any pair of monotonically non-decreasing functions. Constructing a window increase policy rising a slowly increasing function results in an aggressive protocol. Similarly. a slowly increasing function in the decrease policy gives rise to smooth protocols. We characterize TCP-friendliness in steady-state and show that any smooth CYRF protocol can be TCP-friendly if the product of its window increase and decrease functions is proportional to the window size. An interesting aspect of this work is that all commonly used window-based protocols such as TCP, GAIMD, and binomial congestion control are shown to be special cases of a single family of protocols, thus providing a powerful unified framework for analyzing them. We derive most of the important results about these protocols as special cases of the results for CYRF.
Camahort, Emilio. "4D Light-Field Modeling and Rendering." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-52. Spring 2001. 186 pages.
Image-based models have recently become an alternative to geometry-based models for computer graphics. They can be formalized as specializations of a more general model, the light field. The light field represents everything visible from any point in 3D space. In computer graphics the light field is modeled as a function that varies over the 4D space of oriented lines. Early models parameterize an oriented line by its intersection with two parallel planes, a parameterization that was inspired by holography. In computer graphics it introduces unnecessary biases that produce a rendering artifact called the disparity problem. We propose an alternative isotropic parameterization, the direction-and-point parameterization (DPP). We compare it to other parameterizations and determine whether they are view-independent, that is, invariant under rotations, translations and perspective projections. We show that no parameterization is view-independent, and that only the DPP introduces a single bias. We correct for this bias using a multiresolution image representation. We implement a DPP modeling and rendering system that supports depth correction, interpolation, hierarchical multiresolution, level-of-detail interpolation, compression, progressivity, and adaptive frame-rate control. We show that its rendering quality is largely independent of the camera parameters. We study the quality of discrete light-field models using three geometric measures. Two quantify discretization errors in the positional and directional parameters of light field. The third measure quantifies pixelation artifacts. We solve three open problems: (i) how to optimally choose planes for two-plane and DPP models, (ii) where to position the discretization windows within those planes, and (iii) how to choose optimal window resolutions. For a given amount of storage, we show that DPP models give the best overall quality representation for 4D light-field modeling and rendering. We demonstrate the application of 4D light-field models to holography. We generate a holographic stereogram based on both planar and isotropic representations. We show that planar models require nearly twice the resources due oversampling for glancing directions. Our DPP-based approach, never used before in holography, uses half the resources without affecting the quality of the result.
Amla, Nina. "Efficient Model Checking for Timing Diagrams." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-53. May 2001. 144 pages.
Marshall, Dana T.. "The Exploitation of Image Construction Data and Temporal/Image Coherence in Ray Traced Animation." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-54. May 2001. 120 pages.
This dissertation proposed an elegant and fast method that speeds the calculation of ray traced animated scenes constructed of convex objects by a combination of temporal and image coherence.
Cheng, Pericles Leng. "SCHEDULING AND SECURITY FOR THE HYPERTEXT TRANSFER PROTOCOL." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-56. Spring 2001. 40 pages.
The Hypertext Transfer Protocol is used to facilitate the communication between "clients" (i.e. computers used to view information) and "servers" (i.e. computers used to store information). The communication between a client and server proceeds in transactions: the client sends a request message to the server and then the server sends back a reply that contains the requested information. In this thesis, we identify two problems associated with the Hypertext Transfer Protocol and propose solutions for them. The first problem is associated with pipelined HTTP request messages. Pipelining means that more than one request is sent to the server without waiting for a reply. If a connection failure occurs then the client sends all the requests again. Sometimes there is a possibility that the result or side effects of executing the same requests again may change. To eliminate this problem we need to check whether a request keeps the sequence idempotent, that is, the sequence can be executed again without changing the result or it's side effects. As a solution we introduce a look-ahead scheduler, which pipelines HTTP requests according to their idempotency. If a connection failure occurs then we know that the sequence send to the server again is idempotent and the result is always the same. The second problem is associated with the insecurity of HTTP cookies, a mechanism used to keep the state of a session. A session is a sequence of related request-reply transactions between a client and a group of servers. During a session, the server needs to maintain the current state of that session. For example, the server may need to maintain a list of all information that the client has requested so far in the session. The server can do this by utilizing cookies. A cookie is a small piece of information that is created by the server to contain the current state of the session. It is sent to the client in the reply and it is stored in the client's computer. When the client initiates the next transaction, the cookie that was stored in the computer is attached to the request before it is sent to the server. When the server receives the request, it uses the attached cookie to remember the current state of the session before it processes the request. (In an Internet store's shopping cart, for example, the server can save the current state of the shopping cart, i.e. items selected by the customer, in a cookie and store it in the client's computer. When the customer visits the store again at a later date, the cookie is sent to the server and his previously saved shopping cart is restored.) In recent years, the use of cookies became a problem since they were used in malevolent ways that jeopardized the privacy, integrity and anonymity that were offered to the individual users of the World Wide Web. The problem arises from the fact that cookies are stored on the client computer unencrypted and they are transferred over the Internet with no security. We analyze the current use of Internet cookies and the security problems that are related with them. Later we suggest ways in which Internet cookies can be implemented so that they are more secure.
Shuja, Khawaja Usman. "Network Resource Management." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-57. March 2002. 10 pages.
This paper suggests a receiver-based scheduler to limit receiving data from other services. We implement Start-Time Fair Queuing in Active Names to schedule incoming data and examine its performance. The fundamental challenge lies in overcoming the difficulties to control receiving data. It is relatively easy to schedule sends, as the sender can control its buffer. But in receiving we have to limit reception from other sources to allow fair allocation to all the processes. Data reception can be controlled at three levels a) sender, b) router and c) receiver level. Under normal circumstances all these options can be employed but the problem arises when the sender is un trusted as it can consume bandwidth and cause denial of service attacks. Even if the intent of the sender is not to consume the bandwidth, the nature of the network traffic may cause it to be bursty. Unpredictable behavior of bursty senders makes the network resource management harder. We have built a receiver-based scheduler that distributes bandwidth fairly using Start Time Fair Queuing scheduler to schedule receiving data from steady senders and achieves up to 92% efficiency under bursty conditions.
Samoladas, Vasilis. "On Indexing Large Databases for Advanced Data Models." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-58. August 2001. 191 pages.
In the last decade, the relational data model has been extended in nu- merous ways, including geographic information systems, abstract data types and object models, constraint and temporal databases, and on-line analytical processing. We study the indexing requirements of these data models. In many cases, these requirements are ful lled by ecient techniques for multidimen- sional range search. Previous techniques for multidimensional range search, such as the R-tree and its variants, are based on ad hoc assumptions on the na- ture of the workloads they index, and have been known to su er from reduced scalability and robustness. We adopt an alternative approach; our study fo- cuses on techniques that provide worst-case performance guarantees, and thus overcome these deficiencies.
Noorani, Nizar. "Comparison of a Simulation System in Haskell vs. Java." The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-01-60. December 20, 2001. 24 pages.
This paper examines the differences involved in implementing a program in an imperative language versus a pure functional language and discusses the advantages and disadvantages of these differences. In particular, this paper discusses the design of a simulation system and its implementation in the Object-Oriented language Java and the pure functional language Haskell. It will then examine the two implementations and make appropriate conclusions.
Questions to trcenter@cs.utexas.edu