\
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.
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.
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.
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.
p
Key words: Database, query execution, index, summary, performance.
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.
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.
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.
TR24A Dynamically Coupled Neural Oscillator Network for Image
Segmentation by 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.
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
TR06Empirical 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.
TR05Where 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.
TR04Join 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.
TR03Summary 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.
TR02Analysis 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.
TR01Issues 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.