bluuebunny/crossref_metadata_2025 huggingface dataset:
Some extensions of a system for inferencing on partial information
Authors: Joshi Aravind K.
Published: January 2007

Some extensions of a system for inferencing on partial information, which uses production rules, are described. Basically, the system consists of RULES, an active set of rules (a subset of potentially large set of rules), partially ordered by specificity, and FACTS, a small active set of facts (a subset of potentially large set of data base facts). The critical feature of the inference method is that only a partial match of the antecedent of a rule is needed. Some selected extensions of the system are presented. These concern some approaches to the problems of selecting from an ambiguous response and, more importantly, transforming or dynamic clustering of FACTS and RULES. This latter problem is important because partial match is defined over the sets RULES and FACTS, and unless these sets are reasonably small, partial match can be an unmanageable operation. Several issues concerning the use of this inference system in certain applications are also briefly discussed.
Control structure of a pattern-directed search system
Authors: Minker Jack
Published: January 2007

A pattern-directed search system based upon work in the first-order predicate calculus and oriented towards Question Answering Systems is described. The pattern directed search consists of a modified form of the unification algorithm which permits a set of literals (which may be thought of as subproblems) to unify only if they can be made to match syntactically
and
semantically. Although the system can be used as a general theorem prover, the work described is oriented towards Question Answering Systems. Semantic information is obtained from a semantic network embedded in the system and used during the pattern matching process.
Conversational action patterns in dialogs
Authors: Faught William S.
Published: January 2007

Systems that interact in dialogs need to understand linguistic actions being used by one another and know which linguistic actions are appropriate for their own uses. We introduce a model based on conversational action patterns to describe and predict speech acts in natural language dialogs and to specify appropriate actions to satisfy the system's goals. A modified production system was used to implement the formalism. The salient characteristics of the production system are:(1) Affects (emotions) can modify the interpretation of external events and alter the flow of control of the systems.(2) The system uses overlapping and parallel rules to predict and generate overlapping linguistic events in dialog situations.
Planning speech acts and referring expressions
Authors: Cohen Philip R.
Published: January 2007

This talk focused on two problems: criteria for speech act definitions and a criterion for the initial choice of referring expressions. The first problem arises in defining speech acts in a form where they can be used - as operators in a (STRIPS-like) problem-solving system. The principle advocated here was one of "conversational competence" - could a problem-solving system, given a goal and knowledge of its conversant's beliefs and goals, issue all and only those speech acts that people would find appropriate under the corresponding circumstances?
Children's understanding of interacting plans
Authors: Newman Denis
Published: January 2007

A research application of the (interacting plans notation system) (Bruce and Newman, 1978) was discusses. A body of recent psychological research has been concerned with the child's developing understanding of other people and in particular with their understanding that one person (A) can infer how B views a situation and that A also can know that B is capable of Inferring A's point of view. The ability to coordinate multiple perspectives has been called "role-taking". The (notation system) provides a means for precisely specifying the role-taking demands of stories or videotaped skits that involve two interacting characters. The specification provides the basis for predicting the relative difficulty that elementary school children would have in telling about several skits produced for children's television which are being used as stimulus materials.
Critical remarks about a paper on limitations for artificial intelligence
Authors: KONRAD Erhard
Published: January 2007

The journal INFORMATION SYSTEMS has printed a methodologically very interesting paper of V. Cherniavsky entitled "On algorithmic natural language analysis and understanding" [1]. However, a rigorous analysis of the paper shows that it contains a hidden fallacy which makes its results questionable.
With J
Authors: Reiter Cliff
Published: January 2007

Modeling techniques forecast future behavior based upon available data. Traditional models use linear or differential equations to create deterministic models that use the available information to estimate parameters in the model and then current information is used as input to the model to forecast subsequent evolution. The idea of fractal or chaotic forecasting is to use historical data that closely matches the pattern of the current situation, and only utilize the most relevant historical data for the construction of the forecast. The technique is fairly simple and can be effective, especially if the phenomenon contains subtly hidden, deterministic, nonlinear behavior. For more discussion of fractal forecasting, see [1,2]; earlier versions of some of these experiments and some variants of the implementation appear in [3].
Extracting relational data from HTML repositories
Authors: Zhang Ruth Yuee , Lakshmanan Laks V. S. , Zamar Ruben H.
Published: January 2007

There is a vast amount of valuable information in HTML documents, widely distributed across the World Wide Web and across corporate intranets. Unfortunately, HTML is mainly presentation oriented and hard to query. In this paper, we develop a system to extract desired information (records) from thousands of HTML documents, starting from a small set of examples. Duplicates in the result are automatically detected and eliminated. We propose a novel method to estimate the current coverage of results by the system, based on capture-recapture models with unequal capture probabilities. We also propose techniques for estimating the error rate of the extracted information and an interactive the technique for enhancing information quality. To evaluate the method and ideas proposed in this paper, we conducted an extensive set of experiments. Our experimental results validate the effectiveness and utility of our system, and demonstrate interesting tradeoffs between running time of information extraction and coverage of results.
Learning important models for web page blocks based on layout and content analysis
Authors: Song Ruihua , Liu Haifeng , Wen Ji-Rong , Ma Wei-Ying
Published: January 2007

Previous work shows that a web page can be partitioned into multiple segments or blocks, and often the importance of those blocks in a page is not equivalent. It has also been proven that differentiating noisy and unimportant blocks from pages can facilitate web mining, search and accessibility. However, no uniform approach and model has been presented to measure the importance of different blocks in a web page. Through a user study, we found that people do have a consistent view about the importance of blocks in a web page. Thus, we investigate how to find a model to automatically assign importance values to blocks in a web page. We formulate the block importance estimation as a learning problem. First, we use a vision-based page segmentation technique to partition a web page into semantic blocks with a hierarchical structure. Then spatial features (such as position and size) and content features (such as the number of images and links) are extracted to construct a feature vector for each block. Then, learning algorithms are used to train a model to assign importance to each block in the web page. In our experiments, the best model can achieve the performance with Micro-F1 80.2% and Micro-Accuracy 86.8%.
Learning by googling
Authors: Cimiano Philipp , Staab Steffen
Published: January 2007

The goal of giving a well-defined meaning to information is currently shared by endeavors such as the Semantic Web as well as by current trends within Knowledge Management. They all depend on the large-scale formalization of knowledge and on the availability of formal metadata about information resources. However, the question how to provide the necessary formal metadata in an effective and efficient way is still not solved to a satisfactory extent. Certainly, the most effective way to provide such metadata as well as formalized knowledge is to let humans encode them directly into the system, but this is neither efficient nor feasible. Furthermore, as current social studies show, individual knowledge is often less powerful than the collective knowledge of a certain community.As a potential way out of the
knowledge acquisition bottleneck
, we present a novel methodology that acquires collective knowledge from the World Wide Web using the Google
TM
API. In particular, we present PANKOW, a concrete instantiation of this methodology which is evaluated in two experiments: one with the aim of classifying novel instances with regard to an existing ontology and one with the aim of learning sub-/superconcept relations.
A critical review of multi-objective optimization in data mining
Authors: Freitas Alex A.
Published: January 2007

This paper addresses the problem of how to evaluate the quality of a model built from the data in a multi-objective optimization scenario, where two or more quality criteria must be simultaneously optimized. A typical example is a scenario where one wants to maximize both the accuracy and the simplicity of a classification model or a candidate attribute subset in attribute selection. One reviews three very different approaches to cope with this problem, namely: (a) transforming the original multi-objective problem into a single-objective problem by using a weighted formula; (b) the lexicographical approach, where the objectives are ranked in order of priority; and (c) the Pareto approach, which consists of finding as many non-dominated solutions as possible and returning the set of non-dominated solutions to the user. One also presents a critical review of the case for and against each of these approaches. The general conclusions are that the weighted formula approach -- which is by far the most used in the data mining literature -- is to a large extent an ad-hoc approach for multi-objective optimization, whereas the lexicographic and the Pareto approach are more principled approaches, and therefore deserve more attention from the data mining community.
KDD physics task
Authors: Wangikar Lalit , Agrwal Vineet , Gupta Vivek
Published: January 2007

In this paper, we present the methodology followed by Inductis in developing the predictive models for Quantum Physics task in KDD Cup 2004. We discuss many challenges that we faced in approaching the task and how we overcame them. We explored the solution space with various classification approaches and finally used stochastic gradient boosting offered on the TreeNet platform. A set of TreeNet models was fit varying various parameters and its performance was measured.
The 1st workshop on ROC analysis in artificial intelligence (ROCAI-2004)
Authors: Hernàndez-Orallo José , Ferri Cèsar , Lachiche Nicolas , Flach Peter
Published: January 2007

This short report includes a summary of the presentations and discussions held during the ROCAI-2004 workshop, as well as the workshop conclusions and the future agenda. ROCAI-2004 was held in Valencia, on August the 22nd, as part of the 16th European Conference on Artificial Intelligence, ECAI-2004, in Valencia, Spain.
A recursive random search algorithm for network parameter optimization
Authors: Ye Tao , Kalyanaraman Shivkumar
Published: January 2007

This paper proposes a new heuristic search algorithm, Recursive Random Search(RRS), for black-box optimization problems. Specifically, this algorithm is designed for the dynamical parameter optimization of network protocols which emphasizes on obtaining good solutions within a limited time frame rather than full optimization. The RRS algorithm is based on the initial high-efficiency property of random sampling and attempts to maintain this high-efficiency by constantly "restarting" random sampling with adjusted sample spaces. Due to its basis on random sampling, the RRS algorithm is robust to the effect of random noises in the objective function and it performs especially efficiently when handling the objective functions with negligible parameters. These properties have been demonstrated with the tests on a suite of benchmark functions. The RRS algorithm has been successfully applied to the optimal configuration of several network protocols. One application to a network routing algorithm is presented.
Searching for mobile mice and elephants in GPRS networks
Authors: Kalden Roger , Ekström Hannes
Published: January 2007

In this paper, we provide statistics on large-scale traffic measurements that have been made in a live cellular GPRS network. We show that the current GPRS traffic is dominated by HTTP- and WAP-based applications, and further show in what direction (uplink and/or downlink) the ensuing traffic is transmitted as well as statistics on the length of the flows on a per application basis. We find that the results differ compared to those found in similar measurement studies that have been carried out in the fixed Internet. In particular, our results suggest that flows are shorter in cellular networks, and that the so-called mice and elephant effect, whereby a small part of the flows make up a majority of the bytes transferred, is not prevalent in GPRS networks. Instead, extremely short flows account for the majority of the total flows and bytes transferred. We also discuss the impact of this finding on future research on TCP loss recovery.
Multi-path admission control for mobile ad hoc networks
Authors: Lindgren Anders , Belding-Royer Elizabeth M.
Published: January 2007

To enable the use of applications that require real-time communication in ad hoc networks, an admission control mechanism must be in place to prevent the network from becoming congested, since congestion results in reduced quality of service for applications. Current admission control solutions encounter problems in the face of mobility, resulting in unacceptable disruptions in communication. To solve this problem, we apply multi-path routing mechanisms and propose a new admission control protocol. We show through simulation that our solution is able to prevent communication disruptions and meet the QoS needs of the application.
Power-performance simulation
Authors: Brooks David , Bose Pradip , Martonosi Margaret
Published: January 2007

Microprocessor research and development increasingly relies on detailed simulations to make design choices. As such, the structure, speed, and accuracy of microarchitectural simulators is of critical importance to the field. This paper describes our experiences in building two simulators, using related but distinct approaches.One of the most important attributes of a simulator is its ability to accurately convey design trends as different aspects of the microarchitecture are varied. In this work, we break down accuracy---a broad term--- into two sub-types:
relative
and
absolute
accuracy. We then discuss typical abstraction errors in power-performance simulators and show when they do (or do not) affect the design rule choices a user of those simulator might make. By performing this validation study using the Wattch and Power Timer simulators, the work addresses validation issues both broadly and in the specific case of a fairly widely-used simulator.
The inteligent system
Authors: Fritz W.
Published: January 2007

In this article, the brain is observed as a total system. A hypotesis of the various functions of the brain is set up and then partially tested through the workings of a computer program.
An investigation into inference with restricted quantification and a taxonomic representation
Authors: Frisch Alan M.
Published: January 2007

The goal of this investigation is to design and analyze efficient inference methods that arise when a representation language is augmented with restricted quantification and a taxonomic representation. These inference methods will be demonstrated by integrating them into the design of a logic-programming system and a knowledge retriever.
Reasoning about structure, behavior and function
Authors: Chandrasekaran B. , Milne Rob
Published: January 2007

The last several years' of work in the area of knowledge-based systems has resulted in a deeper understanding of the potentials of the current generation of ideas, but more importantly, also about their limitations and the need for research both in a broader framework as well as in new directions. The following ideas seem to us to be worthy of note in this connection.
Sixth generation computing
Authors: Gaines Brian R
Published: January 2007

This paper gives a precis of the sixth-generation computing systems research proposal,
Promotion of Research and Development on electronics and Information Systems That May Complement or Substitute for Human Intelligence
. The proposal was requested by the Japanese Ministry of Science and Technology in January 1983, prepared by the Subcommittee on Artificial Intelligence of The Council for Aerospace, Electronics and Other Advanced Technologies, and submitted in March 1985. It proposes an interdisciplinary research program on the nature of human intelligence involving physiology, psychology, linguistics, logic and computer science.
Suffixal derivative time-change analysis of sixteenth-century French
Authors: Tuttle Heath
Published: January 2007

In an effort to understand how language changes across time. I have taken advantage of the information inherent in the lexicon of the sixteenth-century writer, Francois Rabelais, whose five major works occurred, for the most part, at five different points in time in the middle third of that century. The unit of analysis, or point of focus, has been some seventy suffixes active in the century. Initially, using historicaletymological dictionaries, I examined Rabelais' sixteenth-century derivatives, seeking to discover if and what the relations were between the numbers of such words both synchronically and diachronically in the five books. A major finding was that derivatives of suffixes of disparate syntactic categories (e.g. forming nouns and verbs) are included by Rabelais in parallel quantities across time. A large number of -ement words in his first work are accompanied by relatively large numbers of -er words in that work, while the second work contains smaller numbers of the derivatives of the two suffixes, for example. But these rises and falls apply to one group of syntactically disparate, derivative-forming suffixes, while another pattern of rises and falls.(i.e. rising and falling derivative tallies) applies to another, potentially disparate, group of derivative-forming suffixes. Why this occurs I can only attribute to whatever constraint rules govern sentence generation and, concomitantly, entire narratives: A sentence or a story cannot consist of all verbs, for example. But our knowledge of these constraints is so sparse that the asking of such fundamental questions of composition, both diachronic and synchronic, even if such asking only begets more questions, is promising.
Review of "Genetic Algorithms for Machine Learning by John J. Greffenstette", Kluwer Academic Publishers, 1993.
Authors: Dracopoulos Dimitri C.
Published: January 2007

This book is a reprint from a special issue of the journalMachine Learningon Genetic Algorithms (GAs). The fact that it was the third special issue of the journal on GAs shows the continuous increase of interest of people in the field. The five selected articles were presented at the Fourth International Conference on Genetic Algorithms, in June 1991 (San Diego), and at a Special Workshop for Machine Learning at the same conference. The intended book audience is both researchers and practitioners in the field.
AAAI president's message
Authors: Newell Allen
Published: January 2007

Births are always interesting affairs. According to some, births are always traumatic - a shock to come from the womb to the world. The birth we give witness to here is that of a new society, the American Association for Artificial Intelligence - AAAI. It has not seemed to me traumatic, but rather almost wholly benign. In a world where not much is benign at the moment, such an event is devoutly to be cherished.
Model checking meets performance evaluation
Authors: Baier Christel , Haverkort Boudewijn R. , Hermanns Holger , Katoen Joost-Pieter
Published: January 2007

Markov chains are one of the most popular models for the evaluation of performance and dependability of information processing systems. To obtain performance measures, typically long-run or transient state probabilities of Markov chains are determined. Sometimes the Markov chain at hand is equipped with rewards and computations involve determining long-run or instantaneous reward probabilities.This note summarises a technique to determine performance and dependability
guarantees
of Markov chains. Given a precise description of the desired guarantee, all states in the Markov chain are determined that surely meet the guarantee. This is done in a fully automated way. Guarantees are described using logics. The use of logics yields an expressive framework that allows to express well-known measures, but also (new) intricate and complex performance guarantees. The power of this technique is that no matter how complex the logical guarantee, it is
automatically
checked which states in the Markov chain satisfy it. Neither manual manipulations of Markov chains (or their high-level descriptions) are needed, nor the knowledge of any numerical technique to analyze them efficiently. This applies to any (time-homogeneous) Markov chain of any structure specified in any high-level formalism.
Optimal scheduling using priced timed automata
Authors: Behrmann Gerd , Larsen Kim G. , Rasmussen Jacob I.
Published: January 2007

This contribution reports on the considerable effort made recently towards extending and applying well-established timed automata technology to optimal scheduling and planning problems. The effort of the authors in this direction has to a large extent been carried out as part of the European projects VHS [20] and AMETIST [16] and are available in the recently released UPPAAL CORA [12], a variant of the real-time verification tool UPPAAL [18, 5] specialized for cost-optimal reachability for the extended model of so-called priced timed automata.
LOGE
Authors: Grass W. , Lipp H. M.
Published: January 2007

Nearly all activities which have been published or which are known concentrate on those topics of computer-aided design related to layout of chips and boards and to testing and documentation. Systems which support logic design itself are not very widespread and are often out of focus. One of the inherent reasons may be that design engineers for whom CAD tools for logic design are developed, show a lot of scepticism and prejudice against those aids. They don't accept the idea that part of their personal work could be substituted by computer based algorithms.
The TREC robust retrieval track
Authors: Voorhees Ellen M.
Published: January 2007

The robust retrieval track explores methods for improving the consistency of retrieval technology by focusing on poorly performing topics. The retrieval task in the track is a traditional ad hoc retrieval task where the evaluation methodology emphasizes a system's least effective topics. The most promising approach to improving poorly performing topics is exploiting text collections other than the target collection such as the web.The track has also investigated appropriate evaluation measures to support the focus on ineffective topics. Traditional measure are dominated by the better-performing topics, and the first two measures used in the track that do emphasize the poorly performing topics are unstable in practice. A third measure, a variant of the traditional MAP measure that uses a geometric mean rather than an arithmetic mean to average individual topic results, shows promise of giving appropriate emphasis to poorly performing topics while being more stable at equal topic set sizes.
Denial-of-service resilience in peer-to-peer file sharing systems
Authors: Dumitriu D. , Knightly E. , Kuzmanovic A. , Stoica I. , Zwaenepoel W.
Published: January 2007

Peer-to-peer (p2p) file sharing systems are characterized by highly replicated content distributed among nodes with enormous aggregate resources for storage and communication. These properties alone are not sufficient, however, to render p2p networks immune to denial-of-service (DoS) attack. In this paper, we study, by means of analytical modeling and simulation, the resilience of p2p file sharing systems against DoS attacks, in which malicious nodes respond to queries with erroneous responses. We consider the file-targeted attacks in current use in the Internet, and we introduce a new class of p2p-network-targeted attacks.In file-targeted attacks, the attacker puts a large number of corrupted versions of a
single
file on the network. We demonstrate that the effectiveness of these attacks is highly dependent on the clients' behavior. For the attacks to succeed over the long term, clients must be unwilling to share files, slow in removing corrupted files from their machines, and quick to give up downloading when the system is under attack.In network-targeted attacks, attackers respond to queries for
any
file with erroneous information. Our results indicate that these attacks are highly scalable: increasing the number of malicious nodes yields a hyperexponential decrease in system goodput, and a moderate number of attackers suffices to cause a near-collapse of the entire system. The key factors inducing this vulnerability are (i) hierarchical topologies with misbehaving "supernodes," (ii) high path-length networks in which attackers have increased opportunity to falsify control information, and (iii) power-law networks in which attackers insert themselves into high-degree points in the graph.Finally, we consider the effects of client counter-strategies such as randomized reply selection, redundant and parallel download, and reputation systems. Some counter-strategies (e.g., randomized reply selection) provide considerable immunity to attack (reducing the scaling from hyperexponential to linear), yet significantly hurt performance in the absence of an attack. Other counter-strategies yield little benefit (or penalty). In particular, reputation systems show little impact unless they operate with near perfection.
A data streaming algorithm for estimating subpopulation flow size distribution
Authors: Kumar Abhishek , Sung Minho , Xu Jun (Jim) , Zegura Ellen W.
Published: January 2007

Statistical information about the flow sizes in the traffic passing through a network link helps a network operator to characterize network resource usage, infer traffic demands, detect traffic anomalies, and improve network performance through traffic engineering. Previous work on estimating the flow size distribution for thecomplete populationof flows has produced techniques that either make inferences from sampled network traffic, or use data streaming approaches. In this work, we identify and solve a more challenging problem of estimating the size distribution and other statistical information aboutarbitrary subpopulationsof flows. Inferring subpopulation flow statistics is more challenging than the complete population counterpart, since subpopulations of interest are often specifieda posteriori(i.e., after the data collection is done), making it impossible for the data collection module to "plan in advance".Our solution consists of a novel mechanism that combines data streaming with traditional packet sampling to provide highly accurate estimates of subpopulation flow statistics. The algorithm employs two data collection modules operating in parallel --- a NetFlow-like packet sampler and a streaming data structure made up of an array of counters. Combining the data collected by these two modules, our estimation algorithm uses a statistical estimation procedure that correlates and decodes the outputs (observations) from both data collection modules to obtain flow statistics for any arbitrary subpopulation. Evaluations of this algorithm on real-world Internet traffic traces demonstrate its high measurement accuracy.
On the performance characteristics of WLANs
Authors: Choi Sunwoong , Park Kihong , Kim Chong-kwon
Published: January 2007

Wide-spread deployment of infrastructure WLANs has made Wi-Fi an integral part of today's Internet access technology. Despite its crucial role in affecting end-to-end performance, past research has focused on MAC protocol enhancement, analysis and simulation-based performance evaluation without sufficient consideration for modeling inaccuracies stemming from inter-layer dependencies, including physical layer diversity, that significantly impact performance. We take a fresh look at IEEE 802.11 WLANs, and using a combination of experiment, simulation, and analysis demonstrate its surprisingly agile performance traits. Our main findings are two-fold. First, contention-based MAC throughput degrades gracefully under congested conditions, enabled by physical layer channel diversity that reduces the effective level of MAC contention. In contrast, fairness and jitter significantly degrade at a critical offered load. This duality obviates the need for link layer flow control for throughput improvement but necessitates traffic control for fairness and QoS. Second, TCP-over-WLAN achieves high throughput commensurate with that of wireline TCP under saturated conditions, challenging the widely held perception that TCP throughput fares poorly over WLANs when subject to heavy contention. We show that TCP-over-WLAN prowess is facilitated by the self-regulating actions of DCF and TCP congestion control that jointly drive the shared physical channel at an effective load of 2--3 wireless stations, even when the number of active stations is very large. Our results highlight subtle inter-layer dependencies including the mitigating influence of TCP-over-WLAN on dynamic rate shifting.
Modeling epidemic information dissemination on mobile devices with finite buffers
Authors: Lindemann Christoph , Waldhorst Oliver P.
Published: January 2007

Epidemic algorithms have recently been proposed as an effective solution for disseminating information in large-scale peer-to-peer (P2P) systems and in mobile ad hoc networks (MANET). In this paper, we present a modeling approach for steady-state analysis of epidemic dissemination of information in MANET. As major contribution, the introduced approach explicitly represents the spread of multiple data items, finite buffer capacity at mobile devices and a least recently used buffer replacement scheme. Using the introduced modeling approach, we analyze seven degrees of separation (7DS) as one well-known approach for implementing P2P data sharing in a MANET using epidemic dissemination of information. A validation of results derived from the analytical model against simulation shows excellent agreement. Quantitative performance curves derived from the analytical model yield several insights for optimizing the system design of 7DS.
Evaluating the number of active flows in a scheduler realizing fair statistical bandwidth sharing
Authors: Kortebi A. , Muscariello L. , Oueslati S. , Roberts J.
Published: January 2007

Despite its well-known advantages, per-flow fair queueing has not been deployed in the Internet mainly because of the common belief that such scheduling is not scalable. The objective of the present paper is to demonstrate using trace simulations and analytical evaluations that this belief is misguided. We show that although the number of flows
in progress
increases with link speed, the number that needs scheduling at any moment is largely independent of this rate. The number of such
active
flows is a random process typically measured in hundreds even though there may be tens of thousands of flows in progress. The simulations are performed using traces from commercial and research networks with quite different traffic characteristics. Analysis is based on models for balanced fair statistical bandwidth sharing and applies properties of queue busy periods to explain the observed behaviour.
Network utility maximization with nonconcave, coupled, and reliability-based uilities
Authors: Chiang Mung , Lee J. W. , Calderbank R. , Palomar D. , Fazel M.
Published: January 2007

Network Utility Maximization (NUM) has significantly extended the classical network flow problem and provided an emerging framework to design resource allocation algorithms such as TCP congestion control and to understand layering as optimization decomposition. We present a summary of very recent results in the theory and applications of NUM. We show new distributed algorithms that converge to the globally optimal rate allocation for NUM problems with nonconcave utility functions representing inelastic flows, with coupled utility functions representing interference effects or hybrid social-selfish utilities, and with rate-reliability tradeoff through adaptive channel coding in the physical layer. We conclude by discussing how do different decompositions of a generalized NUM problem correspond to different layering architectures.
Rate-adaptive time synchronization for long-lived sensor networks
Authors: Ganeriwal Saurabh , Ganesanl Deepak , Hansen Mark , Srivastava Mani B. , Estrin Deborah
Published: January 2007

Time synchronization is critical to sensor networks at many layers of its design and enables better duty-cycling of the radio, accurate localization, beamforming and other collaborative signal processing. While there has been significant work in sensor network synchronization, measurement based studies have been restricted to very short-term (few minutes) datasets and have focused on obtaining accurate instantaneous synchronization. Long-term synchronization has typically been handled by periodic re-synchronization schemes with beacon intervals of a few minutes based on the assumption that long-term drift is too hard to model and predict. Thus, none of this work exploits the temporally correlated behavior of the clock drift. Yet, there are incredible energy gains to be achieved from better modeling and prediction of long-term drift that can provide bounds on long-term synchronization error across a sensor network. Better synchronization can lead to significantly lower duty-cycles of the radio, simplify signal processing and can enable an order of magnitude greater lifetime than current techniques.We measure, evaluate and analyze in-depth the long-term behavior of synchronization skew and drift on typical Mica sensor nodes and develop an efficient long-term time synchronization protocol. We use four real time data sets gathered over periods of 12-30 hours in different environmental conditions to study the interplay between three key parameters that influence long-term synchronization - synchronization rate, history of past synchronization beacons and the estimation scheme. We use this measurement-based study to design an online adaptive time-synchronization algorithm that can adapt to changing clock drift and environmental conditions while achieving application-specified precision with very high probability. We find that our algorithm achieves between one and two orders of magnitude improvement in energy efficiency over currently available time-synchronization approaches.
Smooth switching problem in buffered crossbar switches
Authors: He Simin , Sun Shutao , Zhao Wei , Zheng Yanfeng , Gao Wen
Published: January 2007

Scalability considerations drive the switch fabric design to evolve from output queueing to input queueing and further to combined input and crosspoint queueing (CICQ). However, few CICQ switches are known with guaranteed quality of service, and credit-based flow control induces a scalability bottleneck. In this paper, we propose a novel CICQ switch called the smoothed buffered crossbar or sBUX, based on a new design objective of smoothness and on a new rate-based flow control scheme called the smoothed multiplexer or sMUX. It is proved that with a buffer of just four cells at each crosspoint, sBUX can utilize 100% of the switch capacity to provide deterministic guarantees of bandwidth and fairness, delay and jitter bounds for each flow. In particular, neither credit-based flow control nor speedup is used, and arbitrary fabric-internal latency is allowed between line cards and the switch core.
Characterizing the two-tier gnutella topology
Authors: Stutzbach Daniel , Rejaie Reza
Published: January 2007

Characterizing the properties of peer-to-peer (P2P) overlay topologies in file-sharing applications is essential for understanding their impact on the network, identifying their performance bottlenecks in practice, and evaluating their performance via simulation. Such characterization requires accurate snapshots of the overlay topology which is difficult to capture due to the large size and dynamic nature. Previous studies characterizing overlay topologies not only are outdated but also rely on partial or potentially distorted snapshots. In this extended abstract, we briefly present the first characterization of two-tier Gnutella topologies based on recent and accurate snapshots.
TurboSMARTS
Authors: Wenisch Thomas F. , Wunderlich Roland E. , Falsafi Babak , Hoe James C.
Published: January 2007

Recent research proposes accelerating processor microarchitecture simulation through statistical sampling. Prior simulation sampling approaches construct accurate model state for each measurement by continuously warming large microarchitectural structures (e.g., caches and the branch predictor) while emulating the billions of instructions between measurements. This approach, called functional warming, occupies hours of runtime while the detailed simulation that is measured requires mere minutes.To eliminate the functional warming bottleneck, we propose TurboSMARTS, a simulation framework that stores functionally-warmed state in a library of small, reusable checkpoints. TurboSMARTS enables the creation of the thousands of checkpoints necessary for accurate sampling by storing only the subset of warmed state accessed during simulation of each brief execution window. TurboSMARTS matches the accuracy of prior simulation sampling techniques (i.e., ±3% error with 99.7% confidence), while estimating the performance of an 8-way out-of-order super-scalar processor running SPEC CPU2000 in 91 seconds per benchmark, on average, using a 12 GB checkpoint library.
A reactive channel model for expediting wireless network simulation
Authors: Hu Chunyu , Hou Jennifer C.
Published: January 2007

A major problem with leveraging event-driven, packet-level simulation environments, such as
ns2
[6],
J-Sim
[1],
OpNet
[2]), and
QualNet
[3]), in conducting wireless network simulation is the vast number of events generated, a majority of which are related to signal transmission in the PHY/MAC layers.In this extended abstract, we investigate the operations of signal transmission in the various stages:
signal propagation
,
signal interference
, and
interaction with the PHY/MAC layers
, and identify where events can be reduced without impairing the accuracy. We propose to leverage the MAC/PHY state information, and devise (from the perspective of network simulation) a reactive channel model (RCM) in which nodes explicitly
register
their interests in receiving certain events according to the MAC/PHY states they are in and the corresponding operations that should be performed. The simulation study indicates that RCM renders an order of magnitude of speed-up without compromising the accuracy of simulation results. An advantage of RCM with respect to the implementation is that there is no need to re-design the channel model for each specific MAC layer, and the modification made in the MAC/PHY layers is quite modest (e.g., a few API changes). This, coupled with the performance gain, suggests that RCM is an attractive, light-weight mechanism for expediting wireless network simulation.
Message delay in MANET
Authors: Groenevelt Robin , Nain Philippe , Koole Ger
Published: January 2007

A generic stochastic model with only two input parameters is introduced to evaluate the message delay in mobile ad hoc networks (MANETs) where nodes may relay messages. The Laplace-Stieltjes transform (LST) of the message delay is obtained for two protocols: the two-hop and the unrestricted multicopy protocol. From these results we deduce the expected message delays. It is shown that, despite its simplicity, the model accurately predicts the message delay under both relay strategies for a number of mobility models (the random waypoint, random direction and the random walker mobility models).
Load sharing in limited access distributed systems
Authors: Harinarayan Venkatesh , Kleinrock Leonard
Published: January 2007

In this paper we examine dynamic load sharing in limited access distributed systems. In this class of distributed systems all servers are not accessible to all sources, and there exist many different accessibility topologies. We focus our attention on the ring topology and provide an analytic model to derive the approximate mean waiting time (our metric of performance). We then consider other limited access topologies and find that rather different interconnection patterns give similar performance measurements. We conjecture that the number of servers accessible to a source is the parameter with the greatest performance impact, in a limited access topology with load sharing. We also introduce another variable called diversity that is indicative of the degree of load sharing and speculate that performance is reasonably insensitive to diversity so long as it is non-zero. Using these conjectures we show how a reasonable estimate of the mean waiting time can be analytically derived in many limited access topologies.
Scheduling periodic and aperiodic tasks in hard real-time computing systems
Authors: Lin Tein-Hsiang , Tarng Wernhuar
Published: January 2007

Scheduling periodic and aperiodic tasks to meet their time constraints has been an important issue in the design of real-time computing systems. Usually, the task scheduling algorithms in such systems must satisfy the deadlines of periodic tasks and provide fast response times for aperiodic tasks. A simple and efficient approach to scheduling real-time tasks is the use of a periodic server in a static preemptive scheduling algorithm. Periodic tasks, including the server, are scheduled
at priori
to meet their deadlines according to the knowledge of their periods and computation times. The scheduling of aperiodic tasks is then managed by the periodic server during its service time. In this paper, a new scheduling algorithm is proposed. The new algorithm creates a periodic server which will have the highest priority but not necessarily the shortest period. The server is suspended to reduce the overhead if there are no aperiodic tasks waiting, and is activated immediately upon the arrival of the next aperiodic task. After activated, the server performs its duty periodically until all waiting aperiodic tasks are completed. For a set of tasks scheduled by this algorithm, the deadlines of periodic tasks are guaranteed by a deterministic feasibility check, and the mean response time of aperiodic tasks are estimated using a queueing model. Based on the analytical results, we can determine the period and service time of the server producing the minimum mean response time for aperiodic tasks. The analytical results are compared with simulation results to demonstrate the correctness of our model.
Performance analysis of concurrent-read exclusive-write
Authors: Reiman Martin , Wright Paul E.
Published: January 2007

We analyze the concurrent-read exclusive-write protocol for access to a shared resource, such as occurs in database and distributed operating systems. Readers arrive according to a Poisson process and acquire shareable i.e., non-exclusive, locks which, once granted, are released after a generally distributed random period. Writers arrive according to an arbitrary renewal process and acquire exclusive locks which, once granted, are held for a random time which is also generally distributed. Locks are granted in the order in which requests are received.We derive necessary and sufficient conditions under which the queue is stable i.e., the Iatencies for reader/writer lock acquisition have a limiting distribution. In the unstable case, the delays of successive readers/writers become unbounded. The stability condition is sensitive to the interarrival-time distribution of the writers and the lock holding-time distribution of the readers but depends only on the mean lock holding-time of the writers.Distributional and moment bounds are given for the latencies of read/write requests.
Instrumentation for a massively parallel MIMD application
Authors: Glenn R. R. , Pryor D. V.
Published: January 2007

This paper describes an application implemented on a simulated machine called Horizon. One purpose of this study is to investigate some of the features of a possible future machine (or class of machines) with a view toward deciding, early on in the research cycle, where problems may come up, what features should be added or strengthened, and what proposed features seem to be unnecessary. Another purpose is to learn more about how to program, instrument and debug a shared memory, massively parallel MIMD computer, and to begin to answer some of the questions: What tools does a programmer need to debug this type of machine? How can a programmer know if the machine is performing well? How can bottlenecks be identified? How can the massive amount of instrumentation information be condensed and presented to a user in a way that makes sense?
REDUCE
Authors: Hearn A. C.
Published: January 2007

We present here a REDUCE 2 [1] solution of the problem proposed by Campbell [2] for the computation of a class of functions useful in the phase-integral approximation. The program follows closely the published method (3). An alternative solution to the problem is given elsewhere in this issue [4].
Factoring multivariate polynomials over the integers
Authors: Wang Paul S. , Rothschild L. Preiss
Published: January 2007

This paper gives an algorithm for finding the irreducible factors of any multivariate polynomial with integer coefficients. The algorithm begins by making substitutions for all but one of the variable. This univariate polynomial is then factored by a known method, which uses an algorithm of Berlekamp for factoring univariate polynomials over finite fields. After this factorization is done, the multivariate factors are recovered from the univariate ones by a kind of Hensel algorithm. A number of ideas are given which greatly speed the computation in some special cases.
Tuning an algebraic manipulation system through measurements
Authors: Bahr Knut , Smit Jaap
Published: January 2007

This paper describes a measurement tool that has been used to analyze, tune, and redesign in part the PL/I-FORMAC Symbolic Mathematics Interpreter. In a number of examples, details are given both on the FORMAC system and on the application of the measurement tool. The basic tool, called invocation count measurement, is simple but quite effective. Its application enabled us to improve FORMAC considerably.