title: Tractability of Theory Patching

abstract:
  In this paper we consider the problem of `theory patching', in which we are
given a domain theory, some of whose components are indicated to be possibly
flawed, and a set of labeled training examples for the domain concept. The
theory patching problem is to revise only the indicated components of the
theory, such that the resulting theory correctly classifies all the training
examples. Theory patching is thus a type of theory revision in which revisions
are made to individual components of the theory. Our concern in this paper is
to determine for which classes of logical domain theories the theory patching
problem is tractable. We consider both propositional and first-order domain
theories, and show that the theory patching problem is equivalent to that of
determining what information contained in a theory is `stable' regardless of
what revisions might be performed to the theory. We show that determining
stability is tractable if the input theory satisfies two conditions: that
revisions to each theory component have monotonic effects on the classification
of examples, and that theory components act independently in the classification
of examples in the theory. We also show how the concepts introduced can be used
to determine the soundness and completeness of particular theory patching
algorithms.


title: Integrative Windowing

abstract:
  In this paper we re-investigate windowing for rule learning algorithms. We
show that, contrary to previous results for decision tree learning, windowing
can in fact achieve significant run-time gains in noise-free domains and
explain the different behavior of rule learning algorithms by the fact that
they learn each rule independently. The main contribution of this paper is
integrative windowing, a new type of algorithm that further exploits this
property by integrating good rules into the final theory right after they have
been discovered. Thus it avoids re-learning these rules in subsequent
iterations of the windowing process. Experimental evidence in a variety of
noise-free domains shows that integrative windowing can in fact achieve
substantial run-time gains. Furthermore, we discuss the problem of noise in
windowing and present an algorithm that is able to achieve run-time gains in a
set of experiments in a simple domain with artificial noise.


title: Model-Based Diagnosis using Structured System Descriptions

abstract:
  This paper presents a comprehensive approach for model-based diagnosis which
includes proposals for characterizing and computing preferred diagnoses,
assuming that the system description is augmented with a system structure (a
directed graph explicating the interconnections between system components).
Specifically, we first introduce the notion of a consequence, which is a
syntactically unconstrained propositional sentence that characterizes all
consistency-based diagnoses and show that standard characterizations of
diagnoses, such as minimal conflicts, correspond to syntactic variations on a
consequence. Second, we propose a new syntactic variation on the consequence
known as negation normal form (NNF) and discuss its merits compared to standard
variations. Third, we introduce a basic algorithm for computing consequences in
NNF given a structured system description. We show that if the system structure
does not contain cycles, then there is always a linear-size consequence in NNF
which can be computed in linear time. For arbitrary system structures, we show
a precise connection between the complexity of computing consequences and the
topology of the underlying system structure. Finally, we present an algorithm
that enumerates the preferred diagnoses characterized by a consequence. The
algorithm is shown to take linear time in the size of the consequence if the
preference criterion satisfies some general conditions.


title:
A Selective Macro-learning Algorithm and its Application to the NxN
  Sliding-Tile Puzzle

abstract:
  One of the most common mechanisms used for speeding up problem solvers is
macro-learning. Macros are sequences of basic operators acquired during problem
solving. Macros are used by the problem solver as if they were basic operators.
The major problem that macro-learning presents is the vast number of macros
that are available for acquisition. Macros increase the branching factor of the
search space and can severely degrade problem-solving efficiency. To make macro
learning useful, a program must be selective in acquiring and utilizing macros.
This paper describes a general method for selective acquisition of macros.
Solvable training problems are generated in increasing order of difficulty. The
only macros acquired are those that take the problem solver out of a local
minimum to a better state. The utility of the method is demonstrated in several
domains, including the domain of NxN sliding-tile puzzles. After learning on
small puzzles, the system is able to efficiently solve puzzles of any size.


title: Chess Pure Strategies are Probably Chaotic

abstract:
  It is odd that chess grandmasters often disagree in their analysis of
positions, sometimes even of simple ones, and that a grandmaster can hold his
own against an powerful analytic machine such as Deep Blue. The fact that there
must exist pure winning strategies for chess is used to construct a control
strategy function. It is then shown that chess strategy is equivalent to an
autonomous system of differential equations, and conjectured that the system is
chaotic. If true the conjecture would explain the forenamed peculiarities and
would also imply that there cannot exist a static evaluator for chess.


title: Downward Collapse from a Weaker Hypothesis

abstract:
  Hemaspaandra et al. proved that, for $m > 0$ and $0 < i < k - 1$: if
$\Sigma_i^p \BoldfaceDelta DIFF_m(\Sigma_k^p)$ is closed under complementation,
then $DIFF_m(\Sigma_k^p) = coDIFF_m(\Sigma_k^p)$. This sharply asymmetric
result fails to apply to the case in which the hypothesis is weakened by
allowing the $\Sigma_i^p$ to be replaced by any class in its difference
hierarchy. We so extend the result by proving that, for $s,m > 0$ and $0 < i <
k - 1$: if $DIFF_s(\Sigma_i^p) \BoldfaceDelta DIFF_m(\Sigma_k^p)$ is closed
under complementation, then $DIFF_m(\Sigma_k^p) = coDIFF_m(\Sigma_k^p)$.


title:
Creating Strong Total Commutative Associative Complexity-Theoretic
  One-Way Functions from Any Complexity-Theoretic One-Way Function

abstract:
  Rabi and Sherman [RS97] presented novel digital signature and unauthenticated
secret-key agreement protocols, developed by themselves and by Rivest and
Sherman. These protocols use ``strong,'' total, commutative (in the case of
multi-party secret-key agreement), associative one-way functions as their key
building blocks. Though Rabi and Sherman did prove that associative one-way
functions exist if $\p \neq \np$, they left as an open question whether any
natural complexity-theoretic assumption is sufficient to ensure the existence
of ``strong,'' total, commutative, associative one-way functions. In this
paper, we prove that if $\p \neq \np$ then ``strong,'' total, commutative,
associative one-way functions exist.


title:
Differentiated End-to-End Internet Services using a Weighted
  Proportional Fair Sharing TCP

abstract:
  In this document we study the application of weighted proportional fairness
to data flows in the Internet. We let the users set the weights of their
connections in order to maximise the utility they get from the network. When
combined with a pricing scheme where connections are billed by weight and time,
such a system is known to maximise the total utility of the network. Our study
case is a national Web cache server connected to long distance links. We
propose two ways of weighting TCP connections by manipulating some parameters
of the protocol and present results from simulations and prototypes. We finally
discuss how proportional fairness could be used to implement an Internet with
differentiated services.


title: First-Order Conditional Logic Revisited

abstract:
  Conditional logics play an important role in recent attempts to formulate
theories of default reasoning. This paper investigates first-order conditional
logic. We show that, as for first-order probabilistic logic, it is important
not to confound statistical conditionals over the domain (such as ``most birds
fly''), and subjective conditionals over possible worlds (such as ``I believe
that Tweety is unlikely to fly''). We then address the issue of ascribing
semantics to first-order conditional logic. As in the propositional case, there
are many possible semantics. To study the problem in a coherent way, we use
plausibility structures. These provide us with a general framework in which
many of the standard approaches can be embedded. We show that while these
standard approaches are all the same at the propositional level, they are
significantly different in the context of a first-order language. Furthermore,
we show that plausibilities provide the most natural extension of conditional
logic to the first-order case: We provide a sound and complete axiomatization
that contains only the KLM properties and standard axioms of first-order modal
logic. We show that most of the other approaches have additional properties,
which result in an inappropriate treatment of an infinitary version of the
lottery paradox.


title: Set-Theoretic Completeness for Epistemic and Conditional Logic

abstract:
  The standard approach to logic in the literature in philosophy and
mathematics, which has also been adopted in computer science, is to define a
language (the syntax), an appropriate class of models together with an
interpretation of formulas in the language (the semantics), a collection of
axioms and rules of inference characterizing reasoning (the proof theory), and
then relate the proof theory to the semantics via soundness and completeness
results. Here we consider an approach that is more common in the economics
literature, which works purely at the semantic, set-theoretic level. We provide
set-theoretic completeness results for a number of epistemic and conditional
logics, and contrast the expressive power of the syntactic and set-theoretic
approaches


title: Plausibility Measures and Default Reasoning

abstract:
  We introduce a new approach to modeling uncertainty based on plausibility
measures. This approach is easily seen to generalize other approaches to
modeling uncertainty, such as probability measures, belief functions, and
possibility measures. We focus on one application of plausibility measures in
this paper: default reasoning. In recent years, a number of different semantics
for defaults have been proposed, such as preferential structures,
$\epsilon$-semantics, possibilistic structures, and $\kappa$-rankings, that
have been shown to be characterized by the same set of axioms, known as the KLM
properties. While this was viewed as a surprise, we show here that it is almost
inevitable. In the framework of plausibility measures, we can give a necessary
condition for the KLM axioms to be sound, and an additional condition necessary
and sufficient to ensure that the KLM axioms are complete. This additional
condition is so weak that it is almost always met whenever the axioms are
sound. In particular, it is easily seen to hold for all the proposals made in
the literature.


title: Computational Geometry Column 34

abstract:
  Problems presented at the open-problem session of the 14th Annual ACM
Symposium on Computational Geometry are listed.


title: The Computational Complexity of Probabilistic Planning

abstract:
  We examine the computational complexity of testing and finding small plans in
probabilistic planning domains with both flat and propositional
representations. The complexity of plan evaluation and existence varies with
the plan type sought; we examine totally ordered plans, acyclic plans, and
looping plans, and partially ordered plans under three natural definitions of
plan value. We show that problems of interest are complete for a variety of
complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the
process of proving that certain planning problems are complete for NP^PP, we
introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the
standard Boolean satisfiability problem to computations involving probabilistic
quantities; our results suggest that the development of good heuristics for
E-MAJSAT could be important for the creation of efficient algorithms for a wide
variety of problems.


title: Immunity and Simplicity for Exact Counting and Other Counting Classes

abstract:
  Ko [RAIRO 24, 1990] and Bruschi [TCS 102, 1992] showed that in some
relativized world, PSPACE (in fact, ParityP) contains a set that is immune to
the polynomial hierarchy (PH). In this paper, we study and settle the question
of (relativized) separations with immunity for PH and the counting classes PP,
C_{=}P, and ParityP in all possible pairwise combinations. Our main result is
that there is an oracle A relative to which C_{=}P contains a set that is
immune to BPP^{ParityP}. In particular, this C_{=}P^A set is immune to PH^{A}
and ParityP^{A}. Strengthening results of Tor\'{a}n [J.ACM 38, 1991] and Green
[IPL 37, 1991], we also show that, in suitable relativizations, NP contains a
C_{=}P-immune set, and ParityP contains a PP^{PH}-immune set. This implies the
existence of a C_{=}P^{B}-simple set for some oracle B, which extends results
of Balc\'{a}zar et al. [SIAM J.Comp. 14, 1985; RAIRO 22, 1988] and provides the
first example of a simple set in a class not known to be contained in PH. Our
proof technique requires a circuit lower bound for ``exact counting'' that is
derived from Razborov's [Mat. Zametki 41, 1987] lower bound for majority.


title: Tally NP Sets and Easy Census Functions

abstract:
  We study the question of whether every P set has an easy (i.e.,
polynomial-time computable) census function. We characterize this question in
terms of unlikely collapses of language and function classes such as the
containment of #P_1 in FP, where #P_1 is the class of functions that count the
witnesses for tally NP sets. We prove that every #P_{1}^{PH} function can be
computed in FP^{#P_{1}^{#P_{1}}}. Consequently, every P set has an easy census
function if and only if every set in the polynomial hierarchy does. We show
that the assumption of #P_1 being contained in FP implies P = BPP and that PH
is contained in MOD_{k}P for each k \geq 2, which provides further evidence
that not all sets in P have an easy census function. We also relate a set's
property of having an easy census function to other well-studied properties of
sets, such as rankability and scalability (the closure of the rankable sets
under P-isomorphisms). Finally, we prove that it is no more likely that the
census function of any set in P can be approximated (more precisely, can be
n^{\alpha}-enumerated in time n^{\beta} for fixed \alpha and \beta) than that
it can be precisely computed in polynomial time.


title: Common knowledge revisited

abstract:
  We consider the common-knowledge paradox raised by Halpern and Moses: common
knowledge is necessary for agreement and coordination, but common knowledge is
unattainable in the real world because of temporal imprecision. We discuss two
solutions to this paradox: (1) modeling the world with a coarser granularity,
and (2) relaxing the requirements for coordination.


title: Performance / Price Sort

abstract:
  NTsort is an external sort on WindowsNT 5.0. It has minimal functionality but
excellent price performance. In particular, running on mail-order hardware it
can sort 1.5 GB for a penny. For commercially available sorts, Postman Sort
from Robert Ramey Software Development has elapsed time performance comparable
to NTsort, while using less processor time. It can sort 1.27 GB for a penny
(12.7 million records.) These sorts set new price-performance records. This
paper documents this and proposes that the PennySort benchmark be revised to
Performance/Price sort: a simple GB/$ sort metric based on a two-pass external
sort.


title:
The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules
  of Thumb

abstract:
  Simple economic and performance arguments suggest appropriate lifetimes for
main memory pages and suggest optimal page sizes. The fundamental tradeoffs are
the prices and bandwidths of RAMs and disks. The analysis indicates that with
today's technology, five minutes is a good lifetime for randomly accessed
pages, one minute is a good lifetime for two-pass sequentially accessed pages,
and 16 KB is a good size for index pages. These rules-of-thumb change in
predictable ways as technology ratios change. They also motivate the importance
of the new Kaps, Maps, Scans, and $/Kaps, $/Maps, $/TBscan metrics.


title:
The Design and Architecture of the Microsoft Cluster Service -- A
  Practical Approach to High-Availability and Scalability

abstract:
  Microsoft Cluster Service (MSCS) extends the Win-dows NT operating system to
support high-availability services. The goal is to offer an execution
environment where off-the-shelf server applications can continue to operate,
even in the presence of node failures. Later ver-sions of MSCS will provide
scalability via a node and application management system that allows
applications to scale to hundreds of nodes. This paper provides a de-tailed
description of the MSCS architecture and the de-sign decisions that have driven
the implementation of the service. The paper also describes how some major
appli-cations use the MSCS features, and describes features added to make it
easier to implement and manage fault-tolerant applications on MSCS.


title: Locally Served Network Computers

abstract:
  NCs are the natural evolution of PCs, ubiquitous computers everywhere. The
current vision of NCs requires two improbable developments: (1) inexpensive
high-bandwidth WAN links to the Internet, and (2) inexpensive centralized
servers. The large NC bandwidth requirements will force each home or office to
have a local server LAN attached to the NCs. These servers will be much less
expensive to purchase and manage than a centralized solution. Centralized staff
are expensive and unresponsive.


title:
Comparing the expressive power of the Synchronous and the Asynchronous
  pi-calculus

abstract:
  The Asynchronous pi-calculus, as recently proposed by Boudol and,
independently, by Honda and Tokoro, is a subset of the pi-calculus which
contains no explicit operators for choice and output-prefixing. The
communication mechanism of this calculus, however, is powerful enough to
simulate output-prefixing, as shown by Boudol, and input-guarded choice, as
shown recently by Nestmann and Pierce. A natural question arises, then, whether
or not it is possible to embed in it the full pi-calculus. We show that this is
not possible, i.e. there does not exist any uniform, parallel-preserving,
translation from the pi-calculus into the asynchronous pi-calculus, up to any
``reasonable'' notion of equivalence. This result is based on the incapablity
of the asynchronous pi-calculus of breaking certain symmetries possibly present
in the initial communication graph. By similar arguments, we prove a separation
result between the pi-calculus and CCS.


title: Developing numerical libraries in Java

abstract:
  The rapid and widespread adoption of Java has created a demand for reliable
and reusable mathematical software components to support the growing number of
compute-intensive applications now under development, particularly in science
and engineering. In this paper we address practical issues of the Java language
and environment which have an effect on numerical library design and
development. Benchmarks which illustrate the current levels of performance of
key numerical kernels on a variety of Java platforms are presented. Finally, a
strategy for the development of a fundamental numerical toolkit for Java is
proposed and its current status is described.


title: The Revolution Yet to Happen

abstract:
  All information about physical objects including humans, buildings,
processes, and organizations will be online. This trend is both desirable and
inevitable. Cyberspace will provide the basis for wonderful new ways to inform,
entertain, and educate people. The information and the corresponding systems
will streamline commerce, but will also provide new levels of personal service,
health care, and automation. The most significant benefit will be a
breakthrough in our ability to remotely communicate with one another using all
our senses.
  The ACM and the transistor were born in 1947. At that time the stored program
computer was a revolutionary idea and the transistor was just a curiosity. Both
ideas evolved rapidly. By the mid 1960s integrated circuits appeared --
allowing mass fabrication of transistors on silicon substrates. This allowed
low-cost mass-produced computers. These technologies enabled extraordinary
increases in processing speed and memory coupled with extraordinary price
declines.
  The only form of processing and memory more easily, cheaply, and rapidly
fabricated is the human brain. Peter Cohrane (1996) estimates the brain to have
a processing power of around 1000 million-million operations per second, (one
Petaops) and a memory of 10 Terabytes. If current trends continue, computers
could have these capabilities by 2047. Such computers could be 'on body'
personal assistants able to recall everything one reads, hears, and sees.


title: Microsoft TerraServer

abstract:
  The Microsoft TerraServer stores aerial and satellite images of the earth in
a SQL Server Database served to the public via the Internet. It is the world's
largest atlas, combining five terabytes of image data from the United States
Geodetic Survey, Sovinformsputnik, and Encarta Virtual Globe. Internet browsers
provide intuitive spatial and gazetteer interfaces to the data. The TerraServer
is also an E-Commerce application. Users can buy the right to use the imagery
using Microsoft Site Servers managed by the USGS and Aerial Images. This paper
describes the TerraServer's design and implementation.


title:
A Fully Polynomial Randomized Approximation Scheme for the All Terminal
  Network Reliability Problem

abstract:
  The classic all-terminal network reliability problem posits a graph, each of
whose edges fails independently with some given probability.


title: Reasoning about Noisy Sensors and Effectors in the Situation Calculus

abstract:
  Agents interacting with an incompletely known world need to be able to reason
about the effects of their actions, and to gain further information about that
world they need to use sensors of some sort. Unfortunately, both the effects of
actions and the information returned from sensors are subject to error. To cope
with such uncertainties, the agent can maintain probabilistic beliefs about the
state of the world. With probabilistic beliefs the agent will be able to
quantify the likelihood of the various outcomes of its actions and is better
able to utilize the information gathered from its error-prone actions and
sensors. In this paper, we present a model in which we can reason about an
agent's probabilistic degrees of belief and the manner in which these beliefs
change as various actions are executed. We build on a general logical theory of
action developed by Reiter and others, formalized in the situation calculus. We
propose a simple axiomatization that captures an agent's state of belief and
the manner in which these beliefs change when actions are executed. Our model
displays a number of intuitively reasonable properties.


title: Uniform Provability in Classical Logic

abstract:
  Uniform proofs are sequent calculus proofs with the following characteristic:
the last step in the derivation of a complex formula at any stage in the proof
is always the introduction of the top-level logical symbol of that formula. We
investigate the relevance of this uniform proof notion to structuring proof
search in classical logic. A logical language in whose context provability is
equivalent to uniform provability admits of a goal-directed proof procedure
that interprets logical symbols as search directives whose meanings are given
by the corresponding inference rules. While this uniform provability property
does not hold directly of classical logic, we show that it holds of a fragment
of it that only excludes essentially positive occurrences of universal
quantifiers under a modest, sound, modification to the set of assumptions: the
addition to them of the negation of the formula being proved. We further note
that all uses of the added formula can be factored into certain derived rules.
The resulting proof system and the uniform provability property that holds of
it are used to outline a proof procedure for classical logic. An interesting
aspect of this proof procedure is that it incorporates within it previously
proposed mechanisms for dealing with disjunctive information in assumptions and
for handling hypotheticals. Our analysis sheds light on the relationship
between these mechanisms and the notion of uniform proofs.


title:
Correspondences between Classical, Intuitionistic and Uniform
  Provability

abstract:
  Based on an analysis of the inference rules used, we provide a
characterization of the situations in which classical provability entails
intuitionistic provability. We then examine the relationship of these
derivability notions to uniform provability, a restriction of intuitionistic
provability that embodies a special form of goal-directedness. We determine,
first, the circumstances in which the former relations imply the latter. Using
this result, we identify the richest versions of the so-called abstract logic
programming languages in classical and intuitionistic logic. We then study the
reduction of classical and, derivatively, intuitionistic provability to uniform
provability via the addition to the assumption set of the negation of the
formula to be proved. Our focus here is on understanding the situations in
which this reduction is achieved. However, our discussions indicate the
structure of a proof procedure based on the reduction, a matter also considered
explicitly elsewhere.


title:
Scoping Constructs in Logic Programming: Implementation Problems and
  their Solution

abstract:
  The inclusion of universal quantification and a form of implication in goals
in logic programming is considered. These additions provide a logical basis for
scoping but they also raise new implementation problems. When universal and
existential quantifiers are permitted to appear in mixed order in goals, the
devices of logic variables and unification that are employed in solving
existential goals must be modified to ensure that constraints arising out of
the order of quantification are respected. Suitable modifications that are
based on attaching numerical tags to constants and variables and on using these
tags in unification are described. The resulting devices are amenable to an
efficient implementation and can, in fact, be assimilated easily into the usual
machinery of the Warren Abstract Machine (WAM). The provision of implications
in goals results in the possibility of program clauses being added to the
program for the purpose of solving specific subgoals. A naive scheme based on
asserting and retracting program clauses does not suffice for implementing such
additions for two reasons. First, it is necessary to also support the
resurrection of an earlier existing program in the face of backtracking.
Second, the possibility for implication goals to be surrounded by quantifiers
requires a consideration of the parameterization of program clauses by bindings
for their free variables. Devices for supporting these additional requirements
are described as also is the integration of these devices into the WAM. Further
extensions to the machine are outlined for handling higher-order additions to
the language. The ideas presented here are relevant to the implementation of
the higher-order logic programming language lambda Prolog.


title: The Complexity of Planar Counting Problems

abstract:
  We prove the #P-hardness of the counting problems associated with various
satisfiability, graph and combinatorial problems, when restricted to planar
instances. These problems include \begin{romannum} \item[{}] {\sc 3Sat, 1-3Sat,
1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set, Minimum Feedback Vertex
Set, X3C, Partition Into Triangles, and Clique Cover.} \end{romannum} We also
prove the {\sf NP}-completeness of the {\sc Ambiguous Satisfiability} problems
\cite{Sa80} and the {\sf D$^P$}-completeness (with respect to random polynomial
reducibility) of the unique satisfiability problems \cite{VV85} associated with
several of the above problems, when restricted to planar instances. Previously,
very few {\sf #P}-hardness results, no {\sf NP}-hardness results, and no {\sf
D$^P$}-completeness results were known for counting problems, ambiguous
satisfiability problems and unique satisfiability problems, respectively, when
restricted to planar instances.
  Assuming {\sf P $\neq $ NP}, one corollary of the above results is
  There are no $\epsilon$-approximation algorithms for the problems of
maximizing or minimizing a linear objective function subject to a planar system
of linear inequality constraints over the integers.


title: Influencing Software Usage

abstract:
  Technology designers often strive to design systems that are flexible enough
to be used in a wide range of situations. Software engineers, in particular,
are trained to seek general solutions to problems. General solutions can be
used not only to address the problem at hand, but also to address a wide range
of problems that the designers may not have even anticipated. Sometimes
designers wish to provide general solutions, while encouraging certain uses of
their technology and discouraging or precluding others. They may attempt to
influence the use of technology by ``hard-wiring'' it so that it only can be
used in certain ways, licensing it so that those who use it are legally
obligated to use it in certain ways, issuing guidelines for how it should be
used, or providing resources that make it easier to use the technology as the
designers intended than to use it in any other way.
  This paper examines several cases where designers have attempted to influence
the use of technology through one of these mechanisms. Such cases include key
recovery encryption, Pegasus Mail, Platform for Internet Content Selection
(PICS) Guidelines, Java, Platform for Privacy Preferences Project (P3P)
Implementation Guide, Apple's style guidelines, and Microsoft Foundation
Classes. In some of these cases, the designers sought to influence the use of
technology for competitive reasons or in order to promote standardization or
interoperability. However, in other cases designers were motivated by
policy-related goals such as protecting privacy or free speech. As new
technologies are introduced with the express purpose of advancing
policy-related goals (for example, PICS and P3P), it is especially important to
understand the roles designers might play in influencing the use of technology.


title: Distributed Computation as Hierarchy

abstract:
  This paper presents a new distributed computational model of distributed
systems called the phase web that extends V. Pratt's orthocurrence relation
from 1986. The model uses mutual-exclusion to express sequence, and a new kind
of hierarchy to replace event sequences, posets, and pomsets. The model
explicitly connects computation to a discrete Clifford algebra that is in turn
extended into homology and co-homology, wherein the recursive nature of objects
and boundaries becomes apparent and itself subject to hierarchical recursion.
Topsy, a programming environment embodying the phase web, is available from
www.cs.auc.dk/topsy.


title: Linear Segmentation and Segment Significance

abstract:
  We present a new method for discovering a segmental discourse structure of a
document while categorizing segment function. We demonstrate how retrieval of
noun phrases and pronominal forms, along with a zero-sum weighting scheme,
determines topicalized segmentation. Futhermore, we use term distribution to
aid in identifying the role that the segment performs in the document. Finally,
we present results of evaluation in terms of precision and recall which surpass
earlier approaches.


title: Producing NLP-based On-line Contentware

abstract:
  For its internal needs as well as for commercial purposes, CDC Group has
produced several NLP-based on-line contentware applications for years. The
development process of such applications is subject to numerous constraints
such as quality of service, integration of new advances in NLP, direct
reactions from users, continuous versioning, short delivery deadlines and cost
control. Following this industrial and commercial experience, malleability of
the applications, their openness towards foreign components, efficiency of
applications and their ease of exploitation have appeared to be key points. In
this paper, we describe TalLab, a powerful architecture for on-line contentware
which fulfils these requirements.


title: Modelling Users, Intentions, and Structure in Spoken Dialog

abstract:
  We outline how utterances in dialogs can be interpreted using a partial first
order logic. We exploit the capability of this logic to talk about the truth
status of formulae to define a notion of coherence between utterances and
explain how this coherence relation can serve for the construction of AND/OR
trees that represent the segmentation of the dialog. In a BDI model we
formalize basic assumptions about dialog and cooperative behaviour of
participants. These assumptions provide a basis for inferring speech acts from
coherence relations between utterances and attitudes of dialog participants.
Speech acts prove to be useful for determining dialog segments defined on the
notion of completing expectations of dialog participants. Finally, we sketch
how explicit segmentation signalled by cue phrases and performatives is covered
by our dialog model.


title: Similarity-Based Queries for Time Series Data

abstract:
  We study a set of linear transformations on the Fourier series representation
of a sequence that can be used as the basis for similarity queries on
time-series data. We show that our set of transformations is rich enough to
formulate operations such as moving average and time warping. We present a
query processing algorithm that uses the underlying R-tree index of a
multidimensional data set to answer similarity queries efficiently. Our
experiments show that the performance of this algorithm is competitive to that
of processing ordinary (exact match) queries using the index, and much faster
than sequential scanning. We relate our transformations to the general
framework for similarity queries of Jagadish et al.


title: A Lexicalized Tree Adjoining Grammar for English

abstract:
  This document describes a sizable grammar of English written in the TAG
formalism and implemented for use with the XTAG system. This report and the
grammar described herein supersedes the TAG grammar described in an earlier
1995 XTAG technical report. The English grammar described in this report is
based on the TAG formalism which has been extended to include lexicalization,
and unification-based feature structures. The range of syntactic phenomena that
can be handled is large and includes auxiliaries (including inversion), copula,
raising and small clause constructions, topicalization, relative clauses,
infinitives, gerunds, passives, adjuncts, it-clefts, wh-clefts, PRO
constructions, noun-noun modifications, extraposition, determiner sequences,
genitives, negation, noun-verb contractions, sentential adjuncts and
imperatives. This technical report corresponds to the XTAG Release 8/31/98. The
XTAG grammar is continuously updated with the addition of new analyses and
modification of old ones, and an online version of this report can be found at
the XTAG web page at http://www.cis.upenn.edu/~xtag/


title: Novelty and Social Search in the World Wide Web

abstract:
  The World Wide Web is fast becoming a source of information for a large part
of the world's population. Because of its sheer size and complexity users often
resort to recommendations from others to decide which sites to visit. We
present a dynamical theory of recommendations which predicts site visits by
users of the World Wide Web. We show that it leads to a universal power law for
the number of users that visit given sites over periods of time, with an
exponent related to the rate at which users discover new sites on their own. An
extensive empirical study of user behavior in the Web that we conducted
confirms the existence of this law of influence while yielding bounds on the
rate of novelty encountered by users.


title: Prefix Probabilities from Stochastic Tree Adjoining Grammars

abstract:
  Language models for speech recognition typically use a probability model of
the form Pr(a_n | a_1, a_2, ..., a_{n-1}). Stochastic grammars, on the other
hand, are typically used to assign structure to utterances. A language model of
the above form is constructed from such grammars by computing the prefix
probability Sum_{w in Sigma*} Pr(a_1 ... a_n w), where w represents all
possible terminations of the prefix a_1 ... a_n. The main result in this paper
is an algorithm to compute such prefix probabilities given a stochastic Tree
Adjoining Grammar (TAG). The algorithm achieves the required computation in
O(n^6) time. The probability of subderivations that do not derive any words in
the prefix, but contribute structurally to its derivation, are precomputed to
achieve termination. This algorithm enables existing corpus-based estimation
techniques for stochastic TAGs to be used for language modelling.


title: Conditions on Consistency of Probabilistic Tree Adjoining Grammars

abstract:
  Much of the power of probabilistic methods in modelling language comes from
their ability to compare several derivations for the same string in the
language. An important starting point for the study of such cross-derivational
properties is the notion of _consistency_. The probability model defined by a
probabilistic grammar is said to be _consistent_ if the probabilities assigned
to all the strings in the language sum to one. From the literature on
probabilistic context-free grammars (CFGs), we know precisely the conditions
which ensure that consistency is true for a given CFG. This paper derives the
conditions under which a given probabilistic Tree Adjoining Grammar (TAG) can
be shown to be consistent. It gives a simple algorithm for checking consistency
and gives the formal justification for its correctness. The conditions derived
here can be used to ensure that probability models that use TAGs can be checked
for _deficiency_ (i.e. whether any probability mass is assigned to strings that
cannot be generated).


title: Separating Dependency from Constituency in a Tree Rewriting System

abstract:
  In this paper we present a new tree-rewriting formalism called Link-Sharing
Tree Adjoining Grammar (LSTAG) which is a variant of synchronous TAGs. Using
LSTAG we define an approach towards coordination where linguistic dependency is
distinguished from the notion of constituency. Such an approach towards
coordination that explicitly distinguishes dependencies from constituency gives
a better formal understanding of its representation when compared to previous
approaches that use tree-rewriting systems which conflate the two issues.


title: Incremental Parser Generation for Tree Adjoining Grammars

abstract:
  This paper describes the incremental generation of parse tables for the
LR-type parsing of Tree Adjoining Languages (TALs). The algorithm presented
handles modifications to the input grammar by updating the parser generated so
far. In this paper, a lazy generation of LR-type parsers for TALs is defined in
which parse tables are created by need while parsing. We then describe an
incremental parser generator for TALs which responds to modification of the
input grammar by updating parse tables built so far.


title:
Fast, Approximate Synthesis of Fractional Gaussian Noise for Generating
  Self-Similar Network Traffic

abstract:
  Recent network traffic studies argue that network arrival processes are much
more faithfully modeled using statistically self-similar processes instead of
traditional Poisson processes [LTWW94,PF95]. One difficulty in dealing with
self-similar models is how to efficiently synthesize traces (sample paths)
corresponding to self-similar traffic. We present a fast Fourier transform
method for synthesizing approximate self-similar sample paths for one type of
self-similar process, Fractional Gaussian Noise, and assess its performance and
validity. We find that the method is as fast or faster than existing methods
and appears to generate close approximations to true self-similar sample paths.
We also discuss issues in using such synthesized sample paths for simulating
network traffic, and how an approximation used by our method can dramatically
speed up evaluation of Whittle's estimator for H, the Hurst parameter giving
the strength of long-range dependence present in a self-similar time series.


title:
Security amplification by composition: The case of doubly-iterated,
  ideal ciphers

abstract:
  We investigate, in the Shannon model, the security of constructions
corresponding to double and (two-key) triple DES. That is, we consider
F_{k1}(F_{k2}(.)) and F_{k1}(F_{k2}^{-1}(F_{k1}(.))) with the component
functions being ideal ciphers. This models the resistance of these
constructions to ``generic'' attacks like meet in the middle attacks. We obtain
the first proof that composition actually increases the security of these
constructions in some meaningful sense. We compute a bound on the probability
of breaking the double cipher as a function of the number of computations of
the base cipher made, and the number of examples of the composed cipher seen,
and show that the success probability is the square of that for a single key
cipher. The same bound holds for the two-key triple cipher. The first bound is
tight and shows that meet in the middle is the best possible generic attack
against the double cipher.


title: Stable models and an alternative logic programming paradigm

abstract:
  In this paper we reexamine the place and role of stable model semantics in
logic programming and contrast it with a least Herbrand model approach to Horn
programs. We demonstrate that inherent features of stable model semantics
naturally lead to a logic programming system that offers an interesting
alternative to more traditional logic programming styles of Horn logic
programming, stratified logic programming and logic programming with
well-founded semantics. The proposed approach is based on the interpretation of
program clauses as constraints. In this setting programs do not describe a
single intended model, but a family of stable models. These stable models
encode solutions to the constraint satisfaction problem described by the
program. Our approach imposes restrictions on the syntax of logic programs. In
particular, function symbols are eliminated from the language. We argue that
the resulting logic programming system is well-attuned to problems in the class
NP, has a well-defined domain of applications, and an emerging methodology of
programming. We point out that what makes the whole approach viable is recent
progress in implementations of algorithms to compute stable models of
propositional logic programs.


title: Efficient Retrieval of Similar Time Sequences Using DFT

abstract:
  We propose an improvement of the known DFT-based indexing technique for fast
retrieval of similar time sequences. We use the last few Fourier coefficients
in the distance computation without storing them in the index since every
coefficient at the end is the complex conjugate of a coefficient at the
beginning and as strong as its counterpart. We show analytically that this
observation can accelerate the search time of the index by more than a factor
of two. This result was confirmed by our experiments, which were carried out on
real stock prices and synthetic data.


title: Semantics and Conversations for an Agent Communication Language

abstract:
  We address the issues of semantics and conversations for agent communication
languages and the Knowledge Query Manipulation Language (KQML) in particular.
Based on ideas from speech act theory, we present a semantic description for
KQML that associates ``cognitive'' states of the agent with the use of the
language's primitives (performatives). We have used this approach to describe
the semantics for the whole set of reserved KQML performatives. Building on the
semantics, we devise the conversation policies, i.e., a formal description of
how KQML performatives may be combined into KQML exchanges (conversations),
using a Definite Clause Grammar. Our research offers methods for a speech act
theory-based semantic description of a language of communication acts and for
the specification of the protocols associated with these acts. Languages of
communication acts address the issue of communication among software
applications at a level of abstraction that is useful to the emerging software
agents paradigm.


title: Separation-Sensitive Collision Detection for Convex Objects

abstract:
  We develop a class of new kinetic data structures for collision detection
between moving convex polytopes; the performance of these structures is
sensitive to the separation of the polytopes during their motion. For two
convex polygons in the plane, let $D$ be the maximum diameter of the polygons,
and let $s$ be the minimum distance between them during their motion. Our
separation certificate changes $O(\log(D/s))$ times when the relative motion of
the two polygons is a translation along a straight line or convex curve,
$O(\sqrt{D/s})$ for translation along an algebraic trajectory, and $O(D/s)$ for
algebraic rigid motion (translation and rotation). Each certificate update is
performed in $O(\log(D/s))$ time. Variants of these data structures are also
shown that exhibit \emph{hysteresis}---after a separation certificate fails,
the new certificate cannot fail again until the objects have moved by some
constant fraction of their current separation. We can then bound the number of
events by the combinatorial size of a certain cover of the motion path by
balls.


title:
Document Archiving, Replication and Migration Container for Mobile Web
  Users

abstract:
  With the increasing use of mobile workstations for a wide variety of tasks
and associated information needs, and with many variations of available
networks, access to data becomes a prime consideration. This paper discusses
issues of workstation mobility and proposes a solution wherein the data
structures are accessed in an encapsulated form - through the Portable File
System (PFS) wrapper. The paper discusses an implementation of the Portable
File System, highlighting the architecture and commenting upon performance of
an experimental system. Although investigations have been focused upon mobile
access of WWW documents, this technique could be applied to any mobile data
access situation.


title: Regression Depth and Center Points

abstract:
  We show that, for any set of n points in d dimensions, there exists a
hyperplane with regression depth at least ceiling(n/(d+1)). as had been
conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n
hyperplanes in d dimensions there exists a point that cannot escape to infinity
without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our
approach to related questions on the existence of partitions of the data into
subsets such that a common plane has nonzero regression depth in each subset,
and to the computational complexity of regression depth problems.


title: Incremental and Decremental Maintenance of Planar Width

abstract:
  We present an algorithm for maintaining the width of a planar point set
dynamically, as points are inserted or deleted. Our algorithm takes time
O(kn^epsilon) per update, where k is the amount of change the update causes in
the convex hull, n is the number of points in the set, and epsilon is any
arbitrarily small constant. For incremental or decremental update sequences,
the amortized time per update is O(n^epsilon).


title: ABR Flow Control for Multipoint Connections

abstract:
  Multipoint capabilities are essential for ATM networks to efficiently support
many applications, including IP multicasting and overlay applications. The
current signaling and routing specifications for ATM define point-to-multipoint
capabilities. Multipoint-to-point connection support is also being discussed by
the signaling and PNNI groups, and will be defined in the near future for the
unspecified bit rate (UBR) service. We examine point-to-multipoint and
multipoint-to-point flow control for the available bit rate (ABR) service, as
discussed in the traffic management working group.


title: Overload Based Explicit Rate Switch Schemes with MCR Guarantees

abstract:
  An explicit rate switch scheme monitors the load at each link and gives
feedback to the sources. We define the overload factor as the ratio of the
input rate to the available capacity. In this paper, we present four overload
based ABR switch schemes which provide MCR guarantees. The switch schemes
proposed use the overload factor and other quantities to calculate feedback
rates. A dynamic queue control mechanism is used to achieve efficient usage of
the link, control queues and, achieve constant queuing delay at steady state.
The proposed algorithms are studied and compared using several configurations.
The configurations were chosen to test the performance of the algorithms in
presence of link bottlenecks, source bottlenecks and transient sources. A
comparison of the proposed algorithms based on the simulation results is
presented.


title:
Design and Analysis of Queue Control Functions for Explicit Rate Switch
  Schemes

abstract:
  The main goals of a switch scheme are high utilization, low queuing delay and
fairness. To achieve high utilization the switch scheme can maintain non-zero
(small) queues in steady state which can be used if the sources do not have
data to send. Queue length (delay) can be controlled if part of the link
capacity is used for draining queues in the event of queue build up. In most
schemes a simple threshold function is used for queue control. Better control
of the queue and hence delay can be achieved by using sophisticated queue
control functions. It is very important to design and analyze such queue
control functions. We study step, linear, hyperbolic and inverse hyperbolic
queue control functions. Analytical explanation and simulation results
consistent with analysis are presented. From the study, we conclude that
inverse hyperbolic is the best control function and to reduce complexity the
linear control function can be used since it performs satisfactorily in most
cases.


title:
A Definition of General Weighted Fairness and its Support in Explicit
  Rate Switch Algorithms

abstract:
  In this paper we give a general definition of weighted fairness and show how
this can achieve various fairness definitions, such as those mentioned in the
ATM Forum TM 4.0 Specifications. We discuss how a pricing policy can be mapped
to general weighted (GW) fairness. The GW fairness can be achieved by
calculating the $ExcessFairshare$ (weighted fairshare of the left over
bandwidth) for each VC. We show how a switch algorithm can be modified to
support the GW fairness by using the $ExcessFairshare$. We use ERICA+ as an
example switch algorithm and show how it can be modified to achieve the general
fairness. Simulations results are presented to demonstrate that the modified
switch algorithm achieves GW fairness. An analytical proof for convergence of
the modified ERICA+ algorithm is given in the appendix.


title: Worst Case Buffer Requirements For Tcp Over ABR

abstract:
  ATM (asynchronous transfer mode) is the technology chosen for the Broadband
Integrated Services Digital Network (B-ISDN). The ATM ABR (available bit rate)
service can be used to transport ``best-effort'' traffic. In this paper, we
extend our earlier work on the buffer requirements problem for TCP over ABR.
Here, a worst case scenario is generated such that TCP sources send a burst of
data at the time when the sources have large congestion windows and the ACRs
(allowed cell rates) for ABR are high. We find that ABR using the ERICA+ switch
algorithm can control the maximum queue lengths (hence the buffer requirements)
even for the worst case. We present analytical arguments for the expected queue
length and simulation results for different number of sources values and
parameter values.


title:
Performance of TCP over ABR with Long-Range Dependent VBR Background
  Traffic over Terrestrial and Satellite ATM networks

abstract:
  Compressed video is well known to be self-similar in nature. We model VBR
carrying Long-Range Dependent (LRD), multiplexed MPEG-2 video sources. The
actual traffic for the model is generated using fast-fourier transform of
generate the fractional gaussian noise (FGN) sequence. Our model of compressed
video sources bears similarity to an MPEG-2 Transport Stream carrying video,
i.e., it is long-range dependent and generates traffic in a piecewise-CBR
fashion. We study the effect of such VBR traffic on ABR carrying TCP traffic.
The effect of such VBR traffic is that the ABR capacity is highly variant. We
find that a switch algorithm like ERICA+ can tolerate this variance in ABR
capacity while maintaining high throughput and low delay. We present simulation
results for terrestrial and satellite configurations.


title: Fairness for ABR multipoint-to-point connections

abstract:
  In multipoint-to-point connections, the traffic at the root (destination) is
the combination of all traffic originating at the leaves. A crucial concern in
the case of multiple senders is how to define fairness within a multicast group
and among groups and point-to-point connections. Fairness definition can be
complicated since the multipoint connection can have the same identifier
(VPI/VCI) on each link, and senders might not be distinguishable in this case.
Many rate allocation algorithms implicitly assume that there is only one sender
in each VC, which does not hold for multipoint-to-point cases. We give various
possibilities for defining fairness for multipoint connections, and show the
tradeoffs involved. In addition, we show that ATM bandwidth allocation
algorithms need to be adapted to give fair allocations for multipoint-to-point
connections.


title: Modeling Traffic Management in ATM Networks with OPNET

abstract:
  Asynchronous transfer mode (ATM) is the new generation of computer and
communication networks that are being deployed throughout the telecommunication
industry as well as in campus backbones. ATM technology distinguishes itself
from the previous networking protocols in that it has the latest traffic
management technology and thus allows guaranteeing delay, throughput, and other
performance measures. This in turn, allows users to integrate voice, video, and
data on the same network. Available bit rate (ABR) service in ATM has been
designed to fairly distribute all unused capacity to data traffic and is
specified in the ATM Forum's Traffic Management (TM4.0) standard. This paper
will describe the OPNET models that have been developed for ATM and ABR design
and analysis.


title: laboratories for Data Communications and Computer Networks

abstract:
  In this paper we describe a hands-on laboratory oriented instructional
package that we have developed for data communications and networking. The
package consists of a software tool, together with instructional material for a
laboratory based networking curriculum. The software is based on a simulation
environment that enables the student to experiment with various networking
protocols, on an easy to use graphical user interface (GUI). Data message
flows, packet losses, control/routing message flows, virtual circuit setups,
link failures, bit errors etc., are some of the features that can be visualized
in this environment. The student can also modify the networking components
provided, as well as add new components using the C programming language. The
instructional material consists of a set of laboratory exercises for flow and
error control (HDLC), IEEE 802.3 CSMA/CD protocol, the token ring protocol,
interconnecting LANs via bridges, TCP congestion avoidance and control, IP
fragmentation and reassembly, ATM PNNI routing and ATM policing. The laboratory
exercises have facilitated the development of a networking curriculum based on
both the traditional computer networking principles, as well as the new
technologies in telecommunication networking. The laboratory environment has
been used in the networking curriculum at The Ohio State University, and is
being piloted at other universities. The entire package is freely available
over the Internet.


title: Aspects of Evolutionary Design by Computers

abstract:
  This paper examines the four main types of Evolutionary Design by computers:
Evolutionary Design Optimisation, Evolutionary Art, Evolutionary Artificial
Life Forms and Creative Evolutionary Design. Definitions for all four areas are
provided. A review of current work in each of these areas is given, with
examples of the types of applications that have been tackled. The different
properties and requirements of each are examined. Descriptions of typical
representations and evolutionary algorithms are provided and examples of
designs evolved using these techniques are shown. The paper then discusses how
the boundaries of these areas are beginning to merge, resulting in four new
'overlapping' types of Evolutionary Design: Integral Evolutionary Design,
Artificial Life Based Evolutionary Design, Aesthetic Evolutionary AL and
Aesthetic Evolutionary Design. Finally, the last part of the paper discusses
some common problems faced by creators of Evolutionary Design systems,
including: interdependent elements in designs, epistasis, and constraint
handling.


title:
A Freely Available Morphological Analyzer, Disambiguator and Context
  Sensitive Lemmatizer for German

abstract:
  In this paper we present Morphy, an integrated tool for German morphology,
part-of-speech tagging and context-sensitive lemmatization. Its large lexicon
of more than 320,000 word forms plus its ability to process German compound
nouns guarantee a wide morphological coverage. Syntactic ambiguities can be
resolved with a standard statistical part-of-speech tagger. By using the output
of the tagger, the lemmatizer can determine the correct root even for ambiguous
word forms. The complete package is freely available and can be downloaded from
the World Wide Web.


title:
Spoken Language Dialogue Systems and Components: Best practice in
  development and evaluation (DISC 24823) - Periodic Progress Report 1: Basic
  Details of the Action

abstract:
  The DISC project aims to (a) build an in-depth understanding of the
state-of-the-art in spoken language dialogue systems (SLDSs) and components
development and evaluation with the purpose of (b) developing a first best
practice methodology in the field. The methodology will be accompanied by (c) a
series of development and evaluation support tools. To the limited extent
possible within the duration of the project, the draft versions of the
methodology and the tools will be (d) tested by SLDS developers from industry
and research, and will be (e) packaged to best suit their needs. In the first
year of DISC, (a) has been accomplished, and (b) and (c) have started. A
proposal to complete the work proposed above by adding 12 months to the 18
months of the present project, has been submitted to Esprit Long-Term Research
in March 1998.


title:
Analysis and Simulation of Delay and Buffer Requirements of
  satellite-ATM Networks for TCP/IP Traffic

abstract:
  In this paper we present a model to study the end-to-end delay performance of
a satellite-ATM netowrk. We describe a satellite-ATM network architecture. The
architecture presents a trade-off between the on-board switching/processing
features and the complexity of the satellite communication systems. The
end-to-end delay of a connection passing through a satellite constellation
consists of the transmission delay, the uplink and downlink ground
terminal-satellite propagation delay, the inter-satellite link delays, the
on-board switching, processing and buffering delays. In a broadband satellite
network, the propagation and the buffering delays have the most impact on the
overall delay. We present an analysis of the propagation and buffering delay
components for GEO and LEO systems. We model LEO constellations as satellites
evenly spaced in circular orbits around the earth. A simple routing algorithm
for LEO systems calculates locally optimal paths for the end-to-end connection.
This is used to calculate the end-to-end propagation delays for LEO networks.
We present a simulation model to calculate the buffering delay for TCP/IP
traffic over ATM ABR and UBR service categories. We apply this model to
calculate total end-to-end delays for TCP/IP over satellite-ATM networks.


title: Improving the Performance of TCP over the ATM-UBR service

abstract:
  In this paper we study the design issues in improving TCP performance over
the ATM UBR service. ATM-UBR switches respond to congestion by dropping cells
when their buffers become full. TCP connections running over UBR can experience
low throughput and high unfairness. Intelligent switch drop policies and
end-system policies can improve the performance of TCP over UBR with limited
buffers. We describe the various design options available to the network as
well as to the end systems to improve TCP performance over UBR. We study the
effects of Early Packet Discard, and two per-VC accounting based buffer
management policies. We also study the effects of various TCP end system
congestion control policies including slow start and congestion avoidance, fast
retransmit and recovery and selective acknowledgments. We present simulation
results for various small and large latency configurations with varying buffer
sizes and number of sources.


title:
Design Issues for providing Minimum Rate Guarantees to the ATM
  Unspecified Bit Rate Service

abstract:
  Recent enhancements have been proposed to the ATM Unspecified Bit Rate (UBR)
service that guarantee a minimum rate at the frame level to the UBR VCs. These
enhancements have been called Guaranteed Frame Rate (GFR). In this paper, we
discuss the motivation, design and implementation issues for GFR. We present
the design of buffer management and policing mechanisms to implement GFR. We
study the effects of policing, per-VC buffer allocation, and per-VC queuing on
providing GFR to TCP/IP traffic. We conclude that per-VC scheduling is
necessary to provide minimum rate guarantees to TCP traffic. We examine the
role of frame tagging in the presence of scheduling and buffer management for
providing minumum rate guarantees. The use of GFR to support the Internet
Controlled Load Service is also discussed.


title: Providing Rate Guarantees to TCP over the ATM GFR Service

abstract:
  The ATM Guaranteed Frame Rate (GFR) service is intended for best effort
traffic that can benefit from minimum throughput guarantees. Edge devices
connecting LANs to an ATM network can use GFR to transport multiple TCP/IP
connections over a single GFR VC.These devices would typically multiplex VCs
into a single FIFO queue. It has been shown that in general, FIFO queuing is
not sufficient to provide rate guarantees, and per-VC queuing with scheduling
is needed. We show that under conditions of low buffer allocation, it is
possible to control TCP rates with FIFO queuing and buffer management. We
present analysis and simulation results on controlling TCP rates by buffer
management. We present a buffer management policy that provides loose rate
guarantees to SACK TCP sources when the total buffer allocation is low. We
study the performance of this buffer management scheme by simulation.


title: Analysis and Modeling of Traffic in Modern Data Communication Networks

abstract:
  In performance analysis and design of communication netword modeling data
traffic is important. With introduction of new applications, the
characteristics of the data traffic changes. We present a brief review the
different models of data traffic and how they have evolved. We present results
of data traffic analysis and simulated traffic, which demonstrates that the
packet train model fits the traffic at source destination level and long-memory
(self-similar) model fits the traffic at the aggregate level.


title:
On Determining the Fair Bandwidth Share for ABR Connections in ATM
  Networks

abstract:
  The ABR service is designed to fairly allocate the bandwidth unused by higher
priority services. The network indicates to the ABR sources the rates at which
they should transmit to minimize their cell loss. Switches must constantly
measure the demand and available capacity, and divide the capacity fairly among
the contending connections. In order to compute the fair and efficient
allocation for each connection, a switch needs to determine the effective
number of active connections. In this paper, we propose a method for
determining the number of active connections and the fair bandwidth share for
each. We prove the efficiency and fairness of the proposed method analytically,
and simulate it by incorporating it into the ERICA switch algorithm.


title:
The OSU Scheme for Congestion Avoidance in ATM Networks: Lessons Learnt
  and Extensions

abstract:
  The OSU scheme is a rate-based congestion avoidance scheme for ATM networks
using explicit rate indication. This work was one of the first attempts to
define explicit rate switch mechanisms and the Resource Management (RM) cell
format in Asynchronous Transfer Mode (ATM) networks. The key features of the
scheme include explicit rate feedback, congestion avoidance, fair operation
while maintaining high utilization, use of input rate as a congestion metric,
O(1) complexity. This paper presents an overview of the scheme, presents those
features of the scheme that have now become common features of other switch
algorithms and discusses three extensions of the scheme.


title: The ERICA Switch Algorithm for ABR Traffic Management in ATM Networks

abstract:
  We propose an explicit rate indication scheme for congestion avoidance in ATM
networks. In this scheme, the network switches monitor their load on each link,
determining a load factor, the available capacity, and the number of currently
active virtual channels. This information is used to advise the sources about
the rates at which they should transmit. The algorithm is designed to achieve
efficiency, fairness, controlled queueing delays, and fast transient response.
The algorithm is also robust to measurement errors caused due to variation in
ABR demand and capacity. We present performance analysis of the scheme using
both analytical arguments and simulation results. The scheme is being
implemented by several ATM switch manufacturers.


title: New Applications of the Incompressibility Method: Part II

abstract:
  The incompressibility method is an elementary yet powerful proof technique.
It has been used successfully in many areas. To further demonstrate its power
and elegance we exhibit new simple proofs using the incompressibility method.


title: New Applications of the Incompressibility Method: Part I


title:
Satellite ATM Network Architectural Considerations and TCP/IP
  Performance

abstract:
  In this paper, we have provided a summary of the design options in
Satellite-ATM technology. A satellite ATM network consists of a space segment
of satellites connected by inter-satellite crosslinks, and a ground segment of
the various ATM networks. A satellite-ATM interface module connects the
satellite network to the ATM networks and performs various call and control
functions. A network control center performs various network management and
resource allocation functions. Several issues such as the ATM service model,
media access protocols, and traffic management issues must be considered when
designing a satellite ATM network to effectively transport Internet traffic. We
have presented the buffer requirements for TCP/IP traffic over ATM-UBR for
satellite latencies. Our results are based on TCP with selective
acknowledgments and a per-VC buffer management policy at the switches. A buffer
size of about 0.5 * RTT to 1 * RTT is sufficient to provide over 98% throughput
to infinite TCP traffic for long latency networks and a large number of
sources. This buffer requirement is independent of the number of sources. The
fairness is high for a large numbers of sources because of the per-VC buffer
management performed at the switches and the nature of TCP traffic.


title: Performance of Bursty World Wide Web (WWW) Sources over ABR

abstract:
  We model World Wide Web (WWW) servers and clients running over an ATM network
using the ABR (available bit rate) service. The WWW servers are modeled using a
variant of the SPECweb96 benchmark, while the WWW clients are based on a model
by Mah. The traffic generated by this application is typically bursty, i.e., it
has active and idle periods in transmission. A timeout occurs after given
amount of idle period. During idle period the underlying TCP congestion windows
remain open until a timeout expires. These open windows may be used to send
data in a burst when the application becomes active again. This raises the
possibility of large switch queues if the source rates are not controlled by
ABR. We study this problem and show that ABR scales well with a large number of
bursty TCP sources in the system.


title:
Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically
  Specified Problems

abstract:
  We study the efficient approximability of basic graph and logic problems in
the literature when instances are specified hierarchically as in \cite{Le89} or
are specified by 1-dimensional finite narrow periodic specifications as in
\cite{Wa93}. We show that, for most of the problems $\Pi$ considered when
specified using {\bf k-level-restricted} hierarchical specifications or
$k$-narrow periodic specifications the following holds:
  \item Let $\rho$ be any performance guarantee of a polynomial time
approximation algorithm for $\Pi$, when instances are specified using standard
specifications. Then $\forall \epsilon > 0$, $ \Pi$ has a polynomial time
approximation algorithm with performance guarantee $(1 + \epsilon) \rho$. \item
$\Pi$ has a polynomial time approximation scheme when restricted to planar
instances. \end{romannum}
  These are the first polynomial time approximation schemes for PSPACE-hard
hierarchically or periodically specified problems. Since several of the
problems considered are PSPACE-hard, our results provide the first examples of
natural PSPACE-hard optimization problems that have polynomial time
approximation schemes. This answers an open question in Condon et. al.
\cite{CF+93}.


title:
Feedback Consolidation Algorithms for ABR Point-to-Multipoint
  Connections in ATM Networks

abstract:
  ABR traffic management for point-to-multipoint connections controls the
source rate to the minimum rate supported by all the branches of the multicast
tree. A number of algorithms have been developed for extending ABR congestion
avoidance algorithms to perform feedback consolidation at the branch points.
This paper discusses various design options and implementation alternatives for
the consolidation algorithms, and proposes a number of new algorithms. The
performance of the proposed algorithms and the previous algorithms is compared
under a variety of conditions. Results indicate that the algorithms we propose
eliminate the consolidation noise (caused if the feedback is returned before
all branches respond), while exhibiting a fast transient response.


title:
TCP Selective Acknowledgments and UBR Drop Policies to Improve ATM-UBR
  Performance over Terrestrial and Satellite Networks

abstract:
  We study the performance of Selective Acknowledgments with TCP over the
ATM-UBR service category. We examine various UBR drop policies, TCP mechanisms
and network configurations to recommend optimal parameters for TCP over UBR. We
discuss various TCP congestion control mechanisms compare their performance for
LAN and WAN networks. We describe the effect of satellite delays on TCP
performance over UBR and present simulation results for LAN, WAN and satellite
networks. SACK TCP improves the performance of TCP over UBR, especially for
large delay networks. Intelligent drop policies at the switches are an
important factor for good performance in local area networks.


title: A Survey of Protocols and Open Issues in ATM Multipoint Communication

abstract:
  Asynchronous transfer mode (ATM) networks must define multicast capabilities
in order to efficiently support numerous applications, such as video
conferencing and distributed applications, in addition to LAN emulation (LANE)
and Internet protocol (IP) multicasting. Several problems and issues arise in
ATM multicasting, such as signaling, routing, connection admission control, and
traffic management problems. IP integrated services over ATM poses further
challenges to ATM multicasting. Scalability and simplicity are the two main
concerns for ATM multicasting. This paper provides a survey of the current work
on multicasting problems in general, and ATM multicasting in particular. A
number of proposed schemes is examined, such as the schemes MARS, MCS, SEAM,
SMART, RSVP, and various multipoint traffic management and transport-layer
schemes. The paper also indicates a number of key open issues that remain
unresolved.


title: Performance Testing Effort at the ATM Forum: An Overview

abstract:
  The testing group at ATM Forum is working on developing a specification for
performance testing of ATM switches and networks. The emphasis is on the user
perceived frame-level performance. This paper explains what is different about
this new effort and gives its status.


title:
Design Considerations for the Virtual Source/Virtual Destination (VS/VD)
  Feature in the ABR Service of ATM Networks

abstract:
  The Available Bit Rate (ABR) service in ATM networks has been specified to
allow fair and efficient support of data applications over ATM utilizing
capacity left over after servicing higher priority classes. One of the
architectural features in the ABR specification [tm4] is the Virtual
Source/Virtual Destination (VS/VD) option. This option allows a switch to
divide an end-to-end ABR connection into separately controlled ABR segments by
acting like a destination on one segment, and like a source on the other. The
coupling in the VS/VD switch between the two ABR control segments is
implementation specific. In this paper, we model a VS/VD ATM switch and study
the issues in designing coupling between ABR segments. We identify a number of
implementation options for the coupling. A good choice significantly improves
the stability and transient performance of the system and reduces the buffer
requirements at the switches.


title:
Use-it or Lose-it Policies for the Available Bit Rate (ABR) Service in
  ATM Networks

abstract:
  The Available Bit Rate (ABR) service has been developed to support 21st
century data applications over Asynchronous Transfer Mode (ATM). The ABR
service uses a closed-loop rate-based traffic management framework where the
network divides left-over bandwidth among contending sources. The ATM Forum
traffic management group also incorporated open-loop control capabilities to
make the ABR service robust to temporary network failures and source
inactivity. An important problem addressed was whether rate allocations of
sources should be taken away if sources do not use them. The proposed
solutions, popularly known as the Use-It-or-Lose-It (UILI) policies, have had
significant impact on the ABR service capabilities. In this paper we discuss
the design, development, and the final shape of these policies and their impact
on the ABR service. We compare the various alternatives through a performance
evaluation.


title: UBR+: Improving Performance of TCP over ATM-UBR service

abstract:
  ATM-UBR switches respond to congestion by dropping cells when their buffers
become full. TCP connections running over UBR experience low throughput and
high unfairness. For 100% TCP throughput each switch needs buffers equal to the
sum of the window sizes of all the TCP connections. Intelligent drop policies
can improve the performance of TCP over UBR with limited buffers. The UBR+
service proposes enhancements to UBR for intelligent drop. Early Packet Discard
improves throughput but does not attempt to improve fairness. Selective packet
drop based on per-connection buffer occupancy improves fairness. The Fair
Buffer Allocation scheme further improves both throughput and fairness.


title:
Performance of TCP over ABR on ATM backbone and with various VBR traffic
  patterns

abstract:
  We extend our earlier studies of buffer requirements of TCP over ABR in two
directions. First, we study the performance of TCP over ABR in an ATM backbone.
On the backbone, the TCP queues are at the edge router and not inside the ATM
network. The router requires buffer equal to the sum of the receiver window
sizes of the participating TCP connections. Second, we introduce various
patterns of VBR background traffic. The VBR background introduces variance in
the ABR capacity and the TCP traffic introduces variance in the ABR demand.
Some simple switch schemes are unable to keep up with the combined effect of
highly varying demands and highly varying ABR capacity. We present our
experiences with refining the ERICA+ switch scheme to handle these conditions.


title:
Performance and Buffering Requirements of Internet Protocols over ATM
  ABR and UBR Services

abstract:
  The Asynchronous Transfer Mode (ATM) networks are quickly being adopted as
backbones over various parts of the Internet. This paper analyzes the
performance of TCP/IP protocols over ATM network's Available Bit Rate (ABR) and
Unspecified Bit Rate (UBR) services. It is shown that ABR pushes congestion to
the edges of the ATM network while UBR leaves it inside the ATM portion.


title:
Performance of TCP/IP Using ATM ABR and UBR Services over Satellite
  Networks

abstract:
  We study the buffering requirements for zero cell loss for TCP/IP over
satellite links using the available bit rate (ABR) and unspecified bit rate
(UBR) services of asynchronous transfer mode (ATM) networks. For the ABR
service, we explore the effect of feedback delay (a factor which depends upon
the position of the bottleneck), the switch scheme used, and background
variable bit rate (VBR) traffic. It is shown that the buffer requirement for
TCP over ABR is independent of the number of TCP sources, but depends on the
aforementioned factors. For the UBR service, we show that the buffer
requirement is the sum of the TCP receiver window sizes. We substantiate our
arguments with simulation results.


title: On Source Rules for ABR Service on ATM Networks with Satellite Links

abstract:
  During the design of ABR traffic management at the ATM Forum, we performed
several analyses to ensure that the ABR service will operate efficiently over
satellite links. In the cases where the performance was unacceptable, we
suggested modifications to the traffic management specifications. This paper
describes one such issue related to the count of missing resource management
cells (Crm) parameter of the ABR source behavior. The analysis presented here
led to the changes which are now part of the ATM traffic management (TM 4.0)
specification. In particular, the size of the transient buffer exposure (TBE)
parameter was set to 24 bits, and no size was enforced for the Crm parameter.
This simple change improved the throughput over OC-3 satellite links from 45
Mbps to 140 Mbps.


title:
A Survey of Congestion Control Techniques and Data Link Protocols in
  Satellite Networks

abstract:
  Satellite communication systems are the means of realizing a global broadband
integrated services digital network. Due to the statistical nature of the
integrated services traffic, the resulting rate fluctuations and burstiness
render congestion control a complicated, yet indispensable function. The long
propagation delay of the earth-satellite link further imposes severe demands
and constraints on the congestion control schemes, as well as the media access
control techniques and retransmission protocols that can be employed in a
satellite network. The problems in designing satellite network protocols, as
well as some of the solutions proposed to tackle these problems, will be the
primary focus of this survey.


title: Source Behavior for ATM ABR Traffic Management: An Explanation

abstract:
  The Available Bit Rate (ABR) service has been developed to support data
applications over Asynchronous Transfer Mode (ATM) networks. The network
continuously monitors its traffic and provides feedback to the source end
systems. This paper explains the rules that the sources have to follow to
achieve a fair and efficient allocation of network resources.


title: Buffer Requirements For TCP/IP Over ABR

abstract:
  We study the buffering requirements for zero cell loss for TCP over ABR. We
show that the maximum buffers required at the switch is proportional to the
maximum round trip time (RTT) of all VCs through the link. The number of
round-trips depends upon the the switch algorithm used. With our ERICA
[erica-final] switch algorithm, we find that the buffering required is
independent of the number of TCP sources. We substantiate our arguments with
simulation results.


title: Potential Networking Applications of Global Positioning Systems (GPS)

abstract:
  The main goal of this study was to survey current applications of GPS to
distributed systems and networks. Detailed lists of GPS products, current
applications, addresses of manufacturers, and sources for further information
are included in this report.


title:
The OSU Scheme for Congestion Avoidance in ATM networks Using Explicit
  Rate Indication

abstract:
  An explicit rate indication scheme for congestion avoidance in computer and
telecommunication networks is proposed. The sources monitor their load and
provide the information periodically to the switches. The switches, in turn,
compute the load level and ask the sources to adjust their rates up or down.
The scheme achieves high link utilization, fair allocation of rates among
contending sources and provides quick convergence. A backward congestion
notification option is also provided. The conditions under which this option is
useful are indicated.


title: Optimal Point Placement for Mesh Smoothing

abstract:
  We study the problem of moving a vertex in an unstructured mesh of
triangular, quadrilateral, or tetrahedral elements to optimize the shapes of
adjacent elements. We show that many such problems can be solved in linear time
using generalized linear programming. We also give efficient algorithms for
some mesh smoothing problems that do not fit into the generalized linear
programming paradigm.


title: Congestion Control with Explicit Rate Indication

abstract:
  As the speed and the dynamic range of computer networks evolve, the issue of
efficient traffic management becomes increasingly important. This work
describes an approach to traffic management using explicit rate information
provided to the source by the network. We present an asynchronous distributed
algorithm for optimal rate calculation across the network, where optimality is
understood in the maxmin sense. The algorithm quickly converges to the optimal
rates and is shown to be well-behaved in transience.


title:
A Brief Overview of ATM: Protocol Layers, LAN Emulation, and Traffic
  Management

abstract:
  Asynchronous Transfer Mode (ATM) has emerged as the most promising technology
in supporting future broadband multimedia communication services. To accelerate
the deployment of ATM technology, the ATM Forum, which is a consortium of
service providers and equipment vendors in the communication industries has
been created to develop implementation and specification agreements. In this
article, we present a brief overview on ATM protocol layers and current
progress on LAN Emulation and Traffic Management in the ATM Forum.


title: ATM Networks: Issues and Challenges Ahead

abstract:
  The paper begins with a discussion of current trends in networking and a
historical reviews of past networking technologies some of which failed. This
leads us to the discussion about what it takes for a new technology to succeed
and what challenges we face in making the current dream of a seamless
world-wide high-speed ATM network a reality.
  Issues in using ATM cells for very high speed applications are presented.
Ensuring that the users benefit from ATM networks involves several other
related disciplines. These are reviewed.


title:
Congestion Control and Traffic Management in ATM Networks: Recent
  Advances and A Survey

abstract:
  Congestion control mechanisms for ATM networks as selected by the ATM Forum
traffic management group are described. Reasons behind these selections are
explained. In particular, selection criteria for selection between rate-based
and credit-based approach and the key points of the debate between the two
approaches are presented. The approach that was finally selected and several
other schemes that were considered are described.


title: FDDI: Current Issues and Future Trends

abstract:
  Key issues in upcoming FDDI standards including low-cost fiber, twisted-pair,
SONET mapping, and FDDI follow-on LAN are discussed after a brief introduction
to FDDI and FDDI-II


title: A Comparison of Hashing Schemes for Address Lookup in Computer Networks

abstract:
  Using a trace of address references, we compared the efficiency of several
different hashing functions, such as cyclic redundancy checking (CRC)
polynomials, Fletcher checksum, folding of address octets using the
exclusive-or operation and bit extraction from the address. Guidelines are
provided for determining the size of the hashmark required to achieve a
specified level of performance.


title: Myths about Congestion Management in High Speed Networks

abstract:
  Weaknesses in several recently proposed ideas about congestion control and
avoidance in high-speed netwroks are identified. Both sides of the debate
concerning prior reservation of resources versus walk-in service, open-loop
control versus feedback control, rate control versus window control, and
router-based control versus source-based control are presented. The
circumstances under which backpressure is useful or not are discussed, and it
is argued that a single congestion scheme is not sufficient, but that a
combination of several schemes is required for complete congestion management
in a network.


title:
Performance Analysis of FDDI Token Ring Networks: Effect of Parameters
  and Guidelines for Setting TTRT

abstract:
  The performance of Fiber-Distributed Data Interface (FDDI) depends upon
several workload parameters; for example; the arrival pattern, frame size, and
configuration parameters, such as the number of stations on the ring, extent of
the ring, and number of stations that are waiting to transmit. In addition, the
performance is affected by a parameter called the Target Token Rotation Time
(TTRT), which can be controlled by the network manager. We considered the
effect of TTRT on various performance metrics for different ring configurations
and concluded that a TTRT value of 8 ms provides a good performance over a wide
range of configurations and workloads.


title: Error Characteristics of Fiber Distributed Data Interface (FDDI)

abstract:
  Fiber Distributed Data Interface (FDDI) is a 100 megabits per second fiber
optic local area network (LAN) standard being developed by the American
National Standard Institute (ANSI).
  We analyze the impact of various design decisions on the error detection
capability of the protocol. In particular, we quantify frame error rate, token
loss rate, and undetected error rate. Several characteristics of the 32-bit
frame check sequence (FCS) polynomial, which is also used in IEEE 802 LAN
protocols, are discussed.


title: Congestion Control in Computer Networks: Trends and Issues

abstract:
  Popular myths that cheaper memory, high-speed links and high-speed processors
will solve the problem of congestion in computer networks are shown to be
false. A simple definition for congestion based on supply and demand of
resources is proposed and is then used to classify various congestion schemes.
The issues that make the congestion problem a difficult one are discussed, and
then the architectural decisions that affect the design of a congestion scheme
are presented. It is argued that long-, medium- and short-term congestion
problems require different solutions. Some of the recent schemes are brifly
surveyed, and areas for further research are discussed.


title:
Characteristics of Destination Address Locality in Computer Networks: A
  Comparison of Caching Schemes

abstract:
  The size of computer networks, along with their bandwidths, is growing
exponentially. To support these large, high-speed networks, it is neccessary to
be able to forward packets in a few microseconds. One part of the forwarding
operation consists of searching through a large address databse. This problem
is encountered in the design of bridges, routers, gateways and name servers.
  Caching can reduce the lookup time if there is a locality in the address
reference pattern. Using a destination reference trace measured on an extended
local are a network, we attempt to see if the destination refernces do have a
significant locality.
  We compared the performance of MIN, LRU, FIFO, and random cache replacement
algorithms. We found that the interactive (terminal) traffic in our sample had
quite different locality behavior than that of the noninteractive traffic. The
interactive traffic did not follow the LRU stack model while the
noninteractivetraffic did. Examples are shown of the environments in which
caching can help as well as those in which caching can hurt, unless the cache
size is large.


title:
A Delay Based Approach for Congestion Avoidance in Interconnected
  Heterogeneous Computer Networks

abstract:
  In heterogeneous networks, achieving congestion avoidance is difficult
because the congestion feedback from one subnetwork may have no meaning to
source on other other subnetworks. We propose using changes in round-trip delay
as an implicit feedback. Using a black-box model of the network, we derive an
expression for the optimal window as a function of the gradient of the
delay-window curve.
  The problems of selfish optimum and social optimum are also addressed. It is
shown that without a careful design, it is possible to get into a race
condition during heavy congestion, where each user wants more resources than
others, thereby leading to a diverging congestion
  It is shown that congestion avoidance using round trip delay is a promising
approach. The aproach has the advantage that there is absolutely no overhead
for the network itself. It is exemplified by a simple scheme. The performance
of the scheme is analyzed using a simulation model. The scheme is shown to be
efficient, fair, convergent and adaptive to changes in network configuration.
  The scheme as described works only for networks that can ne modelled with
queueing servers with constant service times. Further research is required to
extend it for implementation in practical networks. Several directions for
future research have beensuggested.


title:
Congestion Avoidance in Computer Networks with a Connectionless Network
  Layer

abstract:
  Widespread use of computer networks and the use of varied technology for the
interconnection of computers has made congestion a significant problem.
  In this report, we summarize our research on congestion avoidance. We compare
the concept of congestion avoidance with that of congestion control.
  Briefly, congestion control is a recovery mechanism, while congestion
avoidance is a prevention mechanism. A congestion control scheme helps the
network to recover from the congestion state while a congestion avoidance
scheme allows a network to operate in the region of low delay and high
throughput with minimal queuing, thereby preventing it from entering the
congested state in which packets are lost due to buffer shortage.
  A number of possible alternatives for congestion avoidance were identified.
  From these alternatives we selected one called the binary feedback scheme in
which the network uses a single bit in the network layer header to feed back
the congestion information to its users, which then increase or decrease their
load to make optimal use of the resources. The concept of global optimality in
a distributed system is defined in terms of efficiency and fairness such that
they can be independently quantified and apply to any number of resources and
users.
  The proposed scheme has been simulated and shown to be globally efficient,
fair, responsive, convergent, robust, distributed, and
configuration-independent.


title:
Congestion Avoidance in Computer Networks with a Connectionless Network
  Layer, Part I: Concepts, Goals and Methodology

abstract:
  Congestion is said to occur in the network when the resource demands exceed
the capacity and packets are lost due to too much queuing in the network.
During congestion, the network throughput may drop to zero and the path delay
may become very high. A congestion control scheme helps the network to recover
from the congestion state. A congestion avoidance scheme allows a network to
operate in the region of low delay and high throughput. Such schemes prevent a
network from entering the congested state. Congestion avoidance is a prevention
mechanism while congestion control is a recovery mechanism. We compare the
concept of congestion avoidance with that of flow control and congestion
control. A number of possible alternative for congestion avoidance have been
identified. From these a few were selected for study. The criteria for
selection and goals for these schemes have been described. In particular, we
wanted the scheme to be globally efficient, fair, dynamic, convergent, robust,
distributed, configuration independent, etc. These goals and the test cases
used to verify whether a particular scheme has met the goals have been
described. We model the network and the user policies for congestion avoidance
as a feedback control system. The key components of a generic congestion
avoidance scheme are: congestion detection, congestion feedback, feedback
selector, signal filter, decision function, and increase/decrease algorithms.
These components have been explained.


title:
A Timeout Based Congestion Control Scheme for Window Flow- Controlled
  Networks

abstract:
  During overload, most networks drop packets due to buffer unavailability. The
resulting timeouts at the source provide an implicit mechanism to convey
congestion signals from the network to the source. On a timeout, a source
should not only retransmit the lost packet, but it should also reduce its load
on the network. Based on this realization, we have developed a simple
congestion control scheme using the acknowledgment timeouts as indications of
packet loss and congestion. This scheme does not require any new message
formats, therefore, it can be used in any network with window flow control,
e.g., ARPAnet or ISO.


title: Divergence of Timeout Algorithms for Packet Retransmissions

abstract:
  The problem of adaptively setting the timeout interval for retransmitting a
packet has been discussed. A layered view of the algorithms has been presented.
It is shown that a timeout algorithm consists of essentially five layers or
procedures which can be independently chosen and modified. A number of timeout
algorithms proposed in the literature have been decomposed into these five
layers.
  One of the key layers not discussed in the literature is that of determining
the sample round trip delay for packets that have been transmitted more than
once. It is shown that this layer has a significant impact on the network
performance.
  Under repeated packet loss, most timeout algorithms either diverge or
converge to a wrong value. A number of alternative schemes have been presented.
It is argued that divergence is preferable to false convergence. It is a
feature that is helpful in reducing network traffic congestion.


title: On Caching out-of-order packets in window flow controlled networks

abstract:
  In window flow controlled networks, if a packet is lost the destination has
to decide whether to save (cache) subsequent out-of-order packets. Also, the
source has to decide whether to send just one packet or to send all packets
following it. This leads to four different types of caching schemes.
Simulations show, against our immediate intuition, that regardless of whether
the destination is caching or not, the source should retransmit only one
packet. This paper describes the alternatives to, and provides justification
for, schemes used in Digital Network Architecture and ARPAnet TCP.


title:
A Quantitative Measure Of Fairness And Discrimination For Resource
  Allocation In Shared Computer Systems

abstract:
  Fairness is an important performance criterion in all resource allocation
schemes, including those in distributed computer systems. However, it is often
specified only qualitatively. The quantitative measures proposed in the
literature are either too specific to a particular application, or suffer from
some undesirable characteristics. In this paper, we have introduced a
quantitative measure called Indiex of FRairness. The index is applicable to any
resource sharing or allocation problem. It is independent of the amount of the
resource. The fairness index always lies between 0 and 1. This boundedness aids
intuitive understanding of the fairness index. For example, a distribution
algorithm with a fairness of 0.10 means that it is unfair to 90% of the users.
Also, the discrimination index can be defined as 1 - fairness index.


title: Data Flies Standby with ABR Service

abstract: Explanation of ABR service in plain language.