bluuebunny/crossref_metadata_2025 huggingface dataset:
Further results on equivalence and decomposition in queueing network models
Authors: Brandwajn Alexandre
Published: January 2007

This paper addresses three aspects related to the notion of exact equivalence in queueing models.

In many cases the parameters of a system equivalent to a given model involve only a small subset of conditional probabilities of the state of the original model given the equivalent one. It is shown that meaningful bounds may be obtained for the conditional probabilities of interest with little computational effort. Such bounds are useful in assessing processing capacities as well as the accuracy of approximate solutions.

As a second point it is shown that the notion of exact equivalence may be easily extended to networks with non-exponential servers. This is done for both the methods of supplementary variables and for the imbedded Markov chain technique. Qualitative analysis of approximation methods is also discussed.

Finally, numerical methods based on the notion of exact equivalence, i.e. operating on conditional probabilities, are considered.
On the performance of decentralized software
Authors: Balkovich Edward E. , Whitby-Strevens Colin
Published: January 2007

Distribution of computing to achieve goals such as enhanced reliability depend on the use of decentralized software. Decentralization typically replaces a sequential process by a system of small, concurrent processes that interact frequently. The implementation of processes and their interactions represents a cost incurred as a result of decentralization. Performance measurements are reported in this paper for decentralized software written in a programming language for distributed computer systems. These performance measurements confirm that low-cost implementations of concurrency are possible, but indicate that decentralized software makes heavy use of run-time functions managing concurrency. An initial model comparing the performance of a specific decentralized software structure to its centralized counterpart indicates that these implementation costs are generally offset by the performance improvements that are due to the parallelism inherent in the decentralized structure. The research facilities for continued study of decentralized software performance are described in the summary.
Performance of a multiprocessor for Applicative programs
Authors: Grit Dale H. , Page Rex L.
Published: January 2007

Applicative programming Languages provide opportunities for parallel processing without requiring the programmer to be concerned with explicit synchronization of portions of the computation. We present a computational model of a multiprocessor which executes applicative programs, and we analyze the expected performance of the model via simulation. As the number of processors is doubled, elapsed execution time is nearly halved, until system bottlenecks occur. An alternative model is proposed which alleviates these bottlenecks. The basis of the second model is an interconnection switch which is characterized by log(n) access time and n log(n) cost.
Analysis of an intrinsic overload control for a class of queueing systems
Authors: Wang Y. T.
Published: January 2007

We consider a priority queueing system which consists of two queues sharing a processor and in which there is delayed feedback. Such a model arises from systems which employ a priority assignment scheme to achieve overload control. An analytic expression for the stationary probability of the queue lengths is derived. An algorithm is proposed to compute the queue lengths distribution. Some numerical results are illustrated.
Analysis of locking policies in database management systems
Authors: Potier D. , Leblanc Ph.
Published: January 2007

Quantitative analysis of locking mechanisms and of their impact on the performance of transactionnal systems have yet received relatively little attention. Although numerous concurrency mechanisms have been proposed and implemented, there is an obvious lack of experimental as well as analytical studies of their behaviour and their influence on system performance. We present in this paper an analytical framework for the performance analysis of locking mechanisms in transactionnal systems based on hierarchical analytical modelling. Three levels of modelling are considered: at level 1, the different stages (lock request, execution, blocking) transactions of through during their life-time are described; the organization and operations of the CPU and I/O resources are analysed at level 2; transaction's behaviour during their lock request phase is analysed at modelling level 3.

This hierarchical approach is applied to the analysis of a physical locking scheme involving a static lock acquisition policy. A simple probabilistic model of the transaction behaviour is used to derived the probability that a new transaction is granted the locks it requests given the number of transactions already active as a function of the granularity of the database. On the other hand, the multiprogramming effect due to the sharing of CPU and I/O resources by transactions is analysed using the standard queueing network approaches and the solution package QNAP. In a final step, the results on the blocking probabilities and the multiprogrammin effect are used as input of a global performance model of the transactionnal system. Markovian analysis is used to solve this model and to obtain the throughput of the system as a function of the data base granularity and other parameters. The results obtained provide a clear understanding of the various factors which determine the global performance, of their role and improtance. They also raise many new issues which can only be solved by further extensive experimental and analytical studies and show that two particular topics deserve special attention: the modelling of transaction behaviour and the modelling of locking overheads.
Optimization of the number of copies in a distribution data base
Authors: Coffman E. G. , Gelenbe E. , Plateau B.
Published: January 2007

We consider the effect on system performance of the distribution of a data base in the form of multiple copies at distinct sites. The purpose of our analysis is to determine the gain in READ throughput that can be obtained in the presence of consistency preserving algorithms that have to be implemented when UPDATE operations are carried out on each copy. We show that READ throughput diminishes if the number of copies exceeds an optimal value. The theoretical model we develop is applied to a system in which consistency is preserved through the use of Ellis's ring algorithm.
Application prototyping
Authors: Jenkins C. Wesley
Published: January 2007

Accurate specification of user requirements for interactive systems is especially difficult in an environment where the demand for information is intense, short-fused and largely unpredictable.

The Congressional Budget Office was created in 1975 by an Act of Congress. Its primary mandate is to serve the Budget and Appropriation committees of both the Senate and the House of Representatives. The Act also defined a Congressional Budget process specifying a calendar of events and specific completion dates for major activities. This placing of budgetary actions produces a highly charged environment in which CBO must be able to respond immediately to information needs with information that is both accurate and consistent.
An approach to software configuration control
Authors: Bryan William , Siegel Stanley , Whiteleather Gary
Published: January 2007

The purpose of this paper is to discuss the process by which a system's life cycle and its associated life cycle products are managed to ensure the quality and integrity of the system. We call this process
configuration control
. Although many of the ideas in this paper are applicable to systems in general, the focus of this paper is on configuration control of systems with software content.

It is becoming apparent to many, in both government and private industry, that the high cost of maintenance of existing computer systems may be attributed to poor configuration control early in the system's life cycle. For example, in an article entitled "A Corporate Road, Map for Systems Development in the '80s, the following claim appears,
Implementing software configuration control in the structured programming environment
Authors: Berlack H. Ronald
Published: January 2007

The fundamental problems in the control of software are explored. The elements of control as they relate to communications is defined, and the implementation of these elements in solving the fundamental problems and achieving optimal control during a software development life cycle, is explained.

Control is defined as a vehicle for communicating changes to established, agreed-upon baseline points, made up of documents and subsequent computer programs. By communicating change to those involved or affected, and obtaining agreement of the change, one achieves a degree of control that does not inhibit software engineering innovation or progress, but helps maintain the project's prime objectives to deliver maintainable, error-free software to the ultimate user.
Producers and consumers views of software quality (Panel Session)
Authors: Gross Peter
Published: January 2007

At this very ACM workshop/symposium indicates, software quality is of great concern to both producers and users of software. It should be obvious to those who have attended the earlier sessions today and to those who will attend the sessions tomorrow that quality is something that cannot be tested into a system or added to a system. It must be integral from the start of the definition of the system's requirements through each phase of analysis, design, implementation, integration, testing, and installation.

Software quality implies an engineering type approach to the development of software. It implies the use of a disciplined development environment, and the use of tools and techniques to provide assurances throughout the software development process that both the software and its baseline specifications are complete, consistent, and traceable from one to another.
A bayesian differential debugging model for software reliability
Authors: Littlewood B.
Published: January 2007

An assumption commonly made in early models of software reliability is that the failure rate of a program is a constant multiple of the number of bugs remaining. This implies that all bugs have the same effect upon the overall failure rate. The assumption is challenged and an alternative proposed. The suggested model results in earlier bug-fixes having a greater effect than later ones (the worst bug show themselves earlier and so are fixed earlier), and the DFR properly between bug-fixes (confidence in programs increases during periods of failure-free operation, as well as at bug-fixes). The model shows a high degree of mathematical tractability, and allows a range of reliability, and allows a range of reliability measures to be calculated exactly. Predictions of total execution time to achieve a target reliability, are obtained.
When to stop testing and start using software?
Authors: Goel Amrit L. , Okumoto Kazuhira
Published: January 2007

During the last decade, numerous studies have been undertaken to quantify the failure process of large scale software systems. (see for example, references 1-12.) An important objective of these studies is to predict software performance and use the information for decision making. An important decision of practical concern is the determination of the amount of time that should be spent in testing. This decision of course will depend on the model used for describing the failure phenomenon and the criterion used for determining system readiness.

In this paper we present a cost model based on the time dependent fault detection rate model of Goel and Okumoto (4,5) and describe a policy that yields the optimal value of test time T.
Some experimental estimators for developmental and delivered errors in software development projects
Authors: Schneider Victor
Published: January 2007

Experimental estimators are presented relating the expected number of software problem reports (B) in a software development project to

the overall reported professional effort (E) in “man months”

the number of subprograms (n)

the overall count of thousands of coded source statements of software(S).

[equation]

These estimators are shown to be consistent with data obtained from the Air Force's Rome Air Development Center, the Naval Research Laboratory, and Japan's Fujitsu Corporation. Although the results are promising, more data is needed to support the validity of these estimators.
A model of Univac 1100/42 swapping
Authors: Dowdy Lawrence W. , Breitenlohner Hans J.
Published: January 2007

The performance of a computer system depends upon the efficiency of its swapping mechanisms. The swapping efficiency is a complex function of many variables. The degree of multiprogramming, the relative loading on the swapping devices, and the speed of the swapping devices are all interdependent variables that affect swapping performance.

In this paper, a model of swapping behavior is given. The interdependencies between the degree of multiprogramming, the swapping devices' loadings, and the swapping devices' speeds are modeled using an iterative scheme.

The validation of a model is its predictive capability. The given swapping model was applied to a Univac 1100/42 system to predict the effect of moving the swapping activity from drums to discs. When the swapping activity was actually moved, throughput
increased
by 20%. The model accurately predicted this improvement.

Subtopics discussed include: 1) the modeling of blocked and overlapped disc seek activity, 2) the usefulness of empirical formulae, and 3) the calibration of unmeasurable parameters. Extensions and further applications of the model are given.
A generative model of working set dynamics
Authors: Ferrari Domenico
Published: January 2007

An algorithm for generating a page reference string which exhibits a given working set size behavior in the time domain is presented, and the possible applications of such a string are discussed. The correctness of the algorithm is proved, and its computational complexity found to be linear in the length of the string. A program implementing the algorithm, which is performed in one pass and requires very little space, is briefly described, and some experimental results are given.
The solution of separable queueing network models using mean value analysis
Authors: Zahorjan John , Wong Eugene
Published: January 2007

Because it is more intuitively understandable than the previously existing convolution algorithms, Mean Value Analysis (MVA) has gained great popularity as an exact solution technique for separable queueing networks. However, the derivations of MVA presented to date apply only to closed queueing network models. Additionally, the problem of the storage requirement of MVA has not been dealt with satisfactorily. In this paper we address both these problems, presenting MVA solutions for open and mixed load independent networks, and a storage maintenance technique that we postulate is the minimum possible of any “reasonable” MVA technique.
Performance evaluation
Authors: Denning Peter J.
Published: January 2007

What is experimental computer science? This question has been widely discussed ever since the Feldman Report was published (1979 [18]). Many computer scientists believe that survival of their discipline is intimately linked to their ability to rejuvenate experimentation. The National Science Foundation instituted the Coordinated Experimental Research Program (CERP) in 1979 to help universities set up facilities capable of supporting experimental research. Other agencies of government are considering similar programs. Some industrial firms are offering similar help through modest cash grants and equipment discounts.

What is experimental computer science? Surprisingly, computer scientists disagree on the answer. A few believe that computer science is in flux—making a transition from theoretical to experimental science—and, hence, no operational definition is yet available. Some believe that it is all the non-theoretical activities of computer science, especially those conferring “hands-on” experience. Quite a few believe that it is large system development projects—i.e., computer and software engineering—and they cite MIT's Multics, Berkeley's version of Bell Labs' UNIX, the ARPAnet, IBM's database System R, and Xerox's Ethernet-based personal computer network as examples.

These beliefs are wrong. There are well-established standards for experimental science. The field of performance evaluation meets these standards and provides examples of experimental science for the rest of the computing field.
Structure and application of a measurement tool-SAMPLER/3000
Authors: Rafii Abbas
Published: January 2007

Design, internal structure, implementation experience and a number of unique features of the SAMPLER/3000 performance evaluation tool are presented. This package can be used to produce program CPU and wait time profiles in several levels of detail in terms of code segments, procedure names and procedure relative addresses. It also provides an accurate profile of the operating systems code which is exercised to service requests from the selective parts of the user code. Programs can be observed under natural load conditions in a single user or shared environment. A program's CPU usage is determined in terms of direct and indirect cost components. The approaches to determine direct and indirect CPU times are described. A program counter sampling technique in virtual memory domain is discussed. Certain interesting aspects of data analysis and on-line data presentation techniques are described. The features of the computer architecture, the services of the loader and compilers which relate to the operation of the tool are discussed. A case study is finally presented.
An event trace monitor for the VAX 11/780
Authors: Tolopka Stephen
Published: January 2007

This paper describes an event trace monitor implemented on Version 1.6 of the VMS operating system at Purdue University. Some necessary VMS terminology is covered first. The operation of the data gathering mechanism is then explained, and the events currently being gathered are listed. A second program, which reduces the data gathered by the monitor to usable form, is next examined, and some examples depicting its operation are given. The paper concludes with a brief discussion of some of the monitor's uses.
A combined evaluation of performance and reliability for degradable systems
Authors: Huslende Ragnar
Published: January 2007

As the field of fault-tolerant computing is maturing and results from this field are taken into practical use the effects of a failure in a computer system need not be catastrophic. With good fault-detection mechanisms it is now possible to cover a very high percentage of all the possible failures that can occur. Once a fault is detected, systems are designed to reconfigure and proceed either with full or degraded performance depending on how much redundancy is built into the system. It should be noted that one particular failure may have different effects depending on the circumstances and the time at which it occurs.

Today we see that large numbers of resources are being tied together in complex computer systems, either locally or in geographically distributed systems and networks. In such systems it is obviously very undesirable that the failure of one element can bring the entire system down. On the other hand one can usually not afford to design the system with sufficient redundancy to mask the effect of all failures immediately.
Modeling a new technique for accessing shared buses
Authors: Afshari P. V. , Bruell S. C. , Kain R. Y.
Published: January 2007

Consider a queueing system in which customers (or jobs) arrive to one of Q separate queues to await service from one of S identical servers (Figure 1). Once a job enters a queue it does not leave that queue until it has been selected for service. Any server can serve any job from any queue. A job selected for service cannot be preempted. In this paper we consider jobs to be in a single class; for the multiple class result see [AFSH81a]. We assume once a queue has been selected, job scheduling from that queue is fair. In particular, our results hold for first come first serve as well as random selection [SPIR79] and, for that matter, any fair nonpreemptive scheduling policy within a queue. We assume that arrivals to each queue follow a Poisson process with the mean arrival rate to queue q being λ
q
. The S identical exponential servers are each processing work at a mean rate of μ.

This system is general enough to be adaptable for modeling many different applications. By choosing the policy employed for queue selection by the servers, we can model multiplexers, channels, remote job entry stations, certain types of communication processors embedded in communication networks, and sets of shared buses. In this paper we will use the latter application to discuss a realistic situation. The elements (“jobs”) in the queues are messages to be sent from modules connected to the shared bus of the system. The servers are the buses; their service times are equal to the message transmission times. The queues are in the interface modules connected to and sharing the buses.
The determination of upper bounds for economically effective compression in packet switching networks
Authors: Aleh Avner , Levin K. Dan
Published: January 2007

This paper deals with the economic tradeoffs associated with data compression in a packet switching environment.

In section II we present the data profile concept and the compression analysis of typical file-transfer data strings. This is followed by a compression cost saving model that is developed in section III. Upper bounds for an economically effective compression service are derived there, and the paper concludes with an example of these bounds based on state of the art technology.
On updating buffer allocation
Authors: Thareja Ashok K. , Tripathi Satish K. , Upton Richard A.
Published: January 2007

Most of the analysis of buffer sharing schemes has been aimed at obtaining the optimal operational parameters under stationary load situations. It is well known that in most operating environments the traffic load changes. In this paper, we address the problem of updating buffer allocation as the traffic load at a network node changes. We investigate the behavior of a complete partitioning buffer sharing scheme to gain insight into the dependency of the throughput upon system parameters. The summary of the analysis is presented in the form of a heuristic. The heuristic is shown to perform reasonably well under two different types of stress tests.
A network performance analyst's workbench
Authors: Brice Richard , Alexander William
Published: January 2007

Performance measurement and analysis of the behavior of a computer network usually requires the application of multiple software and hardware tools. The location, functionality, data requirements, and other properties of the tools often reflect the distribution of equipment in the network. We describe how we have attempted to organize a collection of tools into a single system that spans a broad subset of the measurement and analysis activities that occur in a complex network of heterogenous computers. The tools are implemented on a pair of dedicated midicomputers. A database management system is used to couple the data collection and analysis tools into a system highly insulated from evolutionary changes in the composition and topology of the network.
A Hierarchical Modeling System for computer networks
Authors: DuBois Donald F.
Published: January 2007

This paper describes the Hierarchical Modeling System (HMS). HMS is a tool - a unified and expandable system - which supports the development of analytic and simulator models of computer networks. The same system and workload descriptions can be interpreted as analytic queueing models with optimization techniques or as discrete event simulation models. The rationale behind the development of HMS is that high level analyses incorporating analytic techniques may be used in the early design phase for networks when many options are considered while detailed simulation studies of fewer design alternatives are appropriate during the later stages.
The new field of “Software Linguistics”
Authors: Misek-Falkoff Linda D.
Published: January 2007

The phrase “Software Linguistics” is applied here to a text-based perspective on software quality matters. There is much in the new work on Software Metrics generally, and Software Science in particular, that is reminiscent of the activities of Natural Language analysis. Maurice Halstead held that Software Science could shed light on Linguistics; this paper sketches some mutually informing reciprocities between the two fields, and across related areas of textual, literary, discourse, and communications analysis.
Software Counting rules
Authors: Spiegel Mitchell G.
Published: January 2007

Counting rules in the software metrics field have been developed for counting such software measurables as the occurence of operators, operands and the number of lines of code. A variety of software metrics, such as those developed by Halstead and others, are computed from these numbers. Published material in the software metrics field has concentrated on relationships between various metrics, comparisions of values obtained for different languages, etc. Yet, little, if anything has been published on assumptions, experimental designs, or the nature of the counting tools (or programs) themselves used to obtain the basic measurements from which these metrics are calculated.
Effect of declarations on software metrics
Authors: Kavi Krishna M. , Jackson U. B.
Published: January 2007

The attractiveness of software science [HAL77] is to some extent due to the simplicity of its instrumentation. Upon learning the detailed rules of counting operators and operands, the experiments and derivations using various algorithms and languages can be repeated. Proposed or actual applications of software science are quite varied (For example, see [SEN79]). The size and construction time of a program can be estimated from the problem specification and the choice of programming language. An estimate of the number of program bugs can be shown to depend on programming effort. Optimal choice of module sizes for multimodule implementations can be computed. Elements of software science have applications to the analysis of technical prose.

The purpose of this experiment is three fold. First, we want to apply software science metrics to the language 'C'.

The second purpose of the experiment is to study the effect of including declaration statements while counting operators and operands.

Finally, we have set out to determine whether the area of application has any influence on software science metrics.
A unification of Halstead's Software Science counting rules for programs and English text, and a claim space approach to extensions
Authors: Misek-Falkoff Linda D.
Published: January 2007

In his
Elements of Software Science
, Maurice Halstead proposed that software quality measurements could be based on static lexemic analysis of the vocabularies of operators and operands, and the number of occurrences of each class, in computer programs. He also proposed that quality issues in Natural Language text could be addressed from similar perspectives, although his rules for programs and for English seem to conflict.

This paper suggests that Halstead's seemingly disparate rules for classifying the tokens of programs and the tokens of English can be generally reconciled, although Halstead himself does not claim such a union. The thesis of Part One is a unification of his two procedures, based on a linguistic partitioning between “open” and “closed” classes. This unification may provide new inputs to some open issues concerning coding, and suggest, on the basis of a conceptual rationale, an explanation as to why programs which are by Halstead's definition “impure” might indeed be confusing to the human reader.

Part Two of this paper, by exploring the nodes in a textual “Claim Space,” briefly considers other groupings of the classes taken as primitive by Halstead, in ways which bring to light alternate and supplementary sets of candidate coding rules productive for study of textual quality.
APL and Halstead's theory
Authors: Laurmaa Timo , Syrjänen Markku
Published: January 2007

We have designed and implemented an algorithm which measures APL-programs in the sense of software science by M.H. Halstead /1/. The reader is assumed to be familiar with the theories of software science.

Our purpose has been to find the best possible algorithm to automatically analyse large quantities of APL-programs. We have also used our measuring tool to make some experiments to find out if APL-programs and workspaces obey the laws of software science or not.

Becasue our purpose was to analyse large quantities, i.e. hundreds of programs we have not implemented an algorithm, which gives exactly correct results from software science point of view, because this would necessitate manual clues to the analysing algorithm and thus an interactive mode of analysis. Instead of it we have strived for a tool, which carries out the analysis automatically and as correctly as possible.

In the next section some difficulties encountered in the design of the measuring algorithm and some inherent limitations of it are discussed. Section 3 summarises the sources of errors in the analysis carried out by our algorithm, while section 4 gives a more detailed description of the way analysis is carried out.

The remaining sections of this paper report on some experiments we have carried out using our measuring tool. The purpose of these experiments has been to evaluate the explaining power of Halstead's theory in connection of APL-programs. However, no attempt has been made to process the results of the experiments statistically. The results of the experiments have been treated here only when 'obvious' (in)compatibilities between the theory and the results have been observed. Possible reasons for the (in)compatibilities are also pointed out.
Foundations and experiments in software science
Authors: Beser Nicholas
Published: January 2007

A number of papers have appeared on the subject of software science; claiming the existence of laws relating the size of a program and the number of operands and operators used. The pre-eminent theory was developed by Halstead in 1972. The thesis work focuses on the examination of Halstead's theory; with an emphasis on his fundamental assumptions. In particular, the length estimator was analyzed to determine why it yields such a high variance; the theoretical foundations of software science have been extended to improve the applicability of the critical length estimator. This elaboration of the basic theory will result in guidelines for the creation of counting rules applicable to specific classes of programs, so that it is possible to determine both when and how software science can be applied in practice.
Product assurance program analyzer (P.A.P.A.) a tool for program complexity evaluation
Authors: Schnurer Karl Ernst
Published: January 2007

This tool has been developed to assist in the software validation process. P.A.P.A. will measure the complexity of programs and detect several program anomalies. The resulting list of analyzed programs is sorted in order of descending complexity. Since high complexity and error-proneness are strongly related, the “critical” programs will be found earlier within the development cycle.

P.A.P.A. provides syntax analyzers for RPG (II/III), PSEUDOCODE (design and documentation language) and PL/SIII (without macro language). It may be applied during the design-, coding- and testphase of software development (e.g. for design- and code inspections).
Complexity measurement of Electronic Switching System (ESS) software
Authors: Gross David R. , King Mary A. , Murr Michael R. , Eddy Michael R.
Published: January 2007

We have been developing a tool that measures the complexity of software: 1) to predict the quality of software products and 2) to allocate proportionally more testing resources to complex modules. The software being measured is real-time and controls telephone switching systems. This software system is large and its development is distributed over a period of several years, with each release providing enhancements and bug fixes.

We have developed a two-stage tool consisting of a parser and an analyzer. The parser operates on the source code and produces operator, operand, and miscellaneous tables. These tables are then processed by an analyzer program that calculates the complexity measures. Changes for tuning our Halstead counting rules involve simple changes to the analyzer only. During the development there were problems and issues to be confronted dealing with static analysis and code metrics. These are also described in this paper.

In several systems we found that more than 80% of software failures can be traced to only 20% of the modules in the system. The McCabe complexity and some of Halstead's metrics score higher than the count of executable statements in their correlations with field failures. It is reasonable to expect that we could devote more effort to the review and test of high-complexity modules and increase the quality of the software product that we send to the field.
Report on DISCO '90
Authors: Winkler Franz
Published: January 2007

The growing importance of systems for symbolic computation has greatly influenced the decision to organize the International Symposium on Design and Implementation of Symbolic Computation Systems, DISCO '90. It took place in Capri, Italy, April 10-12, 1990, with the partecipation of about 120 researchers of several european and extraeuropean countries. DISCO '90 has been the first international event in the field, organized and sponsored by Italian Universities, Institutes of the Italian National Research Council and industry, in cooperation with: ACM, AICA, AiiA, EATCS, ECCAI, SAME, SIGSAM
A comparative evaluation of graphical user interfaces
Authors: Ebner Rainer , Haring Gunter , Penz Franz , Weichselberger Gerhard
Published: January 2007

In a study based on a questionnaire and an empirical test three graphical user interfaces for the DOS operating system commands (GEM, Windows 1.04, Windows 2.01) are compared.
Using graphs to explore databases and create reports
Authors: Barr Robert
Published: January 2007

In most information systems that use them, graphs "illustrate" the numbers in a crosstab- or list-style report. However, they can also be employed both to explore a database to locate wanted data, and to retrieve data from the database to create a report.
A graphical user interface to support a production team
Authors: DiPietro Stephen M.
Published: January 2007

This paper describes the user interface of a software system that supports production of a large geographic database. The user interface of the system facilitates coordination of a production team whose activities are separated in time and space. The user interface provides visibility into the status and organization of the production effort and provides easy access to the tools and data required to perform the work.
Book review: AN INTRODUCTION TO HUMAN-COMPUTER INTERACTION by Paul Booth (Erlbaum: 1989)
Authors: Carey Tom
Published: January 2007

From the cover: "The book provides an overview of the diverse research areas that are only gradually building into a coherent and well-structured field. It aims to explain the underlying causes of the cognitive, social and organizational problems typically encountered when computer systems are introduced."
Measuring adversaries
Authors: Paxson Vern
Published: January 2007

Many concepts and techniques developed for general Internet measurement have counterparts in the domain of detecting and analyzing network attacks. The task is greatly complicated, however, by the fact that the object of study is
adversarial
: attackers do not wish to be "measured" and will take steps to thwart observation. We look at the far-ranging consequences of this different measurement environment: the analysis difficulties-some fundamental-that arise due to subtle ambiguities in the true semantics of observed traffic; new notions of "active measurement"; the highly challenging task of rapidly characterizing Internet-scale pheonmena such as global worm pandemics; the need for detailed application-level analysis and related policy and legal difficulties; attacks that target passive analysis tools; and the inherent "arms race" nature of the undertaking.
Flow classification by histograms
Authors: Soule Augustin , Salamatia Kavé , Taft Nina , Emilion Richard , Papagiannaki Konstantina
Published: January 2007

In order to control and manage highly aggregated Internet traffic flows efficiently, we need to be able to categorize flows into distinct classes and to be knowledgeable about the different behavior of flows belonging to these classes. In this paper we consider the problem of classifying BGP level prefix flows into a small set of homogeneous classes. We argue that using the entire distributional properties of flows can have significant benefits in terms of quality in the derived classification. We propose a method based on modeling flow histograms using Dirichlet Mixture Processes for random distributions. We present an inference procedure based on the Simulated Annealing Expectation Maximization algorithm that estimates all the model parameters as well as flow
membership probabilities
- the probability that a flow belongs to any given class. One of our key contributions is a new method for Internet flow classification. We show that our method is powerful in that it is capable of examining macroscopic flows while simultaneously making fine distinctions between different traffic classes. We demonstrate that our scheme can address issues with flows being close to class boundaries and the inherent dynamic behaviour of Internet flows.
Two-level processor-sharing scheduling disciplines
Authors: Aalto Samuli , Ayesta Urtzi , Nyberg-Oksanen Eeva
Published: January 2007

Inspired by several recent papers that focus on scheduling disciplines for network flows, we present a mean delay analysis of Multilevel Processor Sharing (MLPS) scheduling disciplines in the context of M/G/1 queues. Such disciplines have been proposed to model the effect of the differentiation between short and long TCP flows in the Internet. Under MLPS, jobs are classified into classes depending on their attained service. We consider scheduling disciplines where jobs within the same class are served either with Processor Sharing (PS) or Foreground Background (FB) policy, and the class that contains jobs with the smallest attained service is served first. It is known that the FB policy minimizes (maximizes) the mean delay when the hazard rate of the job size distribution is decreasing (increasing). Our analysis, based on pathwise and meanwise arguments of the unfinished truncated work, shows that Two-Level Processor Sharing (TLPS) disciplines, e.g., FB+PS and PS+PS, are better than PS scheduling when the hazard rate of the job size distribution is decreasing. If the hazard rate is increasing and bounded, we show that PS outperforms PS+PS and FB+PS. We further extend our analysis to study local optimality within a level of an MLPS scheduling discipline.
Performance analysis of LAS-based scheduling disciplines in a packet switched network
Authors: Rai Idris A. , Urvoy-Keller Guillaume , Vernon Mary K. , Biersack Ernst W.
Published: January 2007

The Least Attained Service (LAS) scheduling policy, when used for scheduling packets over the bottleneck link of an Internet path, can greatly reduce the average flow time for short flows while not significantly increasing the average flow time for the long flows that share the same bottleneck. No modification of the packet headers is required to implement the simple LAS policy. However, previous work has also shown that a drawback of the LAS scheduler is that, when link utilization is greater than 70%, long flows experience large jitter in their packet transfer times as compared to the conventional First-Come-First-Serve (FCFS) link scheduling. This paper proposes and evaluates new differentiated LAS scheduling policies that reduce the jitter for long flows that are identified as "priority" flows.To evaluate the new policies, we develop analytic models to estimate average flow transfer time as a function of flow size, and average packet transmission time as a function of position in the flow, for the single-bottleneck "dumbbell topology" used in many ns simulation studies. Models are developed for FCFS scheduling, LAS scheduling, and each of the new differentiated LAS scheduling policies at the bottleneck link. Over a wide range of configu-rations, the analytic estimates agree very closely with the ns estimates. Thus, the analytic models can be used instead of simulation for comparing the policies with respect to mean flow transfer time (as a function of flow size) and mean packet transfer time. Furthermore, an initial discrepancy between the analytic and simulation estimates revealed errors in the parameter values that are often specified in the widely used ns Web workload generator. We develop an improved Web workload specification, which is used to estimate the packet jitter for long flows (more accurately than with previous simulation workloads).Results for the scheduling policies show that a particular policy, LAS-log, greatly improves the mean flow transfer time for priority long flows while providing performance similar to LAS for the ordinary flows. Simulations show that the LAS-log policy also greatly reduces the jitter in packet delivery times for the priority flows.
A resource-allocation queueing fairness measure
Authors: Raz David , Levy Hanoch , Avi-Itzhak Benjamin
Published: January 2007

Fairness is a major issue in the operation of queues, perhaps it is the reason why queues were formed in the first place. Recent studies show that the fairness of a queueing system is important to customers not less than the actual delay they experience. Despite this observation little research has been conducted to study fairness in queues, and no commonly agreed upon measure of queue fairness exists. Two recent research exceptions are Avi-Itzhak and Levy [1], where a fairness measure is proposed, and Wierman and Harchol-Balter [18] (this conference, 2003), where a
criterion
is proposed for classifying service policies as fair or unfair; the criterion focuses on customer service requirement and deals with fairness with respect to service times.In this work we recognize that the inherent behavior of a queueing system is governed by two major factors: Job
seniority
(arrival times) and job
service requirement
(service time). Thus, it is desired that a queueing fairness measure would account for both. To this end we propose a Resource Allocation Queueing Fairness Measure, (RAQFM), that accounts for both relative job seniority and relative service time. The measure allows accounting for individual job discrimination as well as system unfairness. The system measure forms a full scale that can be used to evaluate the level of unfairness under various queueing disciplines. We present several basic properties of the measure. We derive the individual measure as well as the system measure for an M/M/1 queue under five fundamental service policies: Processor Sharing (PS), First Come First Served (FCFS), Non-Preemptive Last Come First Served (NP-LCFS), Preemptive Last Come First Served (P-LCFS), and Random Order of Service (ROS). The results of RAQFM are then compared to those of Wierman and Harchol-Balter [18], and the quite intriguing observed differences are discussed.
ACCEL-RATE
Authors: Hao Fang , Kodialam Murali , Lakshman T. V.
Published: January 2007

Per-flow network traffic measurement is an important component of network traffic management, network performance assessment, and detection of anomalous network events such as incipient DoS attacks. In [1], the authors developed a mechanism called RATE where the focus was on developing a memory efficient scheme for estimating per-flow traffic rates to a specified level of accuracy. The time taken by RATE to estimate the per-flow rates is a function of the specified estimation accuracy and this time is acceptable for several applications. However some applications, such as quickly detecting worm related activity or the tracking of transient traffic, demand faster estimation times. The main contribution of this paper is a new scheme called ACCEL-RATE that, for a specified level of accuracy, can achieve orders of magnitude decrease in per-flow rate estimation times. It achieves this by using a hashing scheme to split the incoming traffic into several sub-streams, estimating the per-flow traffic rates in each of the substreams and then relating it back to the original per-flow traffic rates. We show both theoretically and experimentally that the estimation time of ACCEL-RATE is at least one to two orders of magnitude lower than RATE without any significant increase in the memory size.
A game theoretic approach to provide incentive and service differentiation in P2P networks
Authors: Ma Richard T. B. , Lee Sam C. M. , Lui John C. S. , Yau David K. Y.
Published: January 2007

Traditional peer-to-peer (P2P) networks do not provide service differentiation and incentive for users. Consequently, users can obtain services without themselves contributing any information or service to a P2P community. This leads to the "free-riding" and "tragedy of the commons" problems, in which the majority of information requests are directed towards a small number of P2P nodes willing to share their resources. The objective of this work is to enable service differentiation in a P2P network based on the amount of services each node has provided to its community, thereby encouraging all network nodes to share resources. We first introduce a resource distribution mechanism between all information sharing nodes. The mechanism is driven by a distributed algorithm which has linear time complexity and guarantees Pareto-optimal resource allocation. Besides giving incentive, the mechanism distributes resources in a way that increases the aggregate utility of the whole network. Second, we model the whole resource request and distribution process as a competition game between the competing nodes. We show that this game has a Nash equilibrium and is collusion-proof. To realize the game, we propose a protocol in which all competing nodes interact with the information providing node to reach Nash equilibrium in a dynamic and efficient manner. Experimental results are reported to illustrate that the protocol achieves its service differentiation objective and can induce productive information sharing by rational network nodes. Finally, we show that our protocol can properly adapt to different node arrival and departure events, and to different forms of network congestion.
On zone-balancing of peer-to-peer networks
Authors: Wang Xiaoming , Zhang Yueping , Li Xiafeng , Loguinov Dmitri
Published: January 2007

Balancing peer-to-peer graphs, including zone-size distributions, has recently become an important topic of peer-to-peer (P2P) research [1], [2], [6], [19], [31], [36]. To bring analytical understanding into the various peer-join mechanisms, we study how zone-balancing decisions made during the initial sampling of the peer space affect the resulting zone sizes and derive several asymptotic results for the maximum and minimum zone sizes that hold with high probability.