bluuebunny/crossref_metadata_2025 huggingface dataset:
Testing of Ada compiler diagnostics
Authors: Kaufman Vitali Sh. , Pavlov Mikhail V. , Rybin Sergei I.
Published: October 2004

This paper presents the main results obtained by the research group of the Computer Science Department of Moscow State University in developing methods and tools for validating compiler diagnostics.Methods of diagnostic test design based on partially formalized models are shown. In addition, a diagnostic test suite and results of its application are described.
On key distribution protocols for repeated authentication
Authors: Syverson Paul
Published: October 2004

In [KSL92], Kehne et al. present a protocol (KSL) for key distribution. Their protocol allows for repeated authentication by means of a ticket. They also give a proof in BAN logic [BAN89] that the protocol provides the principals with a reasonable degree of trust in the authentication and key distribution. They present an optimality result that their protocol contains a minimal number of messages. Nonetheless, in [NS93] Neuman and Stubblebine present a protocol (NS) as an explicit alternative to KSL that requires one less message in the initial authentication and key distribution. One goal of this paper is to examine some of the reasons for this discrepancy. Another goal is to demonstrate possible attacks on NS. Like any attacks on cryptographic protocols, these depend on assumptions about implementation details. But, when possible they are serious: a penetrator can initiate the protocol, masquerade as another principal, obtain the session key, and even generate the session key herself.
1
We will set out implementation assumptions required for the attacks to take place and implementation assumptions that preclude such an attack. We will also look at other protocols, including one that is not subject to this form of attack and has the same number of messages as NS. Finally, we will briefly discuss the logical analysis of these repeat authentication protocols.
A response to Cheriton and Skeen's criticism of causal and totally ordered communication
Authors: Birman Ken
Published: October 2004

In a paper to be presented at the 1993 ACM Symposium on Operating Systems Principles, Cheriton and Skeen offer their understanding of causal and total ordering as a communication property. In this brief rebuttal. I present some responses to their criticism, and also explain why I find their discussion of causal and total communication ordering to be narrow and incomplete.
Why bother with CATOCS?
Authors: van Renesse Robbert
Published: October 2004

In their paper
Understanding the Limitations of Causally and Totally Ordered Communication
[CS93], David Cheriton (Stanford University) and Dale Skeen (Teknekron Software Systems, Inc.) identify several potential problems in using causally and totally ordered communication support (CATOCS), and conclude that such support is of limited merit at best. This is a remarkable statement, given that, first, many well-known researchers are advocating a CATOCS model, and second, several projects have used CATOCS support successfully.[CS93] lists four limitations. They recognize that the third limitation is only a generalization of the second, so that there are really only three. However, in the course of the paper they state an additional two. For convenience, we combine overhead and scalability concerns. In total, therefore, the paper actually does contain four limitations. These are:• Lamport's event ordering cannot always be recognized in a system, and therefore correct causal delivery cannot always be enforced.• CATOCS delivery is not sufficient to guarantee the consistency of user-level state. The mechanisms that do guarantee such consistency obviate the need for CATOCS.• CATOCS events, even if atomic, are not
durable
, that is, they may be lost after delivery.• CATOCS presents unacceptable overhead, and does not scale.They conclude that CATOCS is at best very narrowly applicable. These limitations are stated without proof or experimental verification. Here, we undertake to refute their conclusion by showing their examples and proof incorrect. We assume familiarity with the contents of [CS93], and, for the sake of brevity, do not repeat their examples.
An “open” oriented file system
Authors: Mahoney Bill
Published: October 2004

A custom application involving a high percentage of open and close file system calls has provided incentive to design and implement a new file system. The fact that many files are small, and that files are referenced by number instead of by name has allowed several design decisions to be made in an attempt to improve performance. The design of the file system is described, and a comparison is made between the new system and a more traditional system to see if the design has been successful.
A short note on implementing “new” machine instructions by software for efficient test of page accessibility
Authors: Liedtke Jochen
Published: October 2004

Checking a page's accessibility (not mapped, read only or read/write) is sometimes useful for operating system kernels. We describe a technique for extending a processor's instruction set (by software) so that accessibility tests can in most cases be done faster than parsing the page table tree by software.
A periodic symmetrically-initiated load balancing algorithm for distributed systems
Authors: Benmohammed-Mahieddine K. , Dew P. M.
Published: October 2004

This paper presents a new load balancing algorithm called Periodic Symmetrically-Initiated (PSI). It is symmetrically initiated and uses periodic polling of a single random node to acquire information about the system state. Its performance on a distributed system is compared to the following algorithms: Random, Sender, Receiver, and Symetric. These algorithms have been evaluated in [15] where the terms Sender and Receiver are referred to as Forward and Reverse respectively. The algorithms performance under different variants to the system model is also studied to assess the sensitivity of the PSI algorithm to changes in the system attributes. This includes the communication bandwidth, the system size, the file system structure, and the workload model. The results of the study show that the PSI algorithm out performs the existing algorithms and is robust over a range of system attributes.
Making distributed multimedia systems secure
Authors: Zimmermann Chris
Published: October 2004

The following paper describes a security scheme for a distributed multimedia environment called Switchboard. After a brief introduction to the philosophy of the Switchboard and the underlying system model, the main building blocks of the concept are described. These are: an authentication mechanism preventing intruder attacks and a protection scheme based on an extended access control matrix approach. This protection scheme covers both static and dynamic aspects of access protection for multimedia devices. Some remarks on the implementation of the mechanisms and a discussion conclude this paper.
BATCES solution #1
Authors: Shumate Ken
Published: October 2004

In mid-1992 the SIGAda Object Oriented Working Group (OOWG) prepared a sample problem for the purpose of comparing various object-oriented methodologies and the resulting object-oriented designs. Solutions to the problem were presented at Tri-Ada '92 in Orlando at a session called "Object-Oriented Methodology Demonstration (OOMD)." This paper was prepared at the request of the OOWG as a follow-up to the presentation. The phrase "Solution #1" in the title is to suggest later alternate approaches and solutions. This paper takes the position that it is important to address software development in the context of the overall systems development process, and the related position that although it is useful to address objects during the analysis phase, an effective object-oriented design is easy to derive from a requirements analysis that is largely functional in nature.
Context-free languages
Authors: Spencer Thomas H.
Published: October 2004

This paper introduces a new level into the Chomsky of formal languages. Specifically the content-free languages are a subset of the regular languages. Content-free languages have many interesting properties.
Effect of packet losses on end-user cost in internetworks with usage based charging
Authors: Kumar Brijesh
Published: October 2004

One of the most sensitive and controversial aspects in incorporating usage based charging in internetworks is the accounting of the packets that are dropped by transit domains during transit from source domain to destination domain. From the perspective of network users, lost packets are a waste of resources, and constitute additional burden on them. We use simulation to quantify the effect of packet losses on end-user cost in an internetwork consisting of transit domains with usage based charging policies. Our simulation shows that time based cost, packet based cost and byte based cost are differently affected by the changes in the packet loss probability of the inter-domain route. This will have implications for inter-domain routing protocols.
A survey of X protocol multiplexors
Authors: Baldeschwieler John Eric , Gutekunst Thomas , Plattner Bernhard
Published: October 2004

An X multiplexor allows a single X Window System client to be displayed and interacted with on several X servers simultaneously. Such a service is necessary for the construction of a computer-supported cooperative work (CSCW) environment such as JVTOS (Joint Viewing and Tele-Operation Service) which is being implemented within RACE II project CIO
1
. This paper describes several existing X multiplexors and evaluates their usefulness for JVTOS.
Multicast channels for collaborative applications
Authors: Pendergast Mark O.
Published: October 2004

This paper describes an architecture and communications system for supporting Group Support Systems (GSS) applications via the use of GSS Channel Objects. GSS applications enable group tasks such as co-authoring, communications, negotiation, problem solving, and system design to be performed. GSS Channel Objects facilitate the creation of GSS applications by providing virtual, multicast connections which parallel the meeting room metaphor of communications. This paper discusses the requirements, design, and implementation of GSS Channel Objects. This includes performance testing on Ethernet and Token Ring LANs.
Internet protocol traffic analysis with applications for ATM switch design
Authors: Schmidt Andrew , Campbell Roy
Published: October 2004

Knowledge of data traffic behavior is fundamental to the efficient design and implementation of a virtual circuit packet switch and its supporting policies and mechanisms. In this paper, we examine the behavior of local and wide area
Internet Protocol
(IP) networks, study connection and connectionless protocols, and use our results to estimate the behavior of a virtual circuit network replacement for these networks.
Integrating security in inter-domain routing protocols
Authors: Kumar Brijesh , Crowcroft Jon
Published: October 2004

Network routing protocols work in a vulnerable environment. Unless protected by appropriate security measures, their operation can be easily subverted by intruders capable of modifying, deleting or adding false information in routing updates. This paper first analyses threats to the secure operation of inter-domain routing protocols, and then proposes various counter measures to make these protocols secure against external threats.
The design of a transceiver for packet video communication on an integrated services network
Authors: Andreatos A. S. , Protonotarios E. N. , De Grandi G.
Published: October 2004

This article describes the architecture of a special Packet Video Transceiver, which is appropriate for the communication of broadcast television signals between two stations of an Integrated Services Network. The system performs line processing and can detect and/or correct various kinds of errors concerning the reception of packets at the receiver. Additional information is given about the design and operation of a special frequency-regulation system which the Receiver uses as a master clock source. This system tries to evaluate the Transmitter scanning frequency basing the evaluation on the timing of the incoming packets transmitted through a noisy channel.
The representation of a program in the Blum-Shub-Smale theory of computation over an arbitrary ring
Authors: Xiao-Long Hu
Published: October 2004

In the paper "On a Theory of Computation and Complexity over the Real Numbers: NP Completeness, Recursive Functions and Universal machines" (BSS 1989), the authors, Lenore Blum, Mike Shub, and Steve Smale, generalize the notion of computability from the set of natural numbers to an arbitrary ordered ring. In particular they discuss the existence of a Universal Machine over such a ring and the "godel" number or "code" of machines defined on such a ring. In this short paper we wish to correct some minor error in their definition of a "code" of a machine.
On per-session end-to-end delay distributions and the call admission problem for real-time applications with QOS requirements
Authors: Yates David , Kurose James , Towsley Don , Hluchyj Michael G.
Published: October 2004

A crucial problem facing the designers and deployers of future high-speed networks is providing applications with quality of service (QOS) guarantees. For soft real-time applications, which are delay sensitive but loss tolerant, delay distribution is an important QOS measure of interest. In this paper we study (through simulation) the end-to-end delay distribution seen by individual sessions under simple first-come first-served (FCFS) multiplexing in a network model with two significant features: (1) all traffic is connection-oriented, (2) cross traffic along routes is representative of that seen by calls in a moderately sized wide area network (i.e., less than 100 switches). We compare these delay distributions with the worst case point-valued analytic delay bounds predicted by three different techniques for providing such bounds (two of which require a more sophisticated link-level scheduling policy). We also consider the per-hop delay distributions seen as a session progresses "deeper" into the network and determine the sensitivity of these delay distributions to the manner in which the interfering traffic is modeled. Finally, we use our delay distribution results to examine the tradeoff between the QOS requested by a call, the manner in which the QOS guarantee is provided, and the number of calls that are admitted at the requested QOS.
An adaptive congestion control scheme for real-time packet video transport
Authors: Kanakia Hemant , Mishra Partho P. , Reibman Amy
Published: October 2004

In this paper we show that modulating the source rate of a video encoder based on feedback information from the network results in graceful degradation in picture quality during periods of congestion. Such source rate modulation techniques have been used in the past in designing video encoders used to generate data at a fixed rate. In such constant bit rate encoders, the source rate modulation is done using feedback information about the occupancy of a local buffer. Since the buffer is local, the feedback information is available instantaneously to the encoder. In the proposed scheme, the feedback information is delayed because it comes from within a packet-switching network. The feedback provides information about the traffic at switches along the path of the video connection. We show that the proposed scheme performs well, even though the information is delayed for relatively large intervals of time. We believe that the use of such schemes will simplify the architecture used for supporting real-time services in future nationwide gigabit networks.
An adaptive framework for dynamic access to bandwith at high speeds
Authors: Fendick Kerry W. , Rodrigues Manoel A.
Published: October 2004

Emerging technologies for high-speed data network provide users with explicit feedback about congestion. Users, however, have questioned whether feedback can help in avoiding congestion in wide-area networks that operate at speeds of multiple megabits- or gigabits-per-second. In this paper we analyze a class of adaptive schemes with delayed feedback, where adaptive sources interact with each other as well as with non-adaptive sources through a single queue. We model the network as a stochastic, delay-differential equation and the rate at which an adaptive source transmits data as a fluid. Our model accounts for different levels of traffic burstiness introduced by the non-adaptive sources and for distinct propagation delays for different adaptive sources. We show how the performance of the system scales with increasing network speeds for quite general fluctuations in the bandwidth available to the adaptive sources. Simulation results show the accuracy of the model's predictions as a function of key parameters. This paper should raise the expectations of users about the potential effectiveness of responding to congestion notification.
On the self-similar nature of Ethernet traffic
Authors: Leland Will E. , Taqqu Murad S. , Willinger Walter , Wilson Daniel V.
Published: October 2004

We demonstrate that Ethernet local area network (LAN) traffic is statistically
self-similar,
that none of the commonly used traffic models is able to capture this fractal behavior, and that such behavior has serious implications for the design, control, and analysis of high-speed, cell-based networks. Intuitively, the critical characteristic of this self-similar traffic is that there is no natural length of a "burst": at every time scale ranging from a few milliseconds to minutes and hours, similar-looking traffic bursts are evident; we find that aggregating streams of such traffic typically intensifies the self-similarity ("burstiness") instead of smoothing it.Our conclusions are supported by a rigorous statistical analysis of hundreds of millions of high quality Ethernet traffic measurements collected between 1989 and 1992, coupled with a discussion of the underlying mathematical and statistical properties of self-similarity and their relationship with actual network behavior. We also consider some implications for congestion control in high-bandwidth networks and present traffic models based on self-similar stochastic processes that are simple, accurate, and realistic for aggregate traffic.
A case for caching file objects inside internetworks
Authors: Danzig Peter B. , Hall Richard S. , Schwartz Michael F.
Published: October 2004

This paper presents evidence that several, judiciously placed file caches could reduce the volume of FTP traffic by 42%, and hence the volume of all NSFNET backbone traffic by 21%. In addition, if FTP client and server software automatically compressed data, this savings could increase to 27%. We believe that a hierarchical architecture of whole file caches, modeled after the existing name server's caching architecture, could become a valuable part of any internet.We derived these conclusions by performing trace driven simulations of various file caching architectures, cache sizes, and replacement policies. We collected the traces of file transfer traffic employed in our simulations on a network that connects the NSFNET backbone to a large, regional network. This particular regional network is responsible for about 5 to 7% of NSFNET traffic.While this paper's analysis and discussion focus on caching for FTP file transfer, the proposed caching architecture applies to caching objects from other internetwork services.
Linear recursive networks and their applications in topological design and data routing
Authors: Jing Hsu Wen , Das Amitabha , Chung Moon Jung
Published: October 2004

We present a new class of interconnection topologies called the
Linear Recursive Networks.
It is shown that each member of this fairly large class of network topologies possesses a recursively-decomposable structure. The path and connectivity properties of the entire class of networks are analyzed and found to have useful features. It is also demonstrated that Point-To-Point or Broadcasting/Gathering operations can be performed efficiently on all Linear Recursive Networks. The preliminary results suggest that the Linear Recursive Networks potentially have many applications.
A distributed queueing random access protocol for a broadcast channel
Authors: Xu Wenxin , Campbell Graham
Published: October 2004

For decades there has been a search for a multiple access protocol for a broadcast channel that would provide a performance that approached that of the ideal M/D/1 queue. This ideal performance would provide immediate access at light loads and then seamlessly move to a reservation system at high offered loads. DQRAP (distributed queueing random access protocol) provides a performance which approaches this ideal. Furthermore it is accomplished using as few as three control minislots which suggests that, aside from establishing new theoretical bounds, DQRAP will be of great practical value.DQRAP requires that channel time be divided into slots each of which consists of one data slot and m control minislots, and that each station maintain two common distributed queues. One queue is called the data transmission queue, or simply TQ, used to organize the order of data transmission, the other queue is the collision resolution queue, or simply RQ, which is used to resolve the collisions and to prevent collisions by new arrivals. The protocol includes data transmission rules, request transmission rules and queuing discipline rules. Modelling and simulation indicate that DQRAP, using as few as 3 minislots, achieves a performance level which approaches that of a hypothetical perfect scheduling protocol, i.e., the M/D/1 system, with respect to throughput and delay. DQRAP could prove useful in packet radio, satellite, broadband cable, cellular voice, WAN, and passive optical networks.
Extensible file systems in spring
Authors: Khalidi Yousef A. , Nelson Michael N.
Published: October 2004

In this paper we describe an architecture for extensible file systems. The architecture enables the extension of file system functionality by composing (or stacking) new file systems on top of existing file systems. A file system that is stacked on top of an existing file system can access the existing file system's files via a well-defined naming interface and can share the same underlying file data in a coherent manner. We describe extending file systems in the context of the Spring operating system. Composing file systems in Spring is facilitated by basic Spring features such as its virtual memory architecture, its strongly-typed well-defined interfaces, its location-independent object invocation mechanism, and its flexible naming architecture. File systems in Spring can reside in the kernel, in user-mode, or on remote machines, and composing them can be done in a very flexible manner.
The Zebra striped network file system
Authors: Hartman John H. , Ousterhout John K.
Published: October 2004

Zebra is a network file system that increases throughput by striping file data across multiple servers. Rather than striping each file separately, Zebra forms all the new data from each client into a single stream, which it then stripes using an approach similar to a log-structured file system. This provides high performance for writes of small files as well as for reads and writes of large files. Zebra also writes parity information in each stripe in the style of RAID disk arrays; this increases storage costs slightly but allows the system to continue operation even while a single storage server is unavailable. A prototype implementation of Zebra, built in the Sprite operating system, provides 4--5 times the throughput of the standard Sprite file system or NFS for large files and a 20%-3x improvement for writing small files.
Understanding the limitations of causally and totally ordered communication
Authors: Cheriton David R. , Skeen Dale
Published: October 2004

Causally and totally ordered communication support (CATOCS) has been proposed as important to provide as part of the basic building blocks for constructing reliable distributed systems. In this paper, we identify four major limitations to CATOCS, investigate the applicability of CATOCS to several classes of distributed applications in light of these limitations, and the potential impact of these facilities on communication scalability and robustness. From this investigation, we find limited merit and several potential problems in using CATOCS. The fundamental difficulty with the CATOCS is that it attempts to solve problems at the communication level in violation of the well-known "end-to-end" argument.
Subcontract
Authors: Hamilton Graham , Powell Michael L. , Mitchell James G.
Published: October 2004

A key problem in operating systems is permitting the orderly introduction of new properties and new implementation techniques. We describe a mechanism, subcontract, that within the context of an object-oriented distributed system permits application programmers control over fundamental object mechanisms. This allows programmers to define new object communication mechanisms without modifying the base system. We describe how new subcontracts can be introduced as alternative communication mechanisms in the place of existing subcontracts. We also briefly describe some of the uses we have made of the subcontract mechanism to support caching, crash recovery, and replication.
Interposition agents
Authors: Jones Michael B.
Published: October 2004

Many contemporary operating systems utilize a system call interface between the operating system and its clients. Increasing numbers of systems are providing low-level mechanisms for intercepting and handling system calls in user code. Nonetheless, they typically provide no higher-level tools or abstractions for effectively utilizing these mechanisms. Using them has typically required reimplementation of a substantial portion of the system interface from scratch, making the use of such facilities unwieldy at best.This paper presents a toolkit that substantially increases the ease of interposing user code between clients and instances of the system interface by allowing such code to be written in terms of the high-level objects provided by this interface, rather than in terms of the intercepted system calls themselves. This toolkit helps enable new interposition agents to be written, many of which would not otherwise have been attempted.This toolkit has also been used to construct several agents including: system call tracing tools, file reference tracing tools, and customizable filesystem views. Examples of other agents that could be built include: protected environments for running untrusted binaries, logical devices implemented entirely in user space, transparent data compression and/or encryption agents, transactional software environments, and emulators for other operating system environments.
The impact of operating system structure on memory system performance
Authors: Chen J. Bradley , Bershad Brian N.
Published: October 2004

In this paper we evaluate the memory system behavior of two distinctly different implementations of the UNIX operating system: DEC's Ultrix, a monolithic system, and Mach 3.0 with CMU's UNIX server, a microkernel-based system. In our evaluation we use combined system and user memory reference traces of thirteen industry-standard workloads. We show that the microkernel-based system executes substantially more non-idle system instructions for an equivalent workload than the monolithic system. Furthermore, the average instruction for programs running on Mach has a higher cost, in terms of memory cycles per instruction, than on Ultrix. In the context of our traces, we explore a number of popular assertions about the memory system behavior of modern operating systems, paying special attention to the effect that Mach's microkernel architecture has on system performance. Our results indicate that many, but not all of the assertions are true, and that a few, while true, have only negligible impact on real system performance.
Lightweight recoverable virtual memory
Authors: Satyanarayanan M. , Mashburn Henry H. , Kumar Puneet , Steere David C. , Kistler James J.
Published: October 2004

Recoverable virtual memory
refers to regions of a virtual address space on which transactional guarantees are offered. This paper describes
RVM
, an efficient, portable, and easily used implementation of recoverable virtual memory for Unix environments. A unique characteristic of RVM is that it allows independent control over the transactional properties of atomicity, permanence, and serializability. This leads to considerable flexibility in the use of RVM, potentially enlarging the range of applications than can benefit from transactions. It also simplifies the layering of functionality such as nesting and distribution. The paper shows that RVM performs well over its intended range of usage even though it does not benefit from specialized operating system support. It also demonstrates the importance of intra- and intertransaction optimizations.
Network objects
Authors: Birrell Andrew , Nelson Greg , Owicki Susan , Wobber Edward
Published: October 2004

A network object is an object whose methods can be invoked over a network. This paper describes the design, implementation, and early experience with a network objects system for Modula-3. The system is novel for its overall simplicity. The paper includes a thorough description of realistic marshaling algorithms for network objects.
Authentication in the Taos operating system
Authors: Wobber Edward , Abadi Martín , Burrows Michael , Lampson Butler
Published: October 2004

We describe a design and implementation of security for a distributed system. In our system, applications access security services through a narrow interface. This interface provides a notion of identity that includes simple principals, groups, roles, and delegations. A new operating system component manages principals, credentials, and secure channels. It checks credentials according to the formal rules of a logic of authentication. Our implementation is efficient enough to support a substantial user community.
Providing location information in a ubiquitous computing environment (panel session)
Authors: Spreitzer Mike , Theimer Marvin
Published: October 2004

To take full advantage of the promise of ubiquitous computing requires the use of location information, yet people should have control over who may know their whereabouts. We present an architecture that achieves these goals for an interesting set of applications. Personal information is managed by User Agents, and a partially decentralized Location Query Service is used to facilitate location-based operations. This architecture gives users primary control over their location information, at the cost of making more expensive certain queries, such as those wherein location and identity closely interact. We also discuss various extensions to our architecture that offer users additional trade-offs between privacy and efficiency. Finally, we report some measurements of the unextended system in operation, focusing on how well the system is actually able to track people. Our system uses two kinds of location information, which turn out to provide partial and complementary coverage.
The ITHACA office object model
Authors: Ang James S. K. , Conrath D. W.
Published: October 2004

This paper presents an object-oriented approach to modeling an office, including both its content and the activities that are carried out within it. This is a part of a larger research effort---the ITHACA Project (Integrated Toolkit for Highly Advanced Computer Applications). Its purpose is to provide software engineers and application programmers with a generic framework within which to develop large, distributed office support systems. The set of interrelated models contains: the active object, the passive object and the procedure models. The active object model represents persons (or actors), organizational structures and their linkages through roles. Office facilities (e.g., cabinets, tables, tops-of-desks, wastebaskets) and information (e.g., documents, letters) are captured by the passive object model. The relationships among the various objects are expressed by both specified relationship attributes and other attributes that can be derived from them. The procedure model consists of office operators (e.g., Move, Edit, Create, Send) that are used as basic building blocks for defining office procedures.The model is presently being used to develop software for the ITHACA Project. A prototype of the active office object model has been developed, written in CooL---Combined object-oriented Language. The prototype will be used as a basis for developing a more complete systems architecture, also described in the paper.
Physical database design
Authors: Spiegler Israel , Widder David
Published: October 2004

Methods and techniques are available for helping the system development effort at the analysis and logical design stages. Yet, once the system has been defined, the designer is left with many decisions that will affect the construction, operation and maintenance stages. This article proposes a conceptual model to support the database designer at the physical design stage. The model incorporates database design methodology with decision support system (DSS) methods. A prototype version of the model is described, together with an analysis of a case study. Such a model may be integrated into a CASE methodology to encompass the entire information system development cycle.
An object algebra for object-oriented database systems
Authors: Alhajj Reda , Arkun M. Erol
Published: October 2004

Although messages can be used to manipulate objects, a query language is still considered a required component of object-oriented database management systems. An object algebra is proposed, as a formal foundation for a query language, that can handle both the state and the behavior of objects. Creation of new objects and introduction of new relationships among objects/classes are also facilitated by the object algebra. The object algebra subsumes the five basic relational algebraic operations while providing several additional powerful ones. Each operand, as well as the result of a query, is a pair of sets: a set of objects and a set of message expressions formed as a sequence of messages accepted by the former set. The result of a query possesses the properties of an operand, thus providing the closure property for operations. Every class has a defined set of objects and derived set of message expressions, thus a class possesses the characteristics of an operand. The result of a query also possesses the characteristics of a class. The superclass/subclass relationships of a query result with the operands is established to provide persistency to the result as a class, and as a consequence algebraic equivalents of schema evolution functions are developed. Object algebra is as powerful as relational and nested relational algebra. In fact, due to message expressions that serve to handle both stored and derived values, object algebra provides greater computational power.
Open issues and challenges in providing quality of service guarantees in high-speed networks
Authors: Kurose Jim
Published: October 2004

In this paper we identify the challenges and open issues involved in providing quality-of-service (QOS) guarantees to sessions in a high-speed wide area network and briefly survey research in this area. Four approaches towards providing QOS guarantees are described and discussed: the tightly controlled approach, the approximate approach, the bounding approach, and the observation-based approach.
Extending the IP internet through address reuse
Authors: Tsuchiya Paul F. , Eng Tony
Published: October 2004

The two most compelling problems facing the IP Internet are IP address depletion and scaling in routing. This paper discusses the characteristics of one of the proposed solutions---address reuse. The solution is to place Network Address Translators (Nat) at the borders of stub domains. Each Nat box has a small pool of globally unique IP addresses that are dynamically assigned to IP flows going through Nat. The dynamic assignment is coordinated with Domain Name Server operation. The IP addresses inside the stub domain are not globally unique---they are reused in other domains, thus solving the address depletion problem. The pool of IP addresses in Nat is from a subnet administered by the regional backbone, thus solving the scaling problem. The main advantage of Nat is that it can be installed without changes to any existing systems, although FTP will fail in some but not all cases. This paper presents a preliminary design for Nat, and discusses its pros and cons.
Reserved bandwidth and reservationless traffic in rate allocating servers
Authors: Berstein Greg M.
Published: October 2004

Bandwidth efficiency in communication networks can require supporting traffic with greatly differing quality of service requirements, particularly in terms of delay. The facilities needed to permit users to take advantage of excess bandwidth include (i) a method of conveying network state information to the source, and (ii) a method for guaranteeing quality of service requirements. Reservation oriented rate allocating servers (RASs) provide QOS guarantees while reservationless RASs provide fairness. This paper gives a technique for modifying a reservation oriented RAS to accommodate reservationless traffic and allow users with bandwidth reservations to take advantage of excess network bandwidth. In addition, this paper shows how to use the packet pair bandwidth probing technique with these new RASs to provide effective and efficient congestion control.
Packets found on an internet
Authors: Bellovin Steven M.
Published: October 2004

As part of our security measures, we spend a fair amount of time and effort looking for things that might otherwise be ignored. Apart from assorted attempted penetrations, we have also discovered many examples of anomalous behavior. These range from excessive ICMP messages to nominally-local broadcast packets that have reached us from around the world.
The use of message-based multicomputer components to construct gigabit networks
Authors: Cohen Danny , Finn Gregory G. , Felderman Robert , DeSchon Annette
Published: October 2004

The typical node of a message-based multicomputer consists of a microprocessor, router and memory. At the California Institute of Technology, the Mosaic project has integrated such a node onto a single chip. That reduction in scale fundamentally changes the scope of node application, since nodes become both very small, and inexpensive.Mosaic nodes may be employed to process, to generate, or to receive data. Since the router in a Mosaic node is independent of the microprocessor, computation and routing take place simultaneously. These nodes may be used to create general purpose gigabit LANs. They may also be used to create special purpose gigabit networks to interconnect instrumentation within spacecraft or aircraft.The ATOMIC project at USC/ISI is using Mosaic nodes to prototype a gigabit LAN testbed. This testbed is operational. Networking and administration software provides full TCP/IP compatibility. Packets have been exchanged between two interfaces at a rate above one gigabit per second (Gb/s).An individual ATOMIC interface is both inexpensive and small, consisting of one Mosaic chip, four SRAM chips and clock logic. Two interfaces easily fit onto a postcard-sized circuit board. Their low cost makes it practical to include several interfaces within a host, providing an interior Gb/s distribution network, multiple access points to the LAN for greater performance or redundancy, and other capabilities that are not yet fully explored. The results reported in this paper represent actual data obtained from the prototype.
A simpler analysis of algorithm 65 (find)
Authors: Raman Rajeev
Published: October 2004

We present a simpler analysis of the expected number of comparisons made by Hoare's selection algorithm (
Comm. ACM
4 (1961), pp. 321--322).
Ada design of a neural network
Authors: Carter Jeffrey R. , Sanden Bo I.
Published: October 2004

A neural network is a computer program structured as a simplified model of a brain. It contains nodes (analogous to neurons) and connections between nodes (analogous to synapses). Neural networks can solve difficult pattern-matching problems. A node sums the inputs it receives from other nodes and passes the result through a transfer function to produce its output. A modifiable weight is associated with each connection. A network is trained on a given training set of inputs. During training, the weights are successively adjusted to produce the desired output.Classical design and implementation of neural networks are based on arrays that hold the node values and connection weights. The control structure consists of nested loops through these arrays. This paper suggests instead an object-based design where the nodes are modeled as objects to be operated on. This design models the conceptual network more closely and makes the software more understandable and maintainable. A generic Ada package representing a neural network is presented in some detail.
Ada in Russia
Authors: Rybin Sergei I.
Published: October 2004

An overall description of the history and current state of the Ada-situation in Russia is presented. Some key details of the situation are outlined. The Moscow State University is proposed as the base organization for international communication and cooperation with the Russian Ada community.
A structure for a defense software reuse marketplace
Authors: Moore James W.
Published: October 2004

The paper begins by briefly examining the demand for reusable software components and the characteristics of the defense industry which serve to differentiate its needs from those of a broader commercial reuse industry. The approach of providing a single library for defense reuse is examined and discarded. The bulk of the paper examines how a reuse marketplace might be built upon the existence of multiple libraries. The operations of a reuse marketplace are described and possible specializations of libraries are suggested. Finally, the pioneering contributions of a few current efforts are noted.
Automatic compiler recognition of monitor tasks
Authors: Schilling Jonathan L. , Nielsen Johan Olmütz
Published: October 2004

Monitor tasks, also known as passive tasks, are a kind of Ada task that is subject to well-known and very powerful optimization. In most compilation systems that perform this optimization, monitor tasks are identified to the complier by the user, via an implementation-defined pragma. This paper describes an alternate approach, whereby the compiler automatically recognizes and optimizes monitor tasks, without need of a pragma, compiler option, or any other user action. The advantages and disadvantages of this approach are discussed, both in terms of the functional impact to the user and the execution-time efficiency of the optimization.
Ada real-time systems and basic priority inheritance
Authors: Briand Loïc
Published: October 2004

The Rate Monotonic Scheduling theory is often presented as the ultimate means for improving dramatically and easily the schedulability of Ada Real-Time systems. To assess its practical impact on Real-Time systems, the behavior of a hard-deadline simulated task set is statstically analyzed in different contexts of scheduling (standard Ada FIFO scheduling or basic priority inheritance) and priority allocation (higher priority to the shorter deadline or to the shorter period).
Static analysis of Ada programs
Authors: Ehrenfried Daniel H.
Published: October 2004

The upcoming standardization of the Ada Semantic Interface Specification (ASIS) makes possible the development of portable static analysis tools for Ada programs. This paper introduces this class of back-end CASE tools, lists their capabilities, and describes how they can be used during the software-development process to increase overall software quality. The description is based on one such tool: the Ada Analyzer developed by Little Tree Consulting.
Memory management in Ada83 and Ada9X
Authors: Van Vlierberghe Stef
Published: October 2004

There has been a significant evolution in the design of Ada9X with respect to meeting memory management requirements. This paper will introduce the memory management problem, and possible approaches in Ada83 and Ada9X. Today the Committee Draft includes full support for user-defined assignment and finalization, and this paper will illustrate how the new language features can be used to provide solutions that are both elegant and robust.An example of a primitive list component is used to illustrate the problem, and to illustrate the evolution from Ada83 to Ada9X.
Automating improvements to the quality of your code
Authors: Radi Thomas S.
Published: October 2004

One aspect of code quality is a design (or a set of source code) that contains only things that are relevant to the solution of the problem at hand. There are no redundant or superfluous entities. In a "good" (high quality) design everything has a purpose, and its purpose is clear. Code quality can be improved by eliminating redundant and unnecessary declarations. This paper provides a technique that can help improve code quality. It identifies several anomalies that can exist in source code, provides a means of identifying the anomalies, and suggests methods to eliminate or minimize the impact of the anomalies.
An Ada 9X subset for inheritance-based reuse and its translation to Ada 83 (Part 2)
Authors: Hirasuna Michael
Published: October 2004

An object oriented reuse strategy based on the Ada 9X inheritance syntax is presented. This paper defines a minimal Ada 9X subset that implements inheritancebased reuse, and outlines its translation to Ada 83. Inheritance allows software modules to be reused without modification to the original source. It is preferred to the "copy and tailor" approach, which has limited software life-cycle benefit since tailored copies need to be tested and maintained.Reuse may be applied at the low level, for components, or at higher levels, for subsystems. Inheritance may be used at any level of reuse, but it is more important for the higher levels. Ada 83 does not support inheritance, but low-level reuse can still be implemented in the form of generic components [BOO87]. The cost advantage from low-level reuse is already assumed when planning today's software systems. Further cost savings must come from high-level reuse, which needs inheritance to be implemented properly. Inheritance will be fully supported in Ada 9X.The approach presented here may be used in a reuse plan for a system that will start development before Ada 9X becomes viable. The Ada 9X subset allows the system software to be structured for reuse, to be implemented in Ada 83, and to be ready for migration to Ada 9X.This is the second part of a two-part paper. The first part discussed the reuse strategy and defined an Ada 9X subset that will implement it. In this part, a translation from the Ada 9X subset to Ada 83 will be outlined.
AdaPT and Ada 9X
Authors: Goldsack S. J. , Holzbacher-Valero A. A. , Volz R. , Waldrop R.
Published: October 2004

Following an initial proposal developed at the 4th Ada Real Time Programming Workshop, Nemacolin Woodlands, 1989, and further meetings to pursue the ideas, a series of papers were published [1][2][3] describing and discussing possible Ada language extensions to support the development of distributable programs. The language consisting of Ada with these extensions has been called AdaPT, which may be thought of as Ada with partitions. After introducing AdaPT, this paper describes how the AdaPT constructs can be implemented in Ada 83, and then shows how they can be related to constructs proposed for Ada 9X. In general, the paper endorses the ideas of the 9X team, and suggests an elegant synthesis bringing together two apparently unrealted aspects of the language (type derivation and distribution) that can provide a basis for managing distribution.
Endian-independent record representation clauses
Authors: Cohen Norman H.
Published: October 2004

Ada-83 record representation clauses can be written in a way that confines dependence on the compiler's bit-numbering scheme to a few lines of the program.