bluuebunny/crossref_metadata_2025 huggingface dataset:
Algorithms for exact polynomial root calculation
Authors: Heindel Lee E.
Published: January 2007

This thesis discusses two sets of fully specified algorithms which, given a univariate polynomial with integer coefficients (with possible multiple roots) and a positive rational error bound, uses infinite-precision arithmetic and Sturm's Theorem to compute intervals containing the real roots of the polynomial and whose lengths are less than the given error bound, The algorithms also provide a simple means of determining the number of real roots in any interval.The first set of algorithms uses infinite-precision integer arithmetic to compute the sequence of polynomials required by Sturm's Theorem and also to do all the required polynomial evaluations. The second set uses congruence arithmetic to compute the images of the sequence of polynomials over the finite fields GF(p
i
) for several primes p
i
and then uses the natural homomorphisms from the integers onto the finite fields GF(p
i
) and the Chinese Remainder Theorem to do the evaluations. The primary advantage of the use of congruence arithmetic in the second set of algorithms is that the computing time to multiply any two elements of GF(p
i
) is a constant whereas the time to multiply any two integers is proportional to the square of their lengths.The computing times of both sets of algorithms are analyzed in detail using the techniques of computing time analysis developed in the past few years by G. E. Collins and D. Knuth. It is shown that if P is a primitive, positive, univariate polynomial over the integers of positive degree, m, whose coefficients are bounded in magnitude by d, and which has L real roots, and ε is some positive rational number, 0 < ε ≤ 1, then the computing time to approximate the roots of P to within is:[EQUATION]using either set of algorithms.The empirical results of applying the two sets of algorithms to random polynomials and the first ten Legendre and Chebyshev polynomials are reported. Neither set of algorithms proved to be faster for all the polynomials tested.
A proposed solution to the FUNARG problem
Authors: Sandewall Erik
Published: January 2007

This paper is a response to Joel Moses's recent paper, "The Function of FUNCTION in LISP, or ... ". We give some examples where the FUNARG feature of LISP 1. 5 is relative useful, and suggest a computationally efficient implementation of FUNARG. The idea in the proposal is to let a FUNARG-expression create indirect-addressing type bindings on the push-list for variables.
Extracting places from traces of locations
Authors: Kang Jong Hee , Welbourne William , Stewart Benjamin , Borriello Gaetano
Published: January 2007

Location-aware systems are proliferating on a variety of platforms from laptops to cell phones. Though these systems offer two principal representations in which to work with location (coordinates and landmarks) they do not offer a means for working with the user-level notion of "place". A place is a locale that is important to a user and which carries a particular semantic meaning such as "my place of work", "the place we live", or "My favorite lunch spot". Mobile devices can make more intelligent decisions about how to behave when they are equipped with this higher-level information. For example, a cell phone can switch to a silent mode when its owner enters a place where a ringer is inappropriate (e.g., a movie theater, a lecture hall, a place for personal reflection.) In this paper, we describe an algorithm for extracting significant places from a trace of coordinates. Furthermore, we experimentally evaluate the algorithm with real, long-term data collected from three participants using a Place Lab client [15], a software client that computes location coordinates by listening for RF-emissions from known radio beacons in the environment (e.g. 802.11 access points, GSM cell towers).
Data acquisition in multiple-sink sensor networks
Authors: Das Abhimanyu , Dutta Debojyoti
Published: January 2007

Scalable, energy-efficient data acquisition in large sensor network deployments such as habitat monitoring is an research important problem. In several papers [1, 2], sensor networks have been modeled as having a single sink (or base-station) that acts as the data recipient for a large number of sensors (data sources) deployed over a sensor field. The sensor network might use simple querying and data collection trees for hop-by-hop query dissemination and routing of sensor responses [1] back towards the sink. Since sensors are energy-constrained devices, we wish to minimize communication energy expenditure of these sensors.
Comparing vector space retrieval with the RUBRIC expert system
Authors: Gey Fredric , Chan Wingkei
Published: January 2007

RUBRIC is an expert system for full-text information retrieval. The underlying model for RUBRIC's information retrieval process is based upon fuzzy set theory. The RUBRIC developers have compared RUBRIC to the boolean retrieval model, which it subsumes. This study compares RUBRIC to the Vector Space Model for information retrieval, using RUBRIC's own test collection of thirty news articles from the Reuters News Service and their test search for articles which satisfy the information need to find out about "violent acts of terrorism." Results indicate that the vector space model is comparable to RUBRIC for relevant documents, while RUBRIC performs better at retrieving marginally relevant documents.
Information storage and retrieval
Authors: Minker Jack
Published: January 2007

Information Storage and Retrieval (IS&R) encompasses a broad scope of topics ranging from basic techniques for accessing data to sophisticated approaches for the analysis of natural language text and the deduction of information. Within the field, three general areas of investigation can be distinguished not only by their subject matter but also by the types of individuals presently interested in them:(1) Document retrieval,(2) Generalized data management, and(3) Question-answering.A functional description which applies to each of the three areas is presented together with a survey of work being conducted. The similarities and differences of the three areas of IS&R are described. Typical systems which incorporate many of the functions and techniques are described in the appendix.
A two-level resource management scheme in wireless networks based on user-satisfaction
Authors: Pal Sourav , Chatterjee Mainak , Das Sajal K.
Published: January 2007

The success of future generation wireless data services will depend on the parameterized provisioning of quality of service (QoS) for applications whose demands and nature are highly heterogeneous. Also, user satisfaction will play a key role in the economic viability of wireless service deployments. In this paper, we present a QoS framework based on the paradigm of
traffic class
and
user satisfaction
. We address the problem of dealing with subjectiveness of user satisfaction or expectation from service providers by defining what we call
user
irritation factors, using Sigmoid functions. These factors reflect users' sensitivity and tolerance to delay. The proposed class-based QoS framework comprises a radio resource management scheme which considers user satisfaction based on the perceived QoS, and caters to heterogeneous applications that have diverse QoS requirements. Our resource management scheme has two components: the admission control algorithm caters to the
long term
user satisfaction while the session-based rate and bandwidth allocation scheme manipulates the
short term
user satisfaction. Soft-reservation schemes are also proposed to cater to the higher paying users. Performance metrics have been specifically defined for each traffic class. Extensive simulations using four types of traffic and three classes of users reveal that the proposed framework offers improved QoS without compromising the utilization of the system.
Analysis of topology-unaware TDMA MAC policies for ad-hoc networks under diverse traffic loads
Authors: Oikonomou Konstantinos , Stavrakakis Ioannis
Published: January 2007

The ever-changing nature of the ad-hoc networks, makes the design of efficient Medium Access Control (MAC) policies challenging. Topology-unaware MAC policies, that allocate slots deterministically or probabilistically have been proposed in the past and evaluated under heavy traffic assumptions. In this paper, the heavy traffic assumption is relaxed and the system throughput achieved by these policies is derived as a function of the traffic load. The presented analysis establishes the conditions and determines the values of the access probability for which the system throughput under the probabilistic policy is not only higher than that under the deterministic policy but it is also close to the maximum achievable, provided that the traffic load and the topology density of the network are known. In case the traffic load and/or the topology density are not known (which is commonly the case in ad-hoc networks), alternative values for the access probability are also derived which, although not the optimal (maximizing the system throughput), they do lead to a system throughput higher than that under the Deterministic Policy. Simulation results for a variety of topologies with different characteristics support the claims and the expectations of the analysis and show the comparative advantage of the Probabilistic Policy over the Deterministic Policy.
The logic engine development system support for microprogrammed bit-slice development
Authors: Prosser Franklin , Winkel David
Published: January 2007

The Logic Engine Development System is an integrated hardware and software system that aids the designer in many phases of microprogrammed bit-slice hardware design. It is the first commercially-available system to provide, direct support for the microprogram sequencer, or to supply a built-in host computer for the designer's use. The Logic Engine includes a new microassembler that encourages structured coding while remaining simple to use.Microprogramming permits the designer to tackle complex control tasks, but this ability to deal conceptually with complex designs brings with it numerous implementation problems. On what type of breadboard should we build the architecture? How will we debug the architecture? How will we produce the microcode? How will we load the microcode into a control store? How will we design and build the microinstruction sequencer? How will we debug the microcode? How will we modify the microcode?These questions imply that the designer will need a powerful support system to allow him to manage microprogrammed control. The control unit itself is only one part of a good development system. Such a system must provide support for the development and debugging of both the architecture and the control algorithm. The system should suppress the usual design headaches and subtleties of hardware construction. A development system should provide the convenience of wire-wrap for initial testing. It should provide lights and switches to assist the designer in displaying and controlling individual signals during the testing stages of design. Of course, it should give powerful support to the development, debugging, and modification of the control program.The Logic Engine Development System, manufactured by Logic Design, Inc., offers a high standard of performance for development systems for microprogrammed bit-slice design.
Improving the performance of UCSD Pascal via microprogramming on the PDP-11/60
Authors: Schaefer Mark T. , Patt Yale N.
Published: January 2007

UCSD Pascal is implemented as a machine-independent virtual machine. This virtual machine is usually interpreted on a host computer by machine language instructions, which, in turn, are often interpreted by microcode. Performance of a virtual machine is generally a function of the number of levels of interpretation required to perform a computation. By bypassing one or more of these layers, it should be possible to enhance performance.To test this hypothesis, a Pascal interpreter was written for the PDP-11/60. After analysis of the Pascal machine, changes were made that interpreted selected portions of the virtual machine directly in microcode.This paper describes the microcode which was added, and discusses the improvements which resulted.
Security and confidentiality in a university computer network
Authors: Kerievsky Bruce
Published: January 2007

It is the intent of this paper to focus attention on the issue of security and confidentiality in a university computer network environment. By the term security, I mean protection for data from being written on by unauthorized network users. Correspondingly, confidentiality represents protection for data from being read by unauthorized computer users. The paper attempts to accomplish this objective in the following manner. First, I will discuss which segments of the computing population in university networks appear to require security and confidentiality for its programs and data. I will then discuss appropriate techniques by which such integrity and privacy can be attained and the problems that might occur in attempting to implement them. Finally, I will present what I have found to be several prevailing misunderstandings about computer network security.
Space-efficient evaluation of hypergeometric series
Authors: Cheng Howard , Gergel Barry , Kim Ethan , Zima Eugene
Published: January 2007

Many important constants, such as
e
and Apéry's constant ζ(3), can be approximated by a truncated hypergeometric series. The evaluation of such series to high precision has traditionally been done by binary splitting followed by fixed-point division. However, the numerator and the denominator computed by binary splitting usually contain a very large common factor. In this paper, we apply standard computer algebra techniques including modular computation and rational reconstruction to overcome the shortcomings of the binary splitting method. The space complexity of our algorithm is the same as a bound on the size of the
reduced
numerator and denominator of the series approximation. Moreover, if the predicted bound is small, the time complexity is better than the standard binary splitting approach. Our approach allows a series to be evaluated to a higher precision without additional memory. We show that when our algorithm is applied to compute ζ(3), the memory requirement is significantly reduced compared to the binary splitting approach.
SAGE
Authors: Stein William , Joyner David
Published: January 2007

SAGE is a framework for number theory, algebra, and geometry computation that is initially being designed for computing with elliptic curves and modular forms. The current implementation is primarily due to William Stein. It is open source and freely available under the terms of the GNU General Public License (GPL).
The spectrum of mathematical modeling and systems simulation
Authors: Karplus Walter J.
Published: January 2007

The methodology involved in the modeling and simulation of physical, life and social science systems is viewed in perspective. A critical factor determining the validity of a model is the extent to which it can be derived from basic laws and insights into the internal structure of the system using deductive methods, rather than relying upon observations and measurements of the system input and outputs. Accordingly, the mathematical models as they arise in various application disciplines are arranged along a spectrum according to the relative amount of deduction and induction involved in their construction. This provides an insight into the ultimate validity of simulations and to what use they can properly be put.
Model reliability and software quality assurance in simulation of nuclear fuel waste management systems
Authors: Ören Tuncer I. , Elzas Maurlce S. , Sheng Grant
Published: January 2007

As is the case with all scientific simulation studies, computerized simulation of nuclear fuel waste management systems can introduce and hide various types of errors. Frameworks to clarify issues of model reliability and software quality assurance are offered. Potential problems with reference to the main areas of concern for reliability and quality are discussed; e.g. experimental issues, decomposition, scope, fidelity, verification, requirements, testing, correctness, robustness are treated with reference to the experience gained in the past. A list comprising over 80 most common computerization errors is provided. Software tools and techniques used to detect and to correct computerization errors are discussed.
Statistical analysis of simulation output data
Authors: Sargent Robert G.
Published: January 2007

This paper is a tutorial paper on how to obtain point estimates and confidence intervals of steady state means of simulation output data. The methods of using replications, batch means, and regenerative cycles for obtaining these point and interval estimates are discussed in detail and are applied to a simple time-shared computer model to illustrate their use. A brief discussion is included on using time series methods to obtain these estimates. The advantages and disadvantages of the various methods are given, including specific recommendations as to when certain methods might be used.
System Dynamics modeling in health care
Authors: Hirsch Gary B.
Published: January 2007

The System Dynamics modeling technique has been extensively applied to health care problems. Most of these applications have revealed insights to planners and policy-makers that would not have arisen without a System Dynamics model. The distinctive characteristics of System Dynamics that enabled these insights to be developed have also been the source of some problems as well. These problems have hindered the implementation of results from certain health care modeling efforts and have kept System Dynamics from being more broadly and extensively applied in the health care field. This paper focuses on both the strengths System Dynamics has shown in its applications to health care and the difficulties that have been encountered. As background to the discussion of strengths and problems, the paper begins with a general description of the System Dynamics approach and brief history of its development and application to health care.
Requiem for large-scale models
Authors: Lee Douglass B.
Published: January 2007

The task in this paper is to evaluate, in some detail,, the fundamental flaws in attempts to construct and use large models and to examine the planning context in which the models, like dinosaurs, collapsed rather than evolved. The conclusions can be summarized in three points:1. In general, none of the goals held out for large-scale models have been achieved, and there is little reason to expect anything different in the future.
Simulation models and some applications to maintenance and repair systems
Authors: Czajkiewicz Zbigniew J. , Reddy Narendra H. R.
Published: January 2007

Simulation is one of the powerful techniques to study maintenance and repair phenomena. Perhaps the most compelling reason for the adoption of simulation has been the need to realistically model a complex environment. Simulation is quite sophisticated in that it enables various groups, activities, and resource mixes to be modelled. Further failure rates of systems and subsystems, repair times and equipment movement times can all be determined randomly based on input probability distributions. Simulation has a distinct advantage to conduct various trade-off studies like trade-offs between manpower requirements and component reliability and their effect on selection from various means.
Information retrieval in context
Authors: Ingwersen Peter , Järvelin Kalervo
Published: January 2007

IR research is now conducted in multi-media, multi-lingual, and multi-modal environments but largely in a context-free manner (Ingwersen & Järvelin, 2005). However, the retrieval of such information depends on time, place, history of interaction, task in hand, and a range of other factors that are not given explicitly but are implicit in the interaction and ambient environment, namely the context. Such contextual data can be used effectively to constrain retrieval of information thereby reducing the complexity of the retrieval process.
Exploratory search interfaces
Authors: White Ryen W. , Kules Bill , Bederson Ben
Published: January 2007

The development and testing of systems to support users engaged in exploratory search activities (i.e., searches where the target may be undefined) is an challenge for the online search community. In this article we report on a workshop on exploratory search issues organized in conjunction with the University of Maryland Human-Computer Interaction Laboratory's Annual Symposium and Open House in June 2005. This workshop brought together researchers from the fields of Information Seeking (IS), Information Retrieval (IR), Human-Computer Interaction (HCI) and Information Visualization (IV) for a cross-disciplinary exploration of these and other issues. Although originally intended to focus on interfaces to support exploratory search the workshop blossomed into a rich discussion of not only interface issues, but also evaluation, the cognitive processes that underlie information exploration and research methods.
The nearest polynomial with a given zero, revisited
Authors: Rezvani Nargol , Corless Robert M.
Published: January 2007

In his 1999 SIGSAM BULLETIN paper [7], H. J. Stetter gave an explicit formula for finding the nearest polynomial with a given zero. This present paper revisits the issue, correcting a minor omission from Stetter's formula and explicitly extending the results to different polynomial bases.Experiments with our implementation demonstrate that the formula may not after all, fully solve the problem, and we discuss some outstanding issues: first, that the nearest polynomial with the given zero may be identically zero (which might be surprising), and, second, that the problem of finding the nearest polynomial of the same degree with a given zero may not, in fact, have a solution. A third variant of the problem, namely to find the nearest monic polynomial (given a monic polynomial initially) with a given zero, a problem that makes sense in some polynomial bases but not others, can also be solved with Stetter's formula, and this may be more satisfactory in some circumstances. This last can be generalized to the case where some coefficients are intrinsic and not to be changed, whereas others are empiric and may safely be changed. Of course, this minor generalization is implicit in [7]; This paper simply makes it explicit.
The RegularChains library in MAPLE
Authors: Lemaire F. , Maza M. Moreno , Xie Y.
Published: January 2007

Performing calculations modulo a set of relations is a basic
technique in algebra. For instance, computing the inverse of an
integer modulo a prime integer or computing the inverse of the
complex number 3 + 2t modulo the relation
ℓ2 + 1 = 0. Computing modulo a set
S containing more than one relation requires
from S to have some mathematical structure. For
instance, computing the inverse of p =
x + y modulo
S =
{x2 +
y +
1,y2 +
x + 1} is difficult unless one realizes that
this question is equivalent to computing the inverse of
p modulo C =
{x4 +
2x2 +
x + 2,y +
x2 + 1}. Indeed, from
there one can simplify p using
y =
-x2 - 1 leading to
q =
-x2 +
x - 1 and compute the inverse of
q modulo
x4 +
2x2 +
x + 2 (using the extended Euclidean algorithm)
leading to -1/2x3 -
1/2x. One commonly used mathematical structure
for a set of algebraic relations is that of a
Gröbner basis. It is particularly well
suited for deciding whether a quantity is null or not modulo a set
of relations. For inverse computations, the notion of a
regular chain is more adequate. For instance,
computing the inverse of p =
x + y modulo the set
C =
{y2 -
2x +
1,x2 -
3x + 2}, which is both a Gröbner basis
and a regular chain, is easily answered in this latter point of
view. Indeed, it naturally leads to consider the GCD of
p and
Cy =
y2 -
2x + 1 modulo the relation
Cx =
x2 -
3x + 2 = 0, which is

[EQUATION]

This shows that p has no inverse if
x = 1 and has an inverse (which can be computed
and which is -y + 2) if x =
2.
On the complexity of the D5 principle
Authors: Dahan X. , Schost É. , Maza M. Moreno , Wu W. , Xie Y.
Published: January 2007

The standard approach for computing with an algebraic number is
through the data of its irreducible minimal polynomial over some
base field
k.
However, in typical tasks such as polynomial
system solving, involving many algebraic numbers of high degree,
following this approach will require using probably costly
factorization algorithms. Della Dora, Dicrescenzo and Duval
introduced "dynamic evaluation" techniques (also termed "D5
principle") [3] as a means to compute with algebraic numbers, while
avoiding factorization. Roughly speaking, this approach leads one
to compute over
direct products of field extensions of k
,
instead of only field extensions.

In this work, we address complexity issues for basic operations
in such structures. Precisely, let

[EQUATION]

be a family of polynomials, called a triangular
set, such that k ←
K =
k[X1,...,Xn]/T
is a direct product of field extensions. We write δ for
the dimension of K over k,
which we call the degree of
T. Using fast polynomial multiplication and
Newton iteration for power series inverse, it is a folklore result
that for any ε > 0, the operations (+, X) in
K can be performed in
cnεδ1+ε
operations in k, for some constant
cε. Using a
fast Euclidean algorithm, a similar result easily carries over to
inversion, in the special case when K is a
field.

Our main results are similar estimates for the general case,
where K is merely a product of fields. Following
the D5 philosophy, meeting zero-divisors in the computation will
lead to splitting the triangular set
T into a family thereof, defining the same
extension. Inversion is then replaced by
quasi-inversion: a quasi-inverse [6] of
α ∈ K is a splitting of
T, such that α is either zero or
invertible in each component, together with the data of the
corresponding inverses.
Classifying search engine queries using the web as background knowledge
Authors: Vogel David , Bickel Steffen , Haider Peter , Schimpfky Rolf , Siemen Peter , Bridges Steve , Scheffer Tobias
Published: January 2007

The performance of search engines crucially depends on their ability to capture the meaning of a query most likely intended by the user. We study the problem of mapping a search engine query to those nodes of a given subject taxonomy that characterize its most likely meanings. We describe the architecture of a classification system that uses a web directory to identify the subject context that the query terms are frequently used in. Based on its performance on the classification of 800,000 example queries recorded from MSN search, the system received the Runner-Up Award for Query Categorization Performance of the KDD Cup 2005.
Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks
Authors: Kyasanur Pradeep , Vaidya Nitin H.
Published: January 2007

Wireless technologies, such as IEEE 802.11a, that are used in ad hoc networks provide for multiple non-overlapping channels. Most ad hoc network protocols that are currently available are designed to use a single channel. However, the available network capacity can be increased by using multiple channels. This paper presents new protocols specifically designed to exploit multiple channels. Our protocols simplify the use of multiple channels by using multiple interfaces, although the number of interfaces per host is typically smaller than the number of channels. We propose a link layer protocol to manage multiple channels, and it can be implemented over existing IEEE 802.11 hardware. We also propose a new routing metric for multi-channel multi-interface networks, and the metric is incorporated into an on-demand routing protocol that operates over the link layer protocol. Simulation results demonstrate the effectiveness of the proposed approach in significantly increasing network capacity, by utilizing all the available channels, even when the number of interfaces per host is smaller than the number of channels.
Allocating indivisible goods
Authors: Bezáková Ivona , Dani Varsha
Published: January 2007

The problem of allocating divisible goods has enjoyed a lot of attention in both mathematics (e.g. the cake-cutting problem) and economics (e.g. market equilibria). On the other hand, the natural requirement of indivisible goods has been somewhat neglected, perhaps because of its more complicated nature. In this work we study a fairness criterion, called the Max-Min Fairness problem, for
k
players who want to allocate among themselves
m
indivisible goods. Each player has a specified valuation function on the subsets of the goods and the goal is to split the goods between the players so as to maximize the minimum valuation. Viewing the problem from a game theoretic perspective, we show that for two players and additive valuations the expected minimum of the (randomized) cut-and-choose mechanism is a 1/2-approximation of the optimum. To complement this result we show that no truthful mechanism can compute the exact optimum.We also consider the algorithmic perspective when the (true) additive valuation functions are part of the input. We present a simple 1/(
m - k
+ 1) approximation algorithm which allocates to every player at least 1/
k
fraction of the value of all but the
k
- 1 heaviest items. We also give an algorithm with additive error against the fractional optimum bounded by the value of the largest item. The two approximation algorithms are incomparable in the sense that there exist instances when one outperforms the other.
A server-mediated peer-to-peer system
Authors: Kwok S. H. , Chan K. Y. , Cheung Y. M.
Published: January 2007

A peer-to-peer (P2P) system is a popular means of file distribution. Existing P2P systems do not adequately address a variety of common problems including (1) limited search scope, (2) dynamic nature of peers and (3) lack of collaboration among peers. In this paper, we propose a server-mediated peer-to-peer system to address these problems and to improve the performance of existing decentralized P2P systems by incorporating a central server into the decentralized P2P system to facilitate collaboration among peers. Two main features of our proposed system are Assisted-search and Assisted-download. Experimental results show that the search coverage was increased by 289.91% by using Assisted-search, while the overall download speed was improved by 33% by using Assisted-download.
Improving privacy in Vickrey auctions
Authors: López Natalia , Núñez Manuel , Rodríguez Ismael , Rubio Fernando
Published: January 2007

Many different types of auctions can be applied to determine selling prices, each of them fulfilling different properties. Among them, Vickrey auctions are specially interesting due to the fact that they disallow strategic behaviors of the bidders. In fact, the dominant strategy for each bidder consists in bidding his reserve price. However, somebody has to collect all the bids, so that bids are not kept private. In this paper we present a method to overcome this problem. That is, we present a way to implement Vickrey auctions preserving the privacy of all the bidders.
SpyGlass
Authors: Buschmann Carsten , Pfisterer Dennis , Fischer Stefan , Fekete Sándor P. , Kröller Alexander
Published: January 2007

In this paper we present a modular and extensible visualization framework for wireless sensor networks. These networks have typically no means of visualizing their internal state, sensor readings or computational results. Visualization is therefore a key issue to develop and operate these networks. Data emitted by individual sensor nodes is collected by gateway software running on a machine in the sensor network. It is then passed on via TCP/IP to the visualization software on a potentially remote machine. Visualization plug-ins can register to different data types, and visualize the information using a flexible multi-layer mechanism that renders the information on a canvas. Developers can easily adapt existing or develop new custom tailored plug-ins for their specific visualization needs and applications.
Applying Ant Colony Optimization to the partitioned scheduling problem for heterogeneous multiprocessors
Authors: Chen Hua , Cheng Albert M. K.
Published: January 2007

The problem of determining whether a set of periodic tasks can be assigned to a set of heterogeneous processors in such a way that all timing constraints are met has been shown, in general, to be NP-hard. This paper presents a new algorithm based on Ant Colony Optimization (ACO) metaheuristic for solving this problem. Experimental results show that our ACO approach can outperform the major existing methods. In addition to being able to search for a feasible assignment solution, our ACO approach can further optimize the solution to reduce its energy consumption.
How should embedded systems be taught?
Authors: Grimheden Martin , Törngren Martin
Published: January 2007

This paper presents results from a previously published analysis performed on the subject of embedded systems using a didactical approach together with some educational implications. To illustrate the didactical analysis, examples from embedded systems education at KTH in Sweden are given where an exemplifying selection and an interactive communication have been adopted in embedded systems related courses.The exemplifying selection means that education in embedded systems would benefit from teaching 'everything of something' rather than 'something of everything', that is, depth rather than width. The interactive communication strongly motivates experimental work, hands-on approaches and problem based learning in general.
An evaluation of the VME architecture for use in embedded systems education
Authors: Ricks Kenneth G. , Jackson David J. , Stapleton William A.
Published: January 2007

The VMEbus is an IEEE standard architecture upon which many embedded and real-time systems are built. It has existed for nearly 25 years and has been extensively used for military, industrial, and aerospace applications. This paper describes the general characteristics of the VMEbus architecture, specifically relating these characteristics to aspects of embedded systems education included as components of the IEEE/ACM CE2004 computer engineering model curriculum. Portions of this model curriculum are currently being implemented at universities across the country as part of an increasing effort to address the need for embedded systems education. This evaluation will help to identify the strengths and weaknesses of this architecture as a general-purpose embedded systems educational tool.
Propositional-logic approach to one-shot multi issue bilateral negotiation
Authors: Ragone Azzurra , Di Noia Tommaso , Di Sciascio Eugenio , Donini Francesco M.
Published: January 2007

Semantic-based e-marketplaces have emerged in recent years, to ease the initial phase of transaction in e-marketplaces, where demand/supply descriptions can be complex and expressive.With the - long term - aim of building an e-marketplace fully exploiting rich semantic descriptions in all stages of a transaction, in this paper we propose a semantic-oriented approach to multi issue bilateral negotiation, which exploits a simple propositional logic. We present the theoretical setting, the negotiation protocol, whose outcome is Pareto-efficient, and illustrate the behavior with a simple example.
A survey of bargaining models for grid resource allocation
Authors: Sim Kwang Mong
Published: January 2007

Whereas it is noted that various types of auctions, commodity market models, and contract-net (tendering) model are more widely used for managing Grid resources, this paper focuses on discussing bargaining (negotiation) models for Grid resource management. To this end, this survey supplements and complements existing surveys by reviewing, comparing, and highlighting the very few extant research initiatives on applying bargaining as a mechanism for managing Grid resources. The contributions of this paper are (i) discussing the motivations for considering bargaining models for Grid resource management, (ii) discussing the issues in building bargaining mechanisms for Grid resource management, (iii) comparing the strategies and protocols of state-of-the-art bargaining models for Grid resources, and (iv) discussing possible new directions.
MobiNet
Authors: Mahadevan Priya , Rodriguez Adolfo , Becker David , Vahdat Amin
Published: January 2007

The current state of the art in evaluating applications and communication protocols for ad hoc wireless networks usually involves either simulation or small-scale live deployment. Larger-scale live deployment is typically costly and difficult to run under controlled circumstances. Simulation allows more flexibility in varying system configurations, but requires the duplication of application and network behavior within the simulator. While simulation and live deployment will clearly continue to play important roles in the evaluation of mobile systems, we present
MobiNet
, a third point in this space. In MobiNet, the communication of unmodified applications running on stock operating systems is subject to the real-time emulation of a user-specified wireless network environment. MobiNet utilizes a cluster of
emulator
nodes to appropriately delay, drop or deliver packets in a hop by hop fashion based on MAC-layer protocols, ad hoc routing protocols, congestion, queuing, and available bandwidth in the network. Our evaluations show that MobiNet emulation is scalable and accurate while executing real code, including video playback.
Exploiting redundancy to conserve energy in storage systems
Authors: Pinheiro Eduardo , Bianchini Ricardo , Dubnicki Cezary
Published: January 2007

This paper makes two main contributions. First, it introduces Diverted Accesses, a technique that leverages the redundancy in storage systems to conserve disk energy. Second, it evaluates the previous (redundancy-oblivious) energy conservation techniques, along with Diverted Accesses, as a function of the amount and type of redundancy in the system. The evaluation is based on novel analytic models of the energy consumed by the techniques. Using these energy models and previous models of reliability, availability, and performance, we can determine the best redundancy configuration for new energy-aware storage systems. To study Diverted Accesses for realistic systems and workloads, we simulate a wide-area storage system under two file-access traces. Our modeling results show that Diverted Accesses is more effective and robust than the redundancy-oblivious techniques. Our simulation results show that our technique can conserve 20-61% of the disk energy consumed by the wide-area storage system.
Partially overlapped channels not considered harmful
Authors: Mishra Arunesh , Shrivastava Vivek , Banerjee Suman , Arbaugh William
Published: January 2007

Many wireless channels in different technologies are known to have partial overlap. However, due to the interference effects among such partially overlapped channels, their simultaneous use has typically been avoided. In this paper, we present a first attempt to model partial overlap between channels in a systematic manner. Through the model, we illustrate that the use of partially overlapped channels is not always harmful. In fact, a careful use of some partially overlapped channels can often lead to significant improvements in spectrum utilization and application performance. We demonstrate this through analysis as well as through detailed application-level and MAC-level measurements. Additionally, we illustrate the benefits of our developed model by using it to directly enhance the performance of two previously proposed channel assignment algorithms --- one in the context of wireless LANs and the other in the context of multi-hop wireless mesh networks. Through detailed simulations, we show that use of partially overlapped channels in both these cases can improve end-to-end application throughput by factors between 1.6 and 2.7 in different scenarios, depending on wireless node density. We conclude by observing that the notion of partial overlap can be the right model of flexibility to design efficient channel access mechanisms in the emerging software radio platforms.
On light and heavy traffic approximations of balanced fairness
Authors: Bonald Thomas , Penttinen Aleksi , Virtamo Jorma
Published: January 2007

Flow level analysis of communication networks with multiple shared resources is generally difficult. A recently introduced sharing scheme called balanced fairness has brought these systems within the realm of tractability. While straightforward in principle, the numerical evaluation of practically interesting performance metrics like per-flow throughput is feasible for limited state spaces only, besides some specific networks where the results are explicit. In the present paper, we study the behaviour of balanced fairness in light and heavy traffic regimes and show how the corresponding performance results can be used to approximate the flow throughput over the whole load range. The results apply to any network, with a state space of arbitrary dimension. A few examples are explicitly worked out to illustrate the concepts.
On suitability of Euclidean embedding of internet hosts
Authors: Lee Sanghwan , Zhang Zhi-Li , Sahu Sambit , Saha Debanjan
Published: January 2007

In this paper, we investigate the suitability of embedding Internet hosts into a Euclidean space given their pairwise distances (as measured by round-trip time). Using the classical scaling and matrix perturbation theories, we first establish the (sum of the) magnitude of
negative
eigenvalues of the (doubly-centered, squared) distance matrix as a measure of suitability of Euclidean embedding. We then show that the distance matrix among Internet hosts contains negative eigenvalues of
large magnitude
, implying that embedding the Internet hosts in a Euclidean space would incur relatively large errors. Motivated by earlier studies, we demonstrate that the inaccuracy of Euclidean embedding is caused by a large degree of
triangle inequality violation
(TIV) in the Internet distances, which leads to negative eigenvalues of large magnitude. Moreover, we show that the TIVs are likely to occur
locally
, hence, the distances among these close-by hosts cannot be estimated accurately using a
global
Euclidean embedding, in addition, increasing the dimension of embedding does not reduce the embedding errors. Based on these insights, we propose a new hybrid model for embedding the network nodes using only a 2-dimensional Euclidean coordinate system and small
error adjustment terms
. We show that the accuracy of the proposed embedding technique is as good as, if not better, than that of a 7-dimensional Euclidean embedding.
Bounding stationary results of Tandem networks with MAP input and PH service time distributions
Authors: Buchholz Peter
Published: January 2007

In this paper, we propose a new approach to compute bounds on stationary measures of queueing systems with an input process described by a Markovian Arrival Process (MAP) and a sequence of stations with Phase Type (PH) service time distributions. Such queueing systems cannot be solved exactly since they have an infinite state space in several natural dimensions. Based on earlier work on the computation of bounds for specific classes of infinite Markov chains, the paper presents a new approach specifically tailored to the analysis of the mentioned class of queueing networks. By increasing the size of the state space of the aggregated Markov chain to be solved for bound computation, bounds can be made arbitrarily tight, but practical limits come up due to the computational complexity. However, we show by means of several examples that tight bounds can be derived with low effort for a large set of queueing systems in the mentioned class.
Finding probably better system configurations quickly
Authors: Osogami Takayuki , Itoko Toshinari
Published: January 2007

The performance of computer and communication systems can in theory be optimized by iteratively finding better system configurations. However, a bottleneck is the time required in simulations/experiments for finding a better system configuration in each iteration. We propose algorithms that quickly find a system configuration that is probably better than the "standard" system configuration, where the performance of a given system configuration is estimated via simulations or experiments. We prove that our algorithms make correct decisions with high probability, and various heuristics to reduce the total simulation time are proposed. Numerical experiments show the effectiveness of the proposed algorithms, and this leads to several guidelines for designing efficient and reliable optimization procedures for the performance of computer and communication systems.
Packet classifiers in ternary CAMs can be smaller
Authors: Dong Qunfeng , Banerjee Suman , Wang Jia , Agrawal Dheeraj , Shukla Ashutosh
Published: January 2007

Serving as the core component in many packet forwarding, differentiating and filtering schemes, packet classification continues to grow its importance in today's IP networks. Currently, most vendors use Ternary CAMs (TCAMs) for packet classification. TCAMs usually use brute-force parallel hardware to simultaneously check for all rules. One of the fundamental problems of TCAMs is that TCAMs suffer from range specifications because rules with range specifications need to be translated into multiple TCAM entries. Hence, the cost of packet classification will increase substantially as the number of TCAM entries grows. As a result, network operators hesitate to configure packet classifiers using range specifications. In this paper, we optimize packet classifier configurations by identifying semantically equivalent rule sets that lead to reduced number of TCAM entries when represented in hardware. In particular, we develop a number of effective techniques, which include: trimming rules, expanding rules, merging rules, and adding rules. Compared with previously proposed techniques which typically require modifications to the packet processor hardware, our scheme does not require any hardware modification, which is highly preferred by ISPs. Moreover, our scheme is complementary to previous techniques in that those techniques can be applied on the rule sets optimized by our scheme. We evaluate the effectiveness and potential of the proposed techniques using extensive experiments based on both real packet classifiers managed by a large tier-1 ISP and synthetic data generated randomly. We observe significant reduction on the number of TCAM entries that are needed to represent the optimized packet classifier configurations.