bluuebunny/crossref_metadata_2025 huggingface dataset:
Future of IEEE standard for Ada PDL to be considered
Authors: Moore James W.
Published: October 2004

The ANSI/IEEE standard describing Ada as a Program Design Language was approved by the IEEE in 1986 and reaffirmed in 1992. Normal IEEE procedures would require that it next be reconsidered for withdrawal, revision or reaffirmation in 1997. The completion of the Ada 95 language revision, though, suggests that reconsideration of the standard should be accelerated. After a quick overview of IEEE standardization, this article briefly describes the history of the Ada/PDL standard and its contents. It poses some of the issues relevant to reconsideration of the standard. Finally, it solicits volunteers to help determine the future of the standard.
Task time lines as a debugging tool
Authors: Briggs J. S. , Jamieson S. D. , Randall G. W. , Wand I. C.
Published: October 2004

Debugging distributed programs is more difficult than debugging sequential ones. This paper describes a means of making this easier by presenting the user with a "time line" view of an Ada program. Each time line shows the successive states of an Ada task as easily recognisable symbols on a time axis. Communication and sychronisation between tasks is shown graphically by lines connecting the time lines. The paper shows how this representation can be used to depict typical Ada tasking activity, and describes a tool that provides a useful interface to the representation.
A new look at an old protocol
Authors: Syverson Paul F.
Published: October 2004

Analyses of the Needham-Schroeder protocol using the logics SVO and BAN are discussed. It is shown that the protocol may fail to meet goals derived in the [BAN89] analysis of it. The features of SVO analysis revealing the limitations on appropriateness of these goals are indicated.
Analysis of caching algorithms for distributed file systems
Authors: Reed Benjamin , Long Darrell D. E.
Published: October 2004

When picking a cache replacement policy for file systems, LRU
(Least Recently Used)
has always been the obvious choice, because of the temporal locality found in programs and data. However, in the case of Sun NFS servers much of the locality is filtered out by the client cache. It has been conjectured that this filtering of locality by the client caches render LRU ineffective as a server cache replacement policy. This study disproves the conjecture by simulating a NFS server cache with real world traces. Traces were taken of NFS read and write requests sent to an NFS server. These traces were then run through a cache simulator using six different cache replacement policies: Least Recently Used
(LRU),
Least Frequently Used
(LFU),
Frequency Based Replacement
(FBR),
First In First Out
(FIFO),
Random
(RAND),
and Optimal
(OPT).
RAND and OPT were used to provide lower and upper bounds on performance. Results show that LRU is an effective NFS server cache replacement policy and frequency based tend to exhibit erratic behavior in the presence of temporal locality and sequentially accessed files.
Decidability of a class of dual communicating finite state machines
Authors: Mountassir H.
Published: October 2004

A number of techniques have been proposed to validate systems of communicating machines which exchange exclusively messages through FIFO channels. The reachability analysis is a well-known and most popular technique implemented in several tools of validation. Two majors questions are discussed : the finiteness of the reachability graph and the state explosion problem. In this paper we clarify a restricted class of dual machines and its applicability of real protocols. Our investigation at the first time concern sufficient conditions to ensure the finiteness of the reachability graph. In the second part of the paper we confirm the results using the fair reachability analysis in which global states are generated by forcing the two machines in equal speeds.
VP
Authors: Tai K. C. , Carver Richard H.
Published: October 2004

A semaphore is a non-negative integer variable on which only operations P and V are allowed. The semaphore construct (with various extensions) is supported by many operating systems and is often used to implement other synchronization constructs. Since the semaphore construct is low-level, a semaphore-based program may contain synchronization errors that are very difficult to detect. In this paper, we propose a new operation VP (s1,s2), where s1 and s2 are distinct or identical semaphores. An execution of VP(s1,s2) by a process T is equivalent to that of "V (s1); P(s2)" except that when T starts the V (s1) operation, T is guaranteed to be the next process to access s2 (i.e., T will execute the P(s2) operation before another process executes a P(s2) or V(s2) operation.) Section 2 shows several examples to illustrate the advantages of the VP operation. Section 3 concludes this paper. In this paper, we assume that the queue for a semaphore is first-in-first-out and that the order of processes blocked in a semaphore queue is the same order in which they executed P operations on the semaphore. We also assume that the scheduling of processes in a concurrent program is
fair,
i.e., each process ready for execution will eventually be selected as the running process. Programs in this paper use Ada-like syntax.
Towards an active network architecture
Authors: Tennenhouse David L. , Wetherall David J.
Published: October 2004

Active networks allow their users to inject customized programs into the nodes of the network. An extreme case, in which we are most interested, replaces packets with "capsules" - program fragments that are executed at each network router/switch they traverse.Active architectures permit a massive increase in the sophistication of the computation that is performed within the network. They will enable new applications, especially those based on application-specific multicast, information fusion, and other services that leverage network-based computation and storage. Furthermore, they will accelerate the pace of innovation by decoupling network services from the underlying hardware and allowing new services to be loaded into the infrastructure on demand.In this paper, we describe our vision of an active network architecture, outline our approach to its design, and survey the technologies that can be brought to bear on its implementation. We propose that the research community mount a joint effort to develop and deploy a wide area ActiveNet.
A virtual loss-load congestion control strategy for high speed networks
Authors: Prithviraj Narayanan , Williamson Carey L.
Published: October 2004

This paper evaluates a hybrid congestion control strategy called the Virtual Loss-Load model. The approach combines the leaky bucket traffic shaper (a preventive congestion control mechanism) with the loss-load model (a reactive congestion control mechanism). Simulation is used to evaluate the virtual loss-load model, and to compare its performance to that of other reactive congestion control strategies from the literature. The evaluation is done using a benchmark suite of network scenarios proposed by Kanakia, Keshav and Mishra. The performance metrics used in the evaluation are file transfer time and packet loss probability.The simulation results show that the virtual loss-load model is an effective congestion control strategy, providing performance comparable to several other reactive congestion control strategies. While transient effects due to dynamic changes in cross traffic result in significantly higher packet loss than expected in the virtual loss-load model, the parameters of the virtual loss-load model make it directly tunable to trade off packet loss and file transfer time.
Non-repudiation with mandatory proof of receipt
Authors: Coffey Tom , Saidha Puneet
Published: October 2004

Non-repudiation allows an exchange of data between two principals in such a manner that the principals cannot subsequently deny their participation in the exchange. Current non-repudiation schemes, while providing a mandatory
proof of origin
service, generally provide only discretionary
proof of receipt
since it is difficult to enforce the return of the
proof of receipt
by the recipient.In this paper a new scheme for achieving mandatory mutual non-repudiation is proposed, encompassing both mandatory
proof of origin
and mandatory
proof of receipt
. The fundamental feature of the scheme is that the proofs of origin and receipt are not exchanged until both principals have submitted their digitally signed evidence to a trusted third party intermediary. This ensures that if the non-repudiation protocol is not completed, neither principal can gain from the exchange. An added advantage is that the process of dispute arbitration is considerably simplified since a small number of rules are required to decide whether an alleged data exchange took place.
Comparison of Raw and Internet protocols in a HIPPI/ATM/SONET based gigabit network
Authors: Singh Raj K. , Tell Stephen G. , Bharrat Shaun J.
Published: October 2004

We compare implementation of Raw and Internet protocols (TCP, UDP) on a programmable HIPPI host-interface called the Network Interface Unit. The network interface unit connects Pixel-Planes 5, a message-based graphics multicomputer, to a wide area gigabit network called VISTAnet. The BISDN network consists of a SONET cross-connect switch and an ATM switch. We discuss the tradeoffs between protocols for our target application and present a comparison of end-to-end throughput based on empirical measurements.
A language-oriented data modeling approach
Authors: Steinberg Geoffrey , Lin Jicheng
Published: October 2004

This paper presents a fresh data modeling tool: Language-Oriented Data Modeling (LODM). The language used is the English language. After a brief summary of previous research in this field, the paper discusses the theoretical under-pinnings of the LODM approach from the perspectives of both relational theory and linguistic theory. The paper then illustrates the implementation of LODM with a research prototype tool, "Database Designer." Through a step-by-step description of the stages involved in using this new tool, the paper addresses the linguistic and database issues encountered in the process of mapping English sentences into a relational schema. In discussing the robustness of the LODM tool, the paper presents both its strengths and its weakness.
Using predictive prefetching to improve World Wide Web latency
Authors: Padmanabhan Venkata N. , Mogul Jeffrey C.
Published: October 2004

The long-term success of the World Wide Web depends on fast response time. People use the Web to access information from remote sites, but do not like to wait long for their results. The latency of retrieving a Web document depends on several factors such as the network bandwidth, propagation time and the speed of the server and client computers. Although several proposals have been made for reducing this latency, it is difficult to push it to the point where it becomes insignificant.This motivates our work, where we investigate a scheme for reducing the latency perceived by users by predicting and prefetching files that are likely to be requested soon, while the user is browsing through the currently displayed page. In our scheme the server, which gets to see requests from several clients, makes predictions while individual clients initiate prefetching. We evaluate our scheme based on trace-driven simulations of prefetching over both high-bandwidth and low-bandwidth links. Our results indicate that prefetching is quite beneficial in both cases, resulting in a significant reduction in the average access time at the cost of an increase in network traffic by a similar fraction. We expect prefetching to be particularly profitable over non-shared (dialup) links and high-bandwidth, high-latency (satellite) links.
Quantification of quality-of-presentations (QOPs) for multimedia synchronization schemes
Authors: Huang Chung-Ming , Lee Ruey-Yang
Published: October 2004

Storing different numbers of media units in advance can guarantee different levels of synchronization qualities. That is, allocating some buffers at the receive client site can smooth intra/inter asynchrony anomalies, which are the side effects of delay jitters. Additionally, the commencement of a multimedia presentation can be smoothly invoked after a pre-defined number of media units has been stored in each medium stream's buffer. To maintain synchronization qualities, video streams can adopt the non-blocking or the restricted blocking synchronization scheme, and audio streams can adopt the blocking synchronization scheme. In this paper, we derive mathematical relationships among associated parameters such that Quality Of Presentations (QOPs), i.e., intra-medium and inter-media asynchrony anomalies, for live continuous multimedia presentations can be analyzed. Using the mathematical analysis, trade-offs between QOPs and networking/system resources can be identified.
Computational Geometry Column 29
Authors: O'Rourke Joseph
Published: October 2004

Past accomplishments of Computational Geometry are reviewed and future directions adumbrated.
Computational geometry column 28
Authors: O'Rourke Joseph
Published: October 2004

The Web directory of Computational Geometry Software is described.
Finding the
i
th largest of
n
for small
i,n
Authors: Gasarch William , Kelly Wayne , Pugh William
Published: October 2004

A classic problem in computer science is selection: given a list of n numbers, find the ith largest, using the fewest number of comparisons. We are interested in the exact number of comparisons required for specific small values of i and n. We have written a program that can be used either to find the exact number of comparisons for very low values of i and n, or to find upper bounds on the number of comparisons for slightly larger values of i and n. In some cases we have improved on the results in the literature and have additional improvements contingent on a conjecture.
Using formal specifications as test oracles for system-critical software
Authors: Hagar Jon , Bieman James M.
Published: October 2004

The process used to validate, verify, and test flight avionics control systems has produced software that is highly reliable. However, ever greater demands for reliability require new automated tools to improve existing processes. We used the Anna (Annotated Ada) formal specification language and supporting tool set to develop a Test Range Oracle Tool (TROT) to automate the testing of equation execution. Our approach fits within the existing testing process, automates perviously manual analysis, and can increase the level of test coverage. The TROT approach also introduces the use of formal specification languages and supporting tools to an existing industry program. This approach supported production tests and is being expanded into other test support areas.
Comments on the S/KEY user authentication scheme
Authors: Mitchell Chris J. , Chen Liqun
Published: October 2004

We give a critical analysis of the security properties of the S/KEY user authentication system.
Scheduling soft aperiodic tasks in adaptable fixed-priority systems
Authors: Lee Jongwoon , Lee Sungyoung , Kim Hyungill
Published: October 2004

This paper presents a new type of scheduling algorithm for servicing soft deadline aperiodic tasks in adaptable fixed-priority real-time systems. The major goals of our proposed task scheduling are not only to guarantee all the deadlines of periodic tasks and to obtain fast response time for aperiodic tasks, but also to retain considerable scheduling predictability. To achieve these goals, we have adopted a new aperiodic task scheduling principle in which a normal fixed-priority assignment strategy and the information on a preassignment table built off-line are properly mingled somewhat dynamically according to the aperiodic tasks' arrivals at runtime. The paper also shows some simulation results in terms of the average aperiodic response time, verifying that the new algorithm offers significant performance improvements over other conventional joint scheduling algorithms, especially under a heavy transient overload.
A combined-consistency approach
Authors: Cornilleau T. , Gressier-Soudan E.
Published: October 2004

This paper presents a new algorithm that provides two types of consistency models simultaneously on the same data. This algorithm combines sequential and causal consistencies. Two community of sites share the same set of data with different consistency models. This algorithm has been validated by a SPIN/PROMELA simulation. Our proposal addresses uniform memory models based applications. Our work can be applied to passive object, variable or page based environments.
An Ada-based script language for simulation applications
Authors: Abbink H. J.
Published: October 2004

This paper describes SLIS, an Ada-based script language used in the simulations of Fokker's Test Centre. First an overview of the simulation development process, its goals and the resulting requirements for the command interface of simulation modules are presented. Then, the separation of a simulation's internal implementation from the external operator view is discussed. The architecture of SLIS and its interaction with simulation modules is described next. Finally, the script language itself is presented.
Applying object-oriented metrics to Ada 95
Authors: Pritchett William W.
Published: October 2004

Ada 95 adds many new and notable features to the Ada 83 standard. The additions include such aspects as object-oriented programming, hierarchical libraries, and protected objects. The enhancements to the language may have a profound impact on the way developers design software in Ada. Consequently, the way in which the new software designs are assessed needs to be addressed. Recent studies suggest traditional functionally-oriented metrics are not applicable to object-oriented software. As a result, new measures are being proposed that may be applicable to object-oriented design. Some of these metrics have been validated on small to medium sized projects written in C++ and Smalltalk. This paper demonstrates how to apply these metrics to Ada 95.
The future of computational complexity theory: part II
Authors: Allender E. , Feigenbaum J. , Goldsmith J. , Pitassi T. , Rudich S.
Published: October 2004

This is the final part of a 2-part column on the future of computational complexity theory. The grounds rules were that the contributors had no restrictions (except a 1-page limit). For readers interested in more formal reports, in addition to the two URLs mentioned in the previous issue (ftp://ftp.cs.washington.edu/tr/1996/O3/UW-CSE-96-O3-O3.PS.Z and http://theory.lcs.mit.edu/-oded/toc-sp.html) I would also point to the recent "Strategic Directions" report (http://geisel.csl.uiuc.edu/-loui/complete.html).Coming during the next few issues: the search for the perfect theory journal; Thomas Jefferson exposed as a theoretical computer scientist; and Mitsunori Ogihara's survey of DNA-based computation. (The "Lance Fortnow in a clown suit" article promised in the previous column actually ran stand-alone last issue due to scheduling; it probably is still available at a library near you!) Finally, some recent work by Edith Hemaspaandra, Harald Hempel, and myself, and of Buhrman and Fortnow, partially resolves one of the open questions from Complexity Theory Column 11.
Strong password-only authenticated key exchange
Authors: Jablon David P.
Published: October 2004

A new simple password exponential key exchange method (SPEKE) is described. It belongs to an exclusive class of methods which provide authentication and key establishment over an insecure channel using only a small password, without risk of offline dictionary attack. SPEKE and the closely-related Diffie-Hellman Encrypted Key Exchange (DH-EKE) are examined in light of both known and new attacks, along with sufficient preventive constraints. Although SPEKE and DH-EKE are similar, the constraints are different. The class of strong password-only methods is compared to other authentication schemes. Benefits, limitations, and tradeoffs between efficiency and security are discussed. These methods are important for several uses, including replacement of obsolete systems, and building hybrid two-factor systems where independent password-only and key-based methods can survive a single event of either key theft or password compromise.
The impact of a zero-scan Internet checksumming mechanism
Authors: Finn Gregory G. , Hotz Steve , Van Meter Rod
Published: October 2004

This paper describes a "zero-scan" mechanism that reduces Internet checksumming overhead from a per-byte scan (or copy) cost, to a small and constant per-message cost. Unlike previous techniques, this mechanism requires no message buffering within the source. This will allow Internet transport protocols to achieve transfer latencies comparable to specialized protocols implemented directly on high-speed LAN (link-layer) services. In addition, this mechanism is transparent to systems outside of the source LAN. Hence, this mechanism affords applications the portability of Internet protocols without sacrificing the high performance of specialized LAN transport protocols.The proposed zero-scan checksumming scheme eliminates the last requirement for an additional data copy/scan, beyond the scan required to transmit or receive from the network channel. If this checksumming mechanism is combined with zero-copy operating system mechanisms that provide low-overhead transfer across application and kernel boundaries, a network interface architecture that provides separate message buffering is no longer required. A consequence is that the network interface may be reduced, essentially, to DMA engines plus link- and physical-layer logic. Taken one step further, the network interface could be integrated with the CPU to create an "internet microprocessor". These alternative interface designs are discussed, along with their requirements and effects upon operating system and computer system architectures.
Synthesis of communications protocols
Authors: Saleh Kassem
Published: October 2004

Protocol synthesis attempts to formalize and automate the process of designing communications protocols. Protocol design is an important step in the communications software or protocol engineering development process. Protocol synthesis has been addressed extensively by many researchers around the world, and various approaches have been proposed: from the stepwise refinement of a high level requirements specification to the automatic generation starting from a formal service specification. In this paper, we introduce protocol synthesis in the context of the protocol engineering process, and we briefly describe and survey the main features of the proposed synthesis methods. Tables summarizing this survey are also provided.
Object-oriented technology
Authors: Smith H. A. , McKeen J. D.
Published: October 2004

These days, everyone in the Information Systems (IS) world is talking about object-oriented technology --- known as "OO" to its aficionados. The enthusiasm about OO has even reached the mainstream press (Hammonds, 1991) and executives are hearing success stories about dramatic productivity gains and "programming with lego blocks" (Hammonds, 1991). Within IS, some people are talking about an OO "revolution" that will dramatically change how IS does its work and which has the potential to eliminate or significantly reduce IS staffs.All this hype is putting IS managers under pressure to get on the OO bandwagon. Once again, managers are being asked to make critical decisions about an unproven technology. On the one hand, IS is actively looking for new ways of improving its quality and productivity. On the other hand, managers know from bitter experience the problems and costs of introducing a new technology. This paper attempts to look critically, beyond the hype, at the current state of OO technology to identify the issues managers must face in making decisions about using it in their organizations.In order to explore and assess what IS organizations are doing with OO technology, the authors convened a focus group of senior IS managers from ten leading Canadian firms representing five industry sectors: retailing, manufacturing, banking, communications, and insurance. Group members were asked to speak about their current encounters with OO, the benefits and problems they have experienced to date, and other issues they are dealing with surrounding the introduction of OO technology in their organizations. This paper first gives a brief overview of OO technology and its relationship to other IS technologies. It then evaluates the key benefits and problems organizations can expect in introducing and using OO. Finally, it attempts to answer some key questions about how and when to introduce OO in an organization.
Creating and sustaining a business edge using information technology
Authors: Senn James A.
Published: October 2004

Charles Darnell, Executive Vice President with Lithonia Lighting, coordinates all company operations in support of customer service. He is known around the world for the innovative and effective deployment of information technology. Darnell is a winner, along with Lithonia's CEO Jim McClung, of the prestigious "Partners in Leadership Award" presented by the Society for Information Management. The award is presented annually to the CEO/CIO partnership that has done the most to use information technology to carry out the company's business strategy.In this candid and hard-hitting interview, Darnell shares his insights and his experiences gained over the 32 years he has been with the company. You'll see the thinking he has used to create the ongoing series of innovations that have led to and sustained a family of worldclass systems.
Operating system design: towards a holistic approach?
Authors: Nicol John R , Blair Gordon S , Walpole Jonathan
Published: October 2004

Recent years have marked the beginning of a new era for operating systems. Distributed computing is clearly one dimension of this. We argue that qualitative issues add a second major dimension. These changes will have a profound effect on operating system design. In this short paper, we present a personal view of what the response to these changes should be. The argument is supported by our experiences in the design of the Cosmos distributed operating system.
Memory management units for microcomputer operating systems
Authors: Rattan I
Published: October 2004

Recently, independent memory management units for microprocessor based systems have become available. This note summarizes the features of register and tree memory management units (using MC68451 & MC68851 as examples) from a viewpoint of microcomputer operating systems design.
Some thoughts on the packet network architecture
Authors: Zhang Lixia
Published: October 2004

Performance control in packet switching networks is one of the remaining areas that are yet to be explored. In this paper we look into the performance problems with two existing network architectures, datagram and virtual circuit. The major problem with the datagram network is lack of effective traffic control; and with the virtual circuit network, the improperly defined network control semantics and mechanisms. We consider that a new network architecture should be investigated in order to provide performance support for diverse applications.
The Burroughs integrated adaptive routing system (BIAS
TM
)
Authors: Gruchevsky S , Piscitello D
Published: October 2004

The routing function used for Burroughs Network Architecture (BNA) to determine the best routes for traffic through the network is known as the BURROUGHS INTEGRATED ADAPTIVE ROUTING SYSTEM, or BIAS™.Based on the algorithm devised for the MERIT Computer Network [3], BIAS™ is a decentralized, deterministic system which adapts to changes in network topology automatically. The current BIAS™ routing architecture incorporates improvements in the original algorithm [1] which significantly reduce the recovery time from failures of network elements and is virtually loop-free, even during recovery from those failures.BIAS™ automatically responds to the following changes to the network topology:- a node (an end system or intermediate system) is added to the network;- a node is removed from the network;- the cost of transiting a node is changed;- a logical link (LAN, leased or switched circuit, X.25 virtual circuit) is added to the network;- a link is removed from the network; and/or- the cost of transiting a link is changed;and re-determines the best route for all traffic throughout the network.
OSI service specification: SAP and CEP modelling
Authors: Tomas JG , Pavon J , Pereda O
Published: October 2004

Within the effort of ISO standarization, service specifications have been thought to be an important tool for formal verification of protocols. The paper discusses the modelling of some concepts quite related with the service: service access points and abstract service primitives. Firstly, ISO concepts are explained. Then, a service architectural model is developed as a refinament of the service access point idea using the connection end point concept. A finite state machine approach is shown to specify the behavior of the modules of such architecture. This lead us to consider the service access point represented as a single state automaton that consists of several connection end point automata. Thus, service access points allow the specification of services, and provide an abstraction of interfaces between adjacent layers of the Open System Interconnection model of ISO.
An assessment of the overhead associated with tasking facilities and task paradigms in Ada
Authors: Burger T M , Nielsen K W
Published: October 2004

The design of real-time systems with Ada requires consideration of design alternatives related to the use of tasks for buffering, creation of tasks with allocators, exception handling, and other factors. This paper describes an assessment made of the overhead associated with Ada tasking facilities and tasking paradigms commonly used in real-time design. The tasking facilities examined included task communication and synchronization, task activation and termination, creating tasks via allocators, and exception handling. The tasking paradigms measured focused on the degree of uncoupling required between a producer and consumer, using intermediary tasks. The timing measurements used in the assessment were obtained with DEC Ada (version 1.2) on a VAX 8600.
Fixed-point conversion, multiplication, and division in Ada
Authors: Froggatt T
Published: October 2004

This paper briefly describes classical fixed-point working, then turns to the facilities offered by the Ada language. It argues that the default-power-of-two scaling coupled with the optionalness of 'small representation specifications have effectively rendered Ada's fixed-point facilities impotent; but that a full implementation would provide an appropriate level of functionality.Ada's accuracy requirements lead to a high run-time cost for certain fixed-point operations; but it is shown that the existence of "perfect" scaling factors, calculated by the ancient method of continued fractions, ensures that this cost it at least bounded. Proposals are made to reduce this cost without impact upon existing Ada users.
Ada language training with a COBOL translation model
Authors: Arnett K A , Butler C M
Published: October 2004

The use of Ada outside of its original embedded systems area seems a certainty. Training Ada programmers is a key concern of those involved in the Ada effort, and there is much concern over professionalism of Ada programmers. While this paper does not suggest that elementary Ada training is sufficient for trained programmers with other language skills, it presents the results of an experiment focused towards providing elementary Ada language training for COBOL programmers. The results demonstrated that participants training with a computer model can learn the same amount of material as textbook trained participants in much less time.
Experiences in using Ada with DBMS applications
Authors: McNickle M , Reedy A
Published: October 2004

This paper presents an overview of work performed between July, 1984 and February, 1986. A prototype effort consisting of the redesign and reimplementation of COBOL programs into Ada has been completed successfully. The redesign and reimplementation of a DBMS applications system under full military life cycle standards is still underway. An important feature of this work is that it demonstrates a transition path for large CODASYL database systems away from COBOL and into Ada. The more important lessons learned and recommendations for future work are summarized. This work was partially funded by U. S. Navy SPAWARSYSCOM under contracts N00039-81-C-0119 and N68786-85-C3010.
Information system technology can improve customer service
Authors: Learmonth Gerard P
Published: October 2004

Creative deployment of information system technologies can lead to new ways to differentiate products and services through customer service, while simultaneously strengthening customer ties.
Educating the CBIS user: a case analysis
Authors: Nelson R Ryan , Cheney Paul H
Published: October 2004

Deficiencies in computer-related education for end users have contributed to the lack of successful integration of computer-based information systems (CBIS) into organizations. Data gathered from 20 companies whose CBIS exert a high strategic impact on existing operating systems were studied to determine how these companies accomplished "education integration." About 80% of the companies reported training budgets between zero and two percent of the CBIS budget, with a majority of the participants reported training staffs consisting of two or less full time trainers. Of the seven educational techniques used by the companies, the Resident Expert technique rated superior in terms of quantity and quality. A description of the activities in four companies with unique approaches to the education of their user community provides additional insights into the role of organizations in promoting the integration and use of CBIS among end users.
Assessment of an effort to integrate computer functions in an engineering design firm
Authors: Morell Jonathan A , Leemon James
Published: October 2004

This study is an assessment of a large engineering design firm's efforts to integrate diverse elements of computer use. The integration effort had two elements: the implementation of workstations capable of integrating project management, analysis, text production and graphics production, and a communication function that allowed system users to access both each others' work and data stored in a variety of other computer systems. Methods used were questionnaires and in-depth interviews. Three basic issues were studied: differential affects of the system on professional and clerical workers, impact of the system on document production, and effects the system had on the nature of work in the organization. Observed changes included better document production, growing reliance on the system, and higher productivity. People did either more of the type of work they did prior to using the system, or the same amount of work but better. There was also an indication that some users were able to do tasks they previously sent to others. Explanations are proposed as to why two other effects were not detected-differential impacts on professional and clerical workers, and a shift in the nature of work in the organization.
The importance of long-range dependence of VBR video traffic in ATM traffic engineering
Authors: Ryu Bong K. , Elwalid Anwar
Published: October 2004

There has been a growing concern about the potential impact of long-term correlations (second-order statistic) in variable-bit-rate (VBR) video traffic on ATM buffer dimensioning. Previous studies have shown that video traffic exhibits long-range dependence (LRD) (Hurst parameter large than 0.5). We investigate the practical implications of LRD in the context of
realistic
ATM traffic engineering by studying ATM multiplexers of VBR video sources over a range of desirable cell loss rates and buffer sizes (maximum delays). Using results based on large deviations theory, we introduce the notion of
Critical Time Scale
(CTS). For a given buffer size, link capacity, and the marginal distribution of frame size, the CTS of a VBR video source is defined as the number of frame correlations that contribute to the cell loss rate. In other words, second-order behavior at the time scale beyond the CTS does not significantly affect the network performance. We show that whether the video source model is Markov or has LRD, its CTS is finite, attains a small value for small buffer, and is a non-decreasing function of buffer size. Numerical results show that (i)
even in the presence of LRD
, long-term correlations do not have significant impact on the cell loss rate; and (ii) short-term correlations have dominant effect on cell loss rate, and therefore, well-designed Markov traffic models are effective for predicting Quality of Service (QOS) of LRD VBR video traffic. Therefore, we conclude that it is unnecessary to capture the long-term correlations of a real-time VBR video source under
realistic
ATM buffer dimensioning scenarios as far as the cell loss rates and maximum buffer delays are concerned.
On the relevance of long-range dependence in network traffic
Authors: Grossglauser M. , Bolot J.-C.
Published: October 2004

There is mounting experimental evidence that network traffic processes exhibit ubiquitous properties of self-similarity and long range dependence (LRD), i.e. of correlations over a wide range of time scales. However, there is still considerable debate about how to model such processes and about their impact on network and application performance. In this paper, we argue that much recent modeling work has failed to consider the impact of two important parameters, namely the finite range of time scales of interest in performance evaluation and prediction problems, and the first-order statistics such as the marginal distribution of the process.We introduce and evaluate a model in which these parameters can be easily controlled. Specifically, our model is a modulated fluid traffic model in which the correlation function of the fluid rate is asymptotically second-order self-similar with given Hurst parameter, then drops to zero at a cutoff time lag. We develop a very efficient numerical procedure to evaluate the performance of the single server queue fed with the above fluid input process. We use this procedure to examine the fluid loss rate for a wide range of marginal distributions, Hurst parameters, cutoff lags, and buffer sizes.Our main results are as follows. First, we find that the amount of correlation that needs to be taken into account for performance evaluation depends not only on the correlation structure of the source traffic, but also on time scales specific to the system under study. For example, the time scale associated to a queueing system is a function of the maximum buffer size. Thus for finite buffer queues, we find that the impact on loss of the correlation in the arrival process becomes nil beyond a time scale we refer to as the correlation horizon. Second, we find that loss depends in a crucial way on the marginal distribution of the fluid rate process. Third, our results suggest that reducing loss by buffering is hard. We advocate the use of source traffic control and statistical multiplexing instead.
Generating efficient protocol code from an abstract specification
Authors: Dabbous Walid , O'Malley Sean , Castelluccia Claude
Published: October 2004

A protocol compiler takes as input an abstract specification of a protocol and generates an implementation of that protocol. Protocol compilers usually produce inefficient code both in terms of code speed and code size. In this paper, we show that the combination of two techniques makes it possible to build protocol compilers that generate efficient code. These techniques are i) the use of a compiler that generates from the specification a unique tree-shaped automaton (rather than multiple independent automata), and ii) the use of optimization techniques applied at the automaton level, i.e. on the branches of the trees.We have developed a protocol compiler that uses both these techniques. The compiler takes as input a protocol specification written in the synchronous language Esterel. The specification is compiled into a unique automaton by the Esterel front end compiler. The automaton is then optimized and converted into
C
code by our protocol optimizer called HIPPCO. HIPPCO improves code performance and reduces code size by simultaneously optimizing the performance of the common path and optimizing the size of the uncommon path. We evaluate the gain expected with our approach on a real-life example, namely a working subset of the TCP protocol generated from an Esterel specification. We compare the protocol code generated with our approach to that derived from the standard BSD TCP implementation. The results are very encouraging. HIPPCO-generated code executes up to 25 % fewer instructions than the BSD code for input packet processing while maintaining comparable code size.
A reliable and scalable striping protocol
Authors: Adiseshu Hari , Parulkar Guru , Varghese George
Published: October 2004

Link striping algorithms are often used to overcome transmission bottlenecks in computer networks. Traditional striping algorithms suffer from two major disadvantages. They provide inadequate load sharing in the presence of variable length packets, and may result in non-
FIFO
delivery of data. We describe a new family of link striping algorithms that solves both problems. Our scheme applies to any layer that can provide multiple
FIFO
channels.We deal with variable sized packets by showing how fair queuing algorithms can be transformed into load sharing algorithms. Our transformation results in practical load sharing protocols, and shows a theoretical connection between two seemingly different problems. The same transformation can be applied to obtain load sharing protocols for links with different capacities. We deal with the
FIFO
requirement for two separate cases. If a sequence number can be added to each packet, we show how to speed up packet processing by letting the receiver simulate the sender algorithm. If no header can be added, we show how to provide quasi-
FIFO
delivery. Quasi-
FIFO
is
FIFO
except during occasional periods of loss of synchronization. We argue that quasi-
FIFO
is adequate for most applications. We also describe a simple technique for speedy restoration of synchronization in the event of loss.We develop an architectural framework for transparently embedding our protocol at the network level by striping IP packets across multiple physical interfaces. The resulting
strIPe
protocol has been implemented within the NetBSD kernel. Our measurements and simulations show that the protocol offers scalable throughput even when striping is done over dissimilar links, and that the protocol synchronizes quickly after packet loss. Measurements show performance improvements over conventional round robin striping schemes and striping schemes that do not resequence packets.
Hierarchical packet fair queueing algorithms
Authors: Bennett Jon C. R. , Zhang Hui
Published: October 2004

Hierarchical Packet Fair Queueing (H-PFQ) algorithms have the potential to simultaneously support guaranteed real-time service, rate-adaptive best-effort, and controlled link-sharing service. In this paper, we design practical H-PFQ algorithms by using one-level Packet Fair Queueing (PFQ) servers as basic building blocks, and develop techniques to analyze delay and fairness properties of the resulted H-PFQ servers. We demonstrate that, in order to provide tight delay bounds in a H-PFQ server, it is essential for the one-level PFQ servers to have small Worst-case Fair Indices (WFI). We propose a new one-level PFQ algorithm called WF
2
Q+ that is the first to have all the following three properties: (a) providing the tightest delay bound among all PFQ algorithms; (b) having the smallest WFI among all PFQ algorithms; and (c) having a relatively low implementation complexity of O(log N). We show that practical H-PFQ algorithms can be implemented by using WF
2
Q+ as the basic building block and prove that the resulting H-WF
2
Q+ algorithms provide similar delay bounds and bandwidth distribution as those provided by a H-GPS server. Simulation experiments are presented to evaluate the proposed algorithm.
Start-time fair queueing
Authors: Goyal Pawan , Vin Harrick M. , Chen Haichen
Published: October 2004

We present Start-time Fair Queuing (SFQ) algorithm that is computationally efficient, achieves fairness regardless of variation in a server capacity, and has the smallest fairness measure among all known fair scheduling algorithms. We analyze its throughput, single server delay, and end-to-end delay guarantee for variable rate Fluctuation Constrained (FC) and Exponentially Bounded Fluctuation (EBF) servers. We show that SFQ is better suited than Weighted Fair Queuing for integrated services networks and it is strictly better than Self Clocked Fair Queuing. To support heterogeneous services and multiple protocol families in integrated services networks, we present a hierarchical SFQ scheduler and derive its performance bounds. Our analysis demonstrates that SFQ is suitable for integrated services networks since it: (1) achieves low average as well as maximum delay for low-throughput applications (e.g., interactive audio, telnet, etc.); (2) provides fairness which is desirable for VBR video; (3) provides fairness, regardless of variation in a server capacity, for throughput-intensive, flow-controlled data applications; (4) enables hierarchical link sharing which is desirable for managing heterogeneity; and (5) is computationally efficient.
Routing high-bandwidth traffic in max-min fair share networks
Authors: Ma Qingming , Steenkiste Peter , Zhang Hui
Published: October 2004

We study how to improve the throughput of high-bandwidth traffic such as large file transfers in a network where resources are fairly shared among connections. While it is possible to devise priority or reservation-based schemes that give high-bandwidth traffic preferential treatment at the expense of other connections, we focus on the use of routing algorithms that improve resource allocation while maintaining max-min fair share semantics. In our approach, routing is closely coupled with congestion control in the sense that congestion information, such as the rates allocated to existing connections, is used by the routing algorithm. To reduce the amount of routing information that must be distributed, an abstraction of the congestion information is introduced. Using an extensive set of simulation, we identify a link-cost or cost metric for "shortest-path" routing that performs uniformly better than the minimal-hop routing and shortest-widest path routing algorithms. To further improve throughput without reducing the fair share of single-path connections, we propose a novel prioritized multi-path routing algorithm in which low priority paths share the bandwidth left unused by higher priority paths. This leads to a conservative extension of max-min fairness called prioritized multi-level max-min fairness. Simulation results confirm the advantages of our multi-path routing algorithm.