OpenRaiser/Intern-Atlas huggingface dataset:
Fast, Approximate Synthesis of Fractional Gaussian Noise for Generating Self-Similar Network Traffic
Venue: arXiv cs.NI 1998
Year: 1998

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.
Semantics and Conversations for an Agent Communication Language
Venue: arXiv cs.MA 1998
Year: 1998

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.
Providing Rate Guarantees to TCP over the ATM GFR Service
Venue: arXiv cs.NI 1998
Year: 1998

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.
The ERICA Switch Algorithm for ABR Traffic Management in ATM Networks
Venue: arXiv cs.NI 1998
Year: 1998

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.
Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
Venue: arXiv cs.CC 1998
Year: 1998

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 $Π$ considered when specified using {\bf k-level-restricted} hierarchical specifications or $k$-narrow periodic specifications the following holds: \item Let $ρ$ be any performance guarantee of a polynomial time approximation algorithm for $Π$, when instances are specified using standard specifications. Then $\forall ε> 0$, $ Π$ has a polynomial time approximation algorithm with performance guarantee $(1 + ε) ρ$. \item $Π$ 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}.
A Survey of Congestion Control Techniques and Data Link Protocols in Satellite Networks
Venue: arXiv cs.NI 1998
Year: 1998

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.
Buffer Requirements For TCP/IP Over ABR
Venue: arXiv cs.NI 1998
Year: 1998

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.
A Brief Overview of ATM: Protocol Layers, LAN Emulation, and Traffic Management
Venue: arXiv cs.NI 1998
Year: 1998

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.
Error Characteristics of Fiber Distributed Data Interface (FDDI)
Venue: arXiv cs.NI 1998
Year: 1998

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.
Congestion Avoidance in Computer Networks with a Connectionless Network Layer
Venue: arXiv cs.NI 1998
Year: 1998

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.
Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part I: Concepts, Goals and Methodology
Venue: arXiv cs.NI 1998
Year: 1998

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.
A Timeout Based Congestion Control Scheme for Window Flow- Controlled Networks
Venue: arXiv cs.NI 1998
Year: 1998

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.
Flood Routing Technique for Data Networks
Venue: arXiv cs.NI 1998
Year: 1998

In this paper, a new routing algorithm based on a flooding method is introduced. Flooding techniques have been used previously, e.g. for broadcasting the routing table in the ARPAnet [1] and other special purpose networks [3][4][5]. However, sending data using flooding can often saturate the network [2] and it is usually regarded as an inefficient broadcast mechanism. Our approach is to flood a very short packet to explore an optimal route without relying on a pre-established routing table, and an efficient flood control algorithm to reduce the signalling traffic overhead. This is an inherently robust mechanism in the face of a network configuration change, achieves automatic load sharing across alternative routes and has potential to solve many contemporary routing problems. An earlier version of this mechanism was originally developed for virtual circuit establishment in the experimental Caroline ATM LAN [6][7] at Monash University.
A Generalized Quantifier Concept in Computational Complexity Theory
Venue: arXiv cs.CC 1998
Year: 1998

A notion of generalized quantifier in computational complexity theory is explored and used to give a unified treatment of leaf language definability, oracle separations, type 2 operators, and circuits with monoidal gates. Relations to Lindstroem quantifiers are pointed out.
The Boolean Hierarchy over Level 1/2 of the Straubing-Therien Hierarchy
Venue: arXiv cs.CC 1998
Year: 1998

For some fixed alphabet A, a language L of A* is in the class L(1/2) of the Straubing-Therien hierarchy if and only if it can be expressed as a finite union of languages A*aA*bA*...A*cA*, where a,b,...,c are letters. The class L(1) is defined as the boolean closure of L(1/2). It is known that the classes L(1/2) and L(1) are decidable. We give a membership criterion for the single classes of the boolean hierarchy over L(1/2). From this criterion we can conclude that this boolean hierarchy is proper and that its classes are decidable.In finite model theory the latter implies the decidability of the classes of the boolean hierarchy over the class Sigma(1) of the FO(<)-logic. Moreover we prove a ``forbidden-pattern'' characterization of L(1) of the type: L is in L(1) if and only if a certain pattern does not appear in the transition graph of a deterministic finite automaton accepting L. We discuss complexity theoretical consequences of our results.
Practical algorithms for on-line sampling
Venue: arXiv cs.LG 1998
Year: 1998

One of the core applications of machine learning to knowledge discovery consists on building a function (a hypothesis) from a given amount of data (for instance a decision tree or a neural network) such that we can use it afterwards to predict new instances of the data. In this paper, we focus on a particular situation where we assume that the hypothesis we want to use for prediction is very simple, and thus, the hypotheses class is of feasible size. We study the problem of how to determine which of the hypotheses in the class is almost the best one. We present two on-line sampling algorithms for selecting hypotheses, give theoretical bounds on the number of necessary examples, and analize them exprimentally. We compare them with the simple batch sampling approach commonly used and show that in most of the situations our algorithms use much fewer number of examples.
On Dart-Zobel Algorithm for Testing Regular Type Inclusion
Venue: arXiv cs.LO 1998
Year: 1998

This paper answers open questions about the correctness and the completeness of Dart-Zobel algorithm for testing the inclusion relation between two regular types. We show that the algorithm is incorrect for regular types. We also prove that the algorithm is complete for regular types as well as correct for tuple distributive regular types. Also presented is a simplified version of Dart-Zobel algorithm for tuple distributive regular types.
Axiomatizing Flat Iteration
Venue: arXiv cs.LO 1998
Year: 1998

Flat iteration is a variation on the original binary version of the Kleene star operation P*Q, obtained by restricting the first argument to be a sum of atomic actions. It generalizes prefix iteration, in which the first argument is a single action. Complete finite equational axiomatizations are given for five notions of bisimulation congruence over basic CCS with flat iteration, viz. strong congruence, branching congruence, eta-congruence, delay congruence and weak congruence. Such axiomatizations were already known for prefix iteration and are known not to exist for general iteration. The use of flat iteration has two main advantages over prefix iteration: 1.The current axiomatizations generalize to full CCS, whereas the prefix iteration approach does not allow an elimination theorem for an asynchronous parallel composition operator. 2.The greater expressiveness of flat iteration allows for much shorter completeness proofs. In the setting of prefix iteration, the most convenient way to obtain the completeness theorems for eta-, delay, and weak congruence was by reduction to the completeness theorem for branching congruence. In the case of weak congruence this turned out to be much simpler than the only direct proof found. In the setting of flat iteration on the other hand, the completeness theorems for delay and weak (but not eta-) congruence can equally well be obtained by reduction to the one for strong congruence, without using branching congruence as an intermediate step. Moreover, the completeness results for prefix iteration can be retrieved from those for flat iteration, thus obtaining a second indirect approach for proving completeness for delay and weak congruence in the setting of prefix iteration.
Early Experience with ASDL in lcc
Venue: arXiv cs.PL 1998
Year: 1998

The Abstract Syntax Description Language (ASDL) is a language for specifying the tree data structures often found in compiler intermediate representations. The ASDL generator reads an ASDL specification and generates code to construct, read, and write instances of the trees specified. Using ASDL permits a compiler to be decomposed into semi-independent components that communicate by reading and writing trees. Each component can be written in a different language, because the ASDL generator can emit code in several languages, and the files written by ASDL-generated code are machine- and language-independent. ASDL is part of the National Compiler Infrastructure project, which seeks to reduce dramatically the overhead of computer systems research by making it much easier to build high-quality compilers. This paper describes dividing lcc, a widely used retargetable C compiler, into two components that communicate via trees defined in ASDL. As the first use of ASDL in a `real' compiler, this experience reveals much about the effort required to retrofit an existing compiler to use ASDL, the overheads involved, and the strengths and weaknesses of ASDL itself and, secondarily, of lcc.
Gryphon: An Information Flow Based Approach to Message Brokering
Venue: arXiv cs.DC 1998
Year: 1998

Gryphon is a distributed computing paradigm for message brokering, which is the transferring of information in the form of streams of events from information providers to information consumers. This extended abstract outlines the major problems in message brokering and Gryphon's approach to solving them.
A Polymorphic Groundness Analysis of Logic Programs
Venue: arXiv cs.PL 1998
Year: 1998

A polymorphic analysis is an analysis whose input and output contain parameters which serve as placeholders for information that is unknown before analysis but provided after analysis. In this paper, we present a polymorphic groundness analysis that infers parameterised groundness descriptions of the variables of interest at a program point. The polymorphic groundness analysis is designed by replacing two primitive operators used in a monomorphic groundness analysis and is shown to be as precise as the monomorphic groundness analysis for any possible values for mode parameters. Experimental results of a prototype implementation of the polymorphic groundness analysis are given.
Case Study in Survivable Network System Analysis
Venue: arXiv cs.SE 1998
Year: 1998

This paper presents a method for analyzing the survivability of distributed network systems and an example of its application.
Deriving Abstract Semantics for Forward Analysis of Normal Logic Programs
Venue: arXiv cs.PL 1998
Year: 1998

The problem of forward abstract interpretation of {\em normal} logic programs has not been formally addressed in the literature although negation as failure is dealt with through the built-in predicate ! in the way it is implemented in Prolog. This paper proposes a solution to this problem by deriving two generic fixed-point abstract semantics $F^b and $F^\diamond for forward abstract interpretation of {\em normal} logic programs. $F^b$ is intended for inferring data descriptions for edges in the program graph where an edge denotes the possibility that the control of execution transfers from its source program point to its destination program point. $F^\diamond$ is derived from $F^b$ and is intended for inferring data descriptions for textual program points.
Locked and Unlocked Polygonal Chains in 3D
Venue: arXiv cs.CG 1998
Year: 1998

In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement. The analogous concept for closed chains is convexification: reconfiguration to a planar convex polygon. Chains that cannot be straightened or convexified are called locked. While there are open chains in 3D that are locked, we show that if an open chain has a simple orthogonal projection onto some plane, it can be straightened. For closed chains, we show that there are unknotted but locked closed chains, and we provide an algorithm for convexifying a planar simple polygon in 3D with a polynomial number of moves.
The Essence of Constraint Propagation
Venue: arXiv cs.AI 1998
Year: 1998

We show that several constraint propagation algorithms (also called (local) consistency, consistency enforcing, Waltz, filtering or narrowing algorithms) are instances of algorithms that deal with chaotic iteration. To this end we propose a simple abstract framework that allows us to classify and compare these algorithms and to establish in a uniform way their basic properties.
Training Reinforcement Neurocontrollers Using the Polytope Algorithm
Venue: arXiv cs.NE 1998
Year: 1998

A new training algorithm is presented for delayed reinforcement learning problems that does not assume the existence of a critic model and employs the polytope optimization algorithm to adjust the weights of the action network so that a simple direct measure of the training performance is maximized. Experimental results from the application of the method to the pole balancing problem indicate improved training performance compared with critic-based and genetic reinforcement approaches.
Fixpoint 3-valued semantics for autoepistemic logic
Venue: arXiv cs.LO 1999
Year: 1999

The paper presents a constructive fixpoint semantics for autoepistemic logic (AEL). This fixpoint characterizes a unique but possibly three-valued belief set of an autoepistemic theory. It may be three-valued in the sense that for a subclass of formulas F, the fixpoint may not specify whether F is believed or not. The paper presents a constructive 3-valued semantics for autoepistemic logic (AEL). We introduce a derivation operator and define the semantics as its least fixpoint. The semantics is 3-valued in the sense that, for some formulas, the least fixpoint does not specify whether they are believed or not. We show that complete fixpoints of the derivation operator correspond to Moore's stable expansions. In the case of modal representations of logic programs our least fixpoint semantics expresses well-founded semantics or 3-valued Fitting-Kunen semantics (depending on the embedding used). We show that, computationally, our semantics is simpler than the semantics proposed by Moore (assuming that the polynomial hierarchy does not collapse).