Technical Report Series Computer and Information Science Research Center Department of Computer and Information Science The Ohio State University 2015 Neil Avenue, Columbus, OH 43210-1277 **********************NOTE********************* Abstracts for 1998 NOTE: some titles may be available ONLY via paper (This is noted after the title/author section.) If you have trouble accessing a file, please send email to tfletch@cis.ohio-state.edu 1998 TR30 A Delay-Optimal Quorum-Based Mutual Exclution Algorithm for Distributed Systems by Guohong Cao and Mukesh Singhal The performance of a mutual exclusion algorith is measured by the number of messages exchanged per critical section execution and the delay between successive executions of the critical section. There is a message complexity and synchronization delay trade-off in mutual exclusion algorithms. Lamport's algorithm and Ricart-Agrawal algorithm both have a synchronization delay of T (T is the average message delay), but their message complexity is O(N). Maekawa's algorithm reduces message complexity to O(the square root of N); however, it increases the synchronization delay to 2T. After Maekawa's algorithm, many quorum-based mutual exclusion algorithms have been proposed to reduce the message complexity or increase the resiliency to site and communication link failures. Since these algorithms are Maekawa-type algorithms, they also suffer from synchronization delay 2T. In this paper, we propose a delay-optimal quorum-based mutual exclusion algorithm which reduces the synchronization delay to T and still has a low message complexity of O(K) (K is the size of the quorum, which can be as low as log N). A correctness proof and a detailed performance analysis are provided. Key words: Quorum, synchronization delay, distributed mutual exclusion, fault-tolerance. TR29 Mutable Checkpoints: A New Checkpointing Approach for Mobile Computing Systems by Guohong Cao and Mukesh Singhal Mobile computing raises many new issues, such as lack of stable storage, low bandwidth of wireless channel, high mobility, and limited battery life. These new issues make traditional checkpointing algorithms unsuitable. Coordinated checkpointing is an attractive approach for transparently adding fault tolerance to distributed applications, since it avoids domino effects and minimizes the stable storage requirement. However, it suffers from high overhead associated with the checkpointing proces in mobile computing systems. Two approaches have been used to reduce the overhead: first is to minimize the number of synchronization messages and the number of checkpoints; the other is to make the checkpointing process non-blocking. These two approaches were orthogonal previously until the Prakash-Singhal algorithm [25] combined them. However, we [5] found some problems in their algorithm and proved that there does not exist a non-blocking algorithm which forces only a minimum number of processes to take their checkpoints. In this paper, we introduce the concept of "mutable checkpoint", which is neither a tentative, checkpoint nor a permanent checkpoint, to design an efficient checkpointing algorithm for mobile computing systems. Mutable checkpoints can be saved anywhere; e.g., the main memory or local disk of MHs. In this way, taking a mutable checkpoint avoids the overhead of transferring large amount of data to the stable storage at MSSs over the wireless network. We present techniques to minimize the number of mutable checkpoints. Simulation results show that the overhead of taking mutable checkpoints is negligible. Based on mutable checkpoints, our non-blocking algorithm avoids the avalanche effect and forces only a minimum number of processes to take their checkpoints on stable storage. Key words: Mobile computing, coordinated checkpointing, causal dependency, non-blocking. TR28 Summary Databases as Indexing Structures by Yuping Yang and Mukesh Singhal A new summary database (SDB) method is proposed for fast query executions in large relational databases. We use signatures to embody summary information. The join execution performance of the SDB method is better than that of the Bc tree method [7]. Query executions using the SDB method is especially fast in very large databases for queries with low join selectivity or complex queries having multiple predicates. A distinct feature of the SDB method is that to process query in a database, a full set of relational operations, including joins and/or selections, can be executed in a small SDB before the large relational database is accessed. A detailed performance comparison between the SDB and Bc tree methods is provided. The excellent performance in answering queries with low selectivity joins and complex queries in very large relational databases makes the SDB method ideal for a variety of "online" service databases and data warehouses. Key words: Database, query execution, index, summary, performance. TR27 M-Tree: An Efficient Index for Fast Execution of Conjunctive Queries by Yuping Yang and Mukesh Singhal A novel index structure, M-tree, which combines the strength of both tree-based indexes and signature files is introduced in this paper. An M-tree is used for indexing data in multiple attributes of a tabular dataset, but it is created at one attribute and its signatures are collected from several other attributes. One M-tree can replace several tree-based indexes and is much smaller than the tree-based indexes it replaces. Because signature of several attributes co-exist in each node of an M-tree, for answering conjunctive queries, accessing data through an M-tree can even be faster than accessing data through several tree-based indexes. Analyses and numerical experiments are conducted to evaluate the storage space and access speed of M-trees. Some aspects of the practical implementatino of signature method in general database environments are also considered in this paper. These include applying signature method to indexing numerical data and duplicate data. Key words: Signature, access index, ordered data, conjunctive query. TR26 Signature Cache: A Light Weight Web Cache Indexing Structure by Yuping Yang and Mukesh Singhal Current trend in Web cache research is to have Web caches sharing their contents to improve the hit ratio. High performance Web cache sharing requires use of access indexes for Web caches to reference each other. The challenges the design of access indexes for sharing Web caches face are the huge size, dynamic nature of Web cache contents, and of course, high access speed. Recently proposed summary cache scheme [9] scheme uses relatively small indexes for sharing Web caches to reference each other. We improved the summary cache scheme and propose a signature cache scheme. Instead of "repairing" existing access indexes, signature cache scheme builds new indexes to accommodate changes of Web cache contents. This scheme simplifies the maintenance of the indexes and significantly reduces the size of counters. The size of the index is further reduced by a semi-distributed index sharing mode. These improvements result in orders of magnitude reductino in the index sharing mode. These improvements result in orders of magnitude reduction in the index size as compared to the summary cache scheme. These benefits of the signature cache scheme come at a cost of slightly increased (one additional message in the worst case) resonse time as compared to that of the summary cache scheme. In applications where small size and ease of maintenance are favored over the response time, the signature cache scheme is a more attractive alternative than the summary cache scheme. Key words: Web cache, signature, distributed, index, sharing. TR25 Analysis of Programs with Exception Handling Constructs by Saurabh Sinha and Mary Jean Harrold Analysis techniques, such as control-flow, data-flow, and control- dependence, are used for a variety of maintenance tasks, including regression testing, dynamic execution profiling, and static and dynamic slicing. To be applicable to programs in languages, such as Java and C++ however, these analysis techniques should, to the extent possible, account for the effects of exception occurrences and exception-handling constructs. This paper presents techniques to construct intraprocedural and interprocedural representations on which existing techniques can be performed, and demonstrates their applicability to several maintenance tasks. TR24 A Dynamically Coupled Neural Oscillator Network for Image Segmentation Ke Chen and DeLiang L. Wang We propose a dynamically coupled neural oscillator network for image segmentation. Instead of pair-wise coupling, an ensemble of oscillators coupled in a local region is used for grouping. We introduce a set of neighborhoods to generate dynamical coupling structures associated with a specific oscillator. Based on the proximity and similarity principles, two grouping rules are proposed to explicitly consider the distinct cases of whether an oscillator is inside a homogeneous image region or near a boundary between different regions. The use of dynamical coupling makes our segmentation network robust to noise on an image, and unlike image processing algorithms no iterative operation is needed for noise removal. For fast computation, a segmentation algorithm is abstracted from the underlying oscillatory dynamics, and has been applied to synthetic and real images. Simulation results demonstrate the effectiveness of our oscillator network in image segmentation. TR23 Design and Evaluation of A High-Performance ATM Firewall Switch and Its Applications by Jun Xu and Mukesh Singhal We present the design of a value-added ATM switch that is capable of performing packet-level (IP) filtering at the maximum throughput of 2.88 Gbps per port. This firewall switch nicely integrates the IP level security mechanisms into the hardware components of an ATM switch so that most of the filtering operation is performed in parallel with the normal cell processing and most of its cost is absorbed into the base cost of the ATM switch. The firewall switch employs a novel scheme to avoid or reduce the latency caused by filtering. We analyze in detail the performance of the firewall switch in terms of the throughput and latency, and address related design issues. Applications of our firewall switch as Internet and intranet security solutions are also discussed. TR22 Boundary Detection by Contextual Nonlinear Smoothing by Xiuwen Liu, DeLiang Wang, J. Raul Ramirez In this paper we present a two-step boundary deteciton algorithm. The first step is a nonlinear smoothing algorithm which is based on an orientation-sensitive probability measure. By incorporating geometrical constraints through the coupling structure, we obtain a robust nonlinear smoothing algorithm, where many nonlinear algorithms can be derived as special cases. Even when noise is substantial, the proposed smoothing algorithm can still preserve salient boundaries. Compared with anisotropic diffusive approaches, the proposed nonlinear algorithm not only performs better in preserving boundaries but also has a non-uniform stable state, whereby reliable results are available within a fixed number of iterations independent of images. The second step is simply a Sobel edge detection algorithm without non-maximum suppression and hysteresis tracking. Due to the proposed nonlinear smoothing, salient boundaries are extracted effectively. Experimental results using synthetic and real images are provided. Keywords: Nonlinear smoothing, Contextual information, Anisotropic diffusion, Edge detection, Boundary detection, Orientation- sensitive probability. TR20 Safe Structural Conformance for Java by Konstantin Laufer, Gerald Baumgartner, and Vincent F. Russo In Java, an interface specifies public abstract methods and associated public constants. Conformance of a class to an interface is by name. We propose to allow structural conformance to interfaces: Any class or interface that declares or implements each method in a target interface conforms structurally to the interface, and any expression of the source class or interface type can be used where a value of the target interface type is expected. We argue that structural conformance results in a major gain in flexibility in situations that require retroactive abstraciton over types. Structural conformance requires no additional syntax and only small modifications to the Java compiler and optionally, for performance reasons, the virtual machine, resulting in a minor performance penalty. Our extension is type-safe: A cast-free program that compiles without errors will not have any type errors at run time. Our extension is conservative: Existing Java programs still compile and run in the same manner as under the original language definition. Finally, structural conformance works well with recent extensions such as Java remote method invocation. We have implemented our extension of Java with structural interface conformance by modifying the Java Developeers Kit 1.1.5 source release for Solaris and Windows 95/NT. We have also created a test suite for the extension. TR19 A Firewalling Scheme for Securing MPOA-based Corporate Intranets by Jun Xu and Mukesh Singhal Enterprise intranets are vulnerable not only to attacks from the Internet barbarians, but also to internal security breaches. Firewalling, typically used to control accesses to a trusted network from the Internet, is also an effective approach to secure enterprise intranets. Firewalling in traditional enterprise intranets is typically implemented as packet filtering routers sitting between different subnets to filter traffic between them. Such firewalling will not work in future ATM-based enterprise intranets that employs MPOA as the internetworking infrastructure. The reason is that in MPOA, cut-through connections intended for high-bandwidth and low-delay end-to-end communication will bypass such packet-filtering routers. So far there is no satisfactory solution to this problem. In this paper, we propose a firewalling scheme for MPOA, which is tight in security, low in cost, high in performance, and easy to manage. Based on the novel concept of "logical chokepoints", the proposed firewalling scheme does not require the existence of physical chokepoints inside the network to be secured. The proposed firewalling scheme is centrally managed so that it scales well to very large MPOA-based enterprise networks. Key Words: Security, INtranet Firewalling, MPOA, Packet Filtering, Virtual LAN. TR18 Two Medium Access Control Schemes for DS-CDMA Personal Communication Networks by Junfeng He and Ming T. Liu Code Division Multiple Access (CDMA) has become an attractive technique for media access control in Personal Communication Networks (PCN). In this paper, two MAC schemes are defined and studied for DS-CDMA PCNs, namely Preamble Signaling Access (PSA) and Minislot Signaling Access (MSA). PSA uses preamble-packet slot structure while MSA is applying mini-slot techniques to solve the problems of code assignment and MAI control. Markovian chain models have been developed to analyze the performance of these two protocols for voice-only systems as well as data-only systems. The analytical model is shown to be very close to simulation results. Based on the results obtained from the analysis, it is shown that, for many cases, MSA protocol performs better than PSA protocol, especially for voice services. Keywords: Personal Communication Network (PCN), CDMA, medium access control (MAC). TR17 Low-cost Fault-tolerance in Barrier Synchronizations by Sandeep S. Kulkarni and Anish Arora In this paper, we show how fault-tolerance can be effectively added to several types of faults in program computations that use barrier synchronization. We divide the faults that occur in practice into two classes, detectable and undetectable, and design a fully distributed program that tolerates the faults in both classes. Our program guarantees that every barrier is executed correctly even if undetectable faults occur. Via analytical as well as simulation results we show that the cost of adding fault-tolerance is low, in part by comparing the times required by our program with that required by the corresponding fault-intolerant counterpart. Keywords: fault-tolerance, multitolerance, detectable and undetectable faults, synchronization, concurrency. TR16 Profile-Based Load Balancing for Heterogeneous Clusters by M. Banikazemi, S. Prabhu, J. Sampathkumar, D.K. Panda, T.W. Page and P. Sadayappan (From the Introduction): CLuster computing is becoming increasingly popular for providing cost-effective and affordable parallel computing for day-to-day computational needs [2, 11,16]. Such environments consist of clusters of workstations connected by Local Area Networks (LANs). The possibility of the incremental expansion of clusters by incorporating new generations of computing nodes and networking technologies is another factor contributing to the popularity of cluster computing. However, this incremental expansion leads to heterogeneity in speed and communication capability of workstations, systems with different memory and cache organization, coexistence of multiple network architectures, and availability of alternative communication protocols. This is forcing the cluster computing environments to be redefined as heterogeneous clusters. TR15 Design and Verification of a Secure Electronic Auction Protocol by Srividhya Subramanian Auctions are an important and common form of commerce today. A difficult aspect of auctions is that the bidder must be present at the site of the auction. This reduces the appeal of auction and restricts the number of people who would otherwise participate in it. An auction over an electronic network is, therefore, an attractive way of conducting business. In this paper, I first present a protocol for electronic auctions between an anonymous customer and a merchant whose identity is public. Protocol interruption by involved parties, passive and active attacks by an intruder, and corruption or loss of messages in the network do not cost the merchant or the customer more than some additional computation. Furthermore, under all circumstances, the transaction is either completed (the right amount of money is exchanged for the right goods) or aborted (there is no transfer of money or goods). In other words, the protocol ensures security, atomicity, and privacy in business transactions. I next develop a logic based on the semantics of BAN-style [4] logic. Using this logic, I prove that the above properties are preserved in the presence of an intruder. Keywords: Electronic commerce, auction, security, atomicity, privacy, anonymity, verification, validation. TR14 Efficient Distributed Channel Allocation for Mobile Cellular Networks by Guohong Cao and Mukesh Singhal The performance of a distributed dynamic channel allocation algorithm is measured by the call blocking rate, the number of messages exchanged per channel acquisition, and the delay incurred in acquiring a channel. In general, there are two approaches to design a distributed channel allocation algorithms: Search and Update. Both of these approaches have advantages and disadvantages. The update approach has shorter acquisition delay and lower call blocking rate, but higher message complexity. On the other hand, the search approach has lower message complexity, but longer acquisition delay and higher call blocking rate. In this paper, we first propose a novel distributed acquisition algorithm, which has similar message complexity as the search approach and similar acquisition delay as the update approach. Then, we present a channel selection algorithm and integrate it into our distributed acquisition algorithm. By a rigorous analysis in terms of delay and message complexity, we show that our channel selection algorithm performs significantly better than the update approach [4] and the search approach [12]. Detailed simulation experiments are carried out in order to evaluate our proposed methodology. The performance of our algorithm is compared with those of the Geometric strategy [1], the Search approach [12], and the Update approach [4]. Simulation results show that our algorithm outperforms all other approaches in terms of call blocking probability under uniform as well as non-uniform traffic. Key words: Distributed channel allocation, channel borrowing, cellular network. TR13 Design of a High-Performance ATM Firewall by Jun Xu and Mukesh Singhal A router-based packet-filtering firewall is an effective way of protecting an enterprise network from unauthorized accesses. However, it will not work efficiently in an ATM network because it requires the termination of end-to-end ATM connections at a packet-filtering router, which incurs huge overhead of reassembling and dissembling packets. Few approaches to this problem have been proposed in the literature; however none of these approaches is completely satisfactory. In this paper, we present the hardware design of a high-speed ATM firewall that does not require the termination of an end-to-end connection in the middle. Compared with the traditional firewalls, this ATM firewall performs exactly the same packet-level filtering without compromising the performance and has the same "look and feel" by sitting at the chokepoint between the private and public ATM networks. It is also easy to manage and flexible to use. Keywords: High-performancre ATM firewall, TCP/IP ssecurity, Packet filtering. TR12 Design and Verification of a Secure, Atomic Transaction Execution Protocol for Electronic Commerce by Srividhya Subramanian and Mukesh Singhal Computer networks are an efficient, inexpensive, convenient and fast mode of communication and information transfer. There is widespread demand for the ability to buy and sell goods, especially electronic, using this medium. Sales over computer networks is also referred to as electronic commerce. A protocol for electronic commerce transactinos is the series of steps that two parties must follow in order to transact business successfully. Various issues arise while designing electronic commerce protocols: how can one party be prevented from disappearing with the money/goods in the middle of a transaction? How can we prevent a third party from "stealing" money from the network? All these and other problems make designing an electronic commerce protocol both challenging and interesting. In this paper, we first present a protocol for electronic commerce transactions between an anonymous customer and a merchant whose identity is public. Protocol interruption by involved parties, passive and active attacks by an intruder, and corruption or loss of messages in the network do not cost the merchant or the customer more than some additional computation. Furthermore, under all circumstances, the transaction is either completed (the right amount of money is exchanged for the right goods) or aborted (there is no transfer of money or goods). In other words, the protocol ensures anonymity, security, and atomicity in business transactions. Using a BAN-style [5] logic, we prove these properties in the presence of an intruder. We also present a protocol for electronic auctions. The auction protocol has the same properties of anonymity, security, and atomiticity as the transaction protocol. Keywords: electronic commerce, transaction, security, atomicity, privacy, anonymity, auction, verification, validation. TR11 Finding Structures in Weather Maps by Xingang Huang and Feng Zhao We describe an effective computational method for extracting structural information from spatial data sets. For instance, the structural information such as the location, shape, size, and movement about pressure cells and troughs are important for weather prdiction. We are interested in extracting these structures and representing them at aggregate levels where salient geometric features are highlighted. The computational challenge is to quantify these features at multiple levels of granularity and find them incrementally. We introduce two types of spatial adjacency relations for spatial objects and present an effective algorithm for extracting and abstracting structural objects using the relational information. An application to finding local pressure cells in the weather data sets is demonstrated. Keywords: Spatial knowledge discovery, proximity relationships, weather map analysis, spatial reasoning, computational tools and algorithms. TR10 Accessing a Medical Database using WWW-Based User Interfaces by Saurabh Sinha, S. Kirk Bowers, and Sandra A. Mamrak We have implemented a Neuro-Oncology Information System (NOIS) for researchers and other personnel engaged in brain-tumor research throughout the United States. In this paper we describe our migration of the implementation of the NOIS user interface from Oracle-based products to Java applets. Our goal in the migration was to design the interface software not only as a set of reusable objects, but also to reuse the patterns of interaction among the components by way of object-oriented frameworks. We describe in detail the design of the user interface classes and the connection objects that let Java applets communicate with the database, and we evaluate our success in meeting our design goal. Keywords and Phrases: brain-tumor research, graphical user interface design, object-oriented design, software reuse. TR08 Proactive Buffer Management for the Streamed Delivery of Stored Video by Wu-chi Feng, Brijesh Krishnaswami, and Arvind Prabhudev NOT YET AVAILABLE Many techniques have been introduced for the adaptive delivery of video across networks such as the Internet. These algorithms can react to network load by dynamically altering the quality of the video stream in real-time, either through a reduction in quality of image or frame rate. For stored video stream, however, these techniques do not take advantage of the a priori information available from the stored data. Bandwidth smoothing techniques, which are effective in reducing the resource requirements for the streamed playback of stored video, use this a priori information but cannot adapt to changes in network conditions. In this paper, we propose the proactive management of streamed stored video delivery over best effort networks like the Internet. Our proposed scheme attempts to maximize the sustained rate of the video by proactively monitoring the available bandwidth and the buffer. Our results show that the quality of video delivered to the desktop can be improved with our technique. TR07 Efficient Collective Communication on Heterogeneous Networks of Workstations by Mohammad Banikazemi, Vijay Moorthy, and Dhabaleswar K. Panda Networks of Workstations (NOW) have become an attractive alternative platform for high performance computing. Due to the commodity nature of workstations and interconnects and due to the multiplicity of vendors and platforms, the NOW environments are being gradually redefined as Heterogeneous Networks of Workstations (HNOW) environments. This paper presents a new framework for implementing collective communication operations (as defined by the Message Passing Interface (MPI) standard) efficiently for the emerging HNOW environments. We first classify different types of heterogeneity in HNOW and then focus on one important characteristic: communication capabilities of workstations. Taking this characteristic into account, we propose two new approaches (Speed-Partitioned Ordered Chain (SPOC) and Fastest-Node First (FNF)) to implement collective communication operations with reduced latency. We also investigate methods for deriving optimal trees for broadcast and multicast operations. However, generating such trees is found to be computationally intensive. It is shown that the FNF approach, in spite of its simplicity, can deliver performance with 1% of the performance of the optimal trees. Finally, these new approaches are compared with the approach used in the MPICH implementation on experimental as well as on simulated testbeds. On a 24-node existing HNOW environment with SGI workstations and ATM interconnection, our approaches reduce the latency of broadcast and multicast operations by a factor of up to 3.5 compared to the approach used in the existing MPICH implementation. On a 64-node simulated testbed, our approaches can reduce the latency of broadcast operation by a factor of up to 4.9. Thus, these results demonstrate that there is significant potential for our approaches to be applied towards designing scalable collective communication libraries for current and future generation HNOW envrionments. Keywords: Parallel Architecture, Network of Workstations (NOW), Heterogeneous Network of Workstations (HNOW), Collective Communication, Broadcast, Multicast. TR06 Empirical Studies of a Prediction Model for Regression Test Selection by Mary Jean Harrold, David Rosenblum, Gregg Rothermel, and Elaine Weyuker Regression testing is an important testing activity that can account for a large proportion of the cost of software maintenance. One approach to reducing the cost of regression testing is to employ a selective regression testing technique that (1)~selects a subset of a test suite that was used to test the software before the modifications, and then (2) uses this subset to test the modified software. Selective regression testing techniques reduce the cost of regression testing if the cost of selecting the subset from the test suite %together with the cost of running the selected subset of tests is less together with the cost of running the selected subset of test cases is less than the cost of running the entire test suite. Rosenblum and Weyuker recently proposed coverage-based predictors for use in predicting the effectiveness of regression test selection strategies. Using the regression testing cost model of Leung and White, Rosenblum and Weyuker demonstrated the applicability of these predictors with respect to a case study involving 31 versions of the KornShell. To further investigate the applicability of the Rosenblum-Weyuker (RW) predictor, additional empirical studies have been performed. The RW predictor was applied to a number of subjects, using two different selective regression testing tools, DejaVu and TestTube. These studies support two conclusions. First, they show that there is some variability in the success with which the predictors work, and second, they suggest that these results can be improved by incorporating information about the distribution of modifications. It is shown how the RW prediction model can be improved to provide such an accounting. TR05 Where to Provide Support for Efficient Multicasting in Irregular Networks: Network Interface or Switch? by Rajeev Sivaram, Ram Kesavan, D.K. Panda, and Craig B. Stunkel Recent research has proposed methods for enhancing the performance of multicast in networks with irregular topologies. These methods fall into two broad categories: (a) network interface (NI) based schemes that make use of enhanced functionality of the software/firmware running at the network interface (NI) processor, or (b) switch-based methods that use enhancements of the switch architecture to support hardware multicast. However, it is not clear how these methods compare to each other and when it makes sense for an architect to use one over the other. In order to answer such questions, in this paper we compare the performance of three efficient multicasting schemes: an NI-based multicasting scheme that uses a k-binomial tree [16], a switch-based multicasting scheme that uses path- based multidestination worms [15], and a switch-based multicasting scheme that uses a single tree-based multidestination worm [35]. We first identify the parameters involved in multicast communication and derive analytical values for the multicast latency under each of the three schemes. We then perform a number of simulation experiments to study the performance of the three schemes for single multicast traffic while changing a number of system parameters one at a time to isolate their impact. Finally, we study the performance of these schemes under increasing multicast load. Our results show that the switch-based multicasting scheme using a single tree-based multidestination worm performs the best among the three schemes. However, the NI-based multicasting scheme is capable of delivering high performance compared to the switch-based multicast using path-based worms especially when the software overhead at the network interface is less than half of the overhead at the host. We therefore conclude that support for multicast at the NI is an important first step to improving multicast performance. However, there is still considerable gain that can be achieved by supporting hardware multicast in switches. Finally, while supporting such hardware multicast, it is better to support schemes that can achieve multicast in one phase. Keywords; Parallel computer architecture, cut-through routing, multicast, broadcast, collective communication, switch-based networks, irregular networks, performance evaluation. TR04 Join Techniques in Relatinoal Databases by Yuping Yang and Mukesh Singhal Equijoin between two relations is one of the basic operations in relational databases. Substantial research efforts are still underway to enhance its performance due to its extreme importance in the industry. However, in recent years, there has not been a study which comprehensively examines, under a common framework, the performance of a wide spectrum of equijoin tgechniques available today. Processor speed, memory size, speed of sequential disk access, as well as the time ratio of random to sequential disk accesses, all have increased drastically in the past decade. Results of many previous performance studies of join techniques no longer hold due to this progress. The main contribution of this paper is twofold. First, it surveys a wide spectrum of equijoin techniques available today. Second, it compares their performance under a common framework that reflects the reality of today's computing environments. Through this survey, we see a trend that indexed join methods are, in general, far better than non-indexed methods for low selectivity joins in large relational databases. Other conclusions of this survey are: (1) a proof that shows that rocking technique in the nested block join provides no speed up; (2) join executions in shared-memory parallel machines with a large number of parallelly operated I/O channels behave more like join executions in shared-nothing parallel machines than that in the shared- memory parallel machines with only a few I/O channels. Key words: Relatinoal database, query execution, join, equijoin, index, disk I/O, performance, survey. TR03 Summary Databases as Indexing Structures by Yuping Yang and Mukesh Singhal This paper proposes a new summary database architecture (SDB) that employs summary informaiton in the forms of signatures for text-valued data and statistics such as the average, minimum, and maximum for numerical- valued data in the execution of joins and selections in a large relational database. Its join execution performance is better than the Bc tree method [4]. Its performance advantage is especially evident in large database for queries with low join selectivity or complex queries that have multiple joins and/or selections. A distinct feature of the SDB method is that for a given query, a full set of relational operations, including joins and/or selections, can be executed in the SDB before the main database is accessed. A detailed comparison between SDB and Bc tree join execution performance is also included. The excellent performance in answering queries with low selectivity joins in large relatinoal databases makes the SDB method ideal for various "online" databases such as the databases over the World Wide Web or in mobile computing environments. Key words: Relational database, query execution, join, selection, equijoin, index, summary, disk I/O, performance. TR02 Analysis and Modeling of Traffic in Modern Data Communication Networks by Gojko Babic, Bobby Vandalore and Raj Jain In performance analysis and design of communication network modeling data traffic is important. With introduction of new applications, the characteristics of the data traffic changes. We present a brief review the different models of data traffic and how they have evolved. We present results of data traffic analysis and simulated traffic, which demonstrates that teh packet train model fits the traffic at source destination level and long-memory (self-similar) model fits the traffic at the aggregate level. TR01 Issues in Querying Multimedia Presentations by Chao-Hui Wu and Renee J. Miller We examine the querying requirements of large libraries of multimedia presentations. We identify several important research problems that must be addressed to enable large scale use of such libraries. These include an integrated composition and query capability to permit the reuse of multimedia objects, presentations and presentation segments. The ad hoc querying must permit content-based queries along with queries over temporal and spatial synchronization characteristics. Complex data mining and decision support style queries must also be supported. Given these requirements, we briefly examine work on querying temporal and sequence data, identifying a few of the similarities and dissimilarities between presentations and these other forms of data. It is our intent to raise research issues rather than suggest definitive solutions.