bluuebunny/crossref_metadata_2025 huggingface dataset:
IT companies' acceptance of and attitudes towards Ada
Authors: Rogers Mike W.
Published: October 2004

A survey was carried out to establish the Ada countries' knowledge about itself and the market potential of the work they were engaged in. Some 62 organisations responses were received (25%) from 10 countries. Though many are well informed, the effect of distance in such a dispersed effort weakens actions. Ada Europe plays a crucial role in this, outside of the large SIG Ada organisation. The delay in validated compilers of up to two years should be removed largely by the end of 1985, with Europe notifying a higher proportion of proposed validations than to date. Average budget overruns over 50% indicate severe difficulties in implementations, but a wider range of problems were noted than just tasking and generics and highly correlated with lack of comprehension. The early indications of the adoption of SE methodology by the Ada implementors indicate a desire to have a realistic set of functionalities in an APSE. Until some of these are provided, state of the art in SEM will not advance via Ada. The markets for Ada are impossible to assess accurately. Companies who have market studies do not release them, many more feel the word "military" is sufficient. Figures available show that relative to expectations of 1982/83, Ada penetration in 1985 is far below expectations. A sizeable public and private sector is emerging, not hampered by the side issue of validation and clamouring for more intelligence from what is seen as a "closed" military activity.
Highly parallel Ada—Ada on an ultracomputer
Authors: Schonberg Edith , Schonberg Edmond
Published: October 2004

We examine the suitability of Ada to a specific multiprocessor architecture, the NYU Ultracomputer. The Ultracomputer is an MIMD machine with shared memory, and a special hardware primitive, the
fetch-and-add
operation, with which non-blocking versions of well-known synchronization primitives can be implemented. We show that fetch-and-add can be used to implement some common Ada tasking idioms, and that well-known algorithms for MIMD machines find a natural description in Ada. Furthermore, Ada solutions implemented with fetch-and-add have fewer and smaller critical sections than previously presented versions. The fetch-and-add primitive also provides an efficient solution to the problem of initializing a number of identical tasks, and to the potentially expensive implementation of termination for large numbers of tasks. We conclude that the Ada tasking model "fits" well an MIMD architecture such as the Ultracomputer.
An event-driven debugger for Ada
Authors: Mauger Claude , Pammett Kevin
Published: October 2004

In this paper, we present the main concepts used in our symbolic debugger for Ada. Described also is a companion tool, the Ada Program VIEWer, which gives users full access to program source while debugging. This debugger is one of the components of the Alsys Tool set which aims at providing high-level Ada-oriented tools, incorporting state-of-the-art techniques for software design, documentation, and development.
The efficiency of storage management schemes for Ada programs
Authors: Gupta Rajiv , Soffa Mary Lou
Published: October 2004

The efficient implementation of high level languages which support concurrency is imperative, particularly in such application areas as embedded real-time systems. Various storage management schemes have been proposed for the implementation concurrency. In this work, a methodology is presented for evaluating the performance of these schemes including the standard heap, Berry-heap, cactus stack and quantized heap when used for Ada programs. The methodology involves the generation of workload traces from an executing program and the use of simulators of the alternative storage management schemes to produce measures of the performances of the schemes. The performance evaluation metrics used are space, time and the space-time product.
An overview and example of application of CAEDE
Authors: Buhr R. J. A. , Karam G. M. , Woodside C. M.
Published: October 2004

CAEDE is an experimental, integrated, iconic design environment which supports (1) a structured design methodology based on Buhr's
System Design With Ada
book (2) an iconic design entry system, (3) a design data base, and (4) design tools. The design data base is automatically represented in Prolog and the majority of the design tools are written in Prolog. Tools are currently available for structural and temporal analysis, and for source code generation. This paper describes both the ideas behind CAEDE and an example of a CAEDE tools written in Prolog for representing and analyzing the temporal behaviour of Ada tasking designs, without having to program them in Ada first.
Developing an automated Ada training product
Authors: Beretz Rene , Brosgol Benjamin M.
Published: October 2004

The emergence of Ada as a major programming language, and the resulting need for training large numbers of programmers in Ada, has led to the development of a variety of educational products and techniques. These include live courses and seminars, textbooks, videotaped instruction, and Computer-Based Training ("CBT"). In this paper we describe the major technical decisions and Ada educational approach that shaped the design of a particular CBT product developed by Alsys -- LESSONS ON ADA. We present the reasons behind the decisions, give an example from one of the lessons that illustrates the educational approach, and summarize future directions for the product.
TSL
Authors: Helmbold David , Luckham David
Published: October 2004

TSL is a language for specifying sequences of tasking events in Ada
1
programs. TSL specifications are submitted with an Ada program and are monitored at runtime for consistency with the actual tasking events as they occur. This paper presents a preliminary design for TSL, an informal overview of its capabilities, and an operational semantics.
Automatic language conversion and its place in the transition to Ada
Authors: Wallis P. J. L.
Published: October 2004

A number of systems for the automatic conversion to Ada of software written in other languages have been specified or implemented, but such systems are of limited usefulness in planned programmes for the transition to Ada. Managerial and technical implications of the availability of automatic converters for planned transitions to Ada are separately discussed.
An implementation of Anna
Authors: Sankar Sriram , Rosenblum David , Neff Randall
Published: October 2004

Anna is a language extension of Ada to include facilities for formally specifying the intended behavior of Ada programs. It augments Ada with precise machine-processable annotations so that well established formal methods of specification and documentation can be applied to Ada programs.This paper describes an implementation of a subset of Anna. The implementation is a transformer that accepts as input an Anna parse tree and produces as output an equivalent Ada parse tree that contains the necessary executable runtime checks for the Anna specifications. An approach called the
Checking Function Approach
is used. This involves the generation of a function for each annotation and generating calls to these functions at appropriate places. The transformer has to take care of various details like hiding, overloading, nesting, etc.It is hoped that the transformer will eventually cover most of Ann and have various features like a good user interface, interaction with a symbolic debugger, and optimization of runtime checks for permanent inclusion.
Ada in the ECLIPLSE project support environment
Authors: Pierce R. H.
Published: October 2004

This paper outlines the object management system provided in the ECLIPSE project support environment and describes how Ada compilers are supported by this system. The structure of a common Ada program library is described and the support tools provided with it.
Decidability of bisimulation equivalence for normed pushdown processes
Authors: Stirling Colin
Published: October 2004

As a service to our readers,
SIGACT News
has an agreement with
Computing Reviews
to reprint reviews of books and articles of interest to the theoretical computer science community.
Computing Reviews
is a monthly journal that publishes critical reviews on a broad range of computing subjects, including models of computation, formal languages, computational complexity theory, analysis of algorithms, and logics and semantics of programs. ACM members can receive a subscription to
Computing Reviews
for $45 per year by writing to ACM headquarters.
Classical versus quantum communication complexity
Authors: Ta-Shma Amnon
Published: October 2004

Classical communication complexity has been intensively studied since its conception two decades ago. Recently, its quantum analogue, the quantum communication complexity model, was defined and studied. In this paper we present some of the main results in the area.
An approach to the formal verification of the two-party cryptographic protocols
Authors: Zhang Yuqing , Li Jihong , Xiao Guozhen
Published: October 2004

A general method, which can be used to verify the two-party cryptographic protocols, is present in this paper. Our approach makes use of running modes of the two-party cryptographic protocols to analyze the protocols. Based on this method, the verification of the protocols becomes independent of model checking tools. Finally, this approach is illustrated with an example on the Needham-Schroeder public-key protocol.
A formal method to prove ordering properties of multicast systems
Authors: Toinard C. , Florin G. , Carrez C.
Published: October 2004

We consider three kinds of ordering properties provided by a multicast system. The messages can be delivered to the different recipients according to a local order, a causal order or a total order. In this paper, a formal method is proposed to prove the total and causal order of multicast protocols. A generalized formal result for multicast protocols is obtained. Some addressing features for other formal results are considered. This study allows to prove that existing systems have the required property. The results can be used to define new solutions. Moreover, the method makes use of various ordering properties, well fitted to practical systems, to achieve a better understanding of the ordering processing.
Replica management in real-time Ada 95 applications
Authors: Pinho Luís Miguel , Vasques Francisco
Published: October 2004

In this paper, we present some of the fault tolerance management mechanisms being implemented in the Multi-μ- architecture, namely its support for replica non-determinism. In this architecture, fault tolerance is achieved by node active replication, with software based replica management and fault tolerance transparent algorithms. A software layer implemented between the application and the real-time kernel, the Fault Tolerance Manager (FTManager), is the responsible for the transparent incorporation of the fault tolerance mechanismsThe active replication model can be implemented either imposing replica determinism or keeping replica consistency at critical points, by means of interactive agreement mechanisms. One of the Multi-μ architecture goals is to identify such critical points, relieving the underlying system from performing the interactive agreement in every Ada dispatching point.
Extendable, dispatchable task communication mechanisms
Authors: Michell Stephen , Lundqvist Kristina
Published: October 2004

The addition of object-oriented features to Ada has left a disconnection between the object-oriented paradigm and the intertask communication and synchronisation paradigms. The lack of extensibility of tasks and protected types as well as the task synchronisation inheritance anomaly has made design of systems that use them with object oriented features more difficult. This paper proposes Ada language changes that would make protected types and tasks partners in object oriented programming and would cure the inheritance anomaly.
An experimental testbed for embedded real time Ada 95
Authors: Walker W. M. , Woolley P. T. , Burns A.
Published: October 2004

The modifications made to Ada during the 9X process have resulted in a language that is ideally suited to programming real-time systems. In this paper we investigate the difficulties in realising this potential. In particular, we consider the issues raised when porting the public GNAT system on to a bare processor and producing a predictable and effective run-time system. As we were also concerned with issues of distribution via a CAN broadcast bus, support for the CAN protocol was included in the run-time system. In addition to investigating the performance of real-time Ada 95 applications we were also interested in more general issues associated with embedded kernel support for Ada 95. To facilitate these investigations and obtain the required level of performance, the thread package via which GNAT implement various aspects of the Ada language has been re-implemented. We discuss the architecture selected for this embedded kernel implementation and its relation to the architecture of the GNAT compiler.
Distributed programming with intermediate IDL
Authors: Smith Gary W. , Volz Richard A.
Published: October 2004

Several heterogeneous-language distributed programming systems have been developed which either use an explicit Interface Definition Language (IDL) for the specification of distributed objects or which directly translate server language specifications to corresponding client language representations. In this paper, we present a new approach which combines the advantages of these prior systems. Our approach uses an IDL as an implicit intermediate step in the translation from server to client language rather than as an explicit user-provided definition.
Data management issues for large scale, distributed workflow systems on the Internet
Authors: Zhao J. Leon , Kumar Akhil
Published: October 2004

The Internet is providing worldwide connectivity for business organizations and has created a much greater opportunity for people to collaborate remotely in an automated workflow setting. However, the speed of delivery of workflow data on the Internet can be unpredictable due to variability in traffic and limited bandwidth. Further, the issue of data management becomes more complex when the system consists of various clients with different system and networking settings. In this paper, we investigate several data management problems in distributed workflow management on the Internet and propose solutions for improving workflow efficiency. More specifically, we explore research issues with respect to system architectures and various data delivery techniques. Our study indicates that it is possible to improve performance considerably by selecting the right combinations of data delivery techniques and system characteristics.
APSARA
Authors: Purao Sandeep
Published: October 2004

Although a number of libraries of patterns have been developed for reuse, there is no mechanism for supporting automated design of object-oriented systems by the intelligent reuse of patterns from such libraries. We describe a web-based system, APSARA, the purpose of which is to create object-oriented designs based upon simple requirements descriptions. The system, developed in Java, implements a pattern retrieval and synthesis methodology that uses natural language processing and automated reasoning heuristics. The system is tested on multiple cases from different domains. The results are reported using metrics defined in the spirit of familiar measures such as recall, precision, coverage and spuriousness. These initial tests suggest that this is a feasible approach for the reuse of patterns in object-oriented design. The testing also reveals specific areas of concern and suggests a number of avenues for extending this research.
To Ada or not to Ada
Authors: Pinho Luís Miguel , Vasques Francisco
Published: October 2004

Ada is really an unfortunate Lady. After years fighting against C/C++ villains, her major lift-up (Ada 95) had brought up a promise of fortune. However, a new strong villain (Java) has appeared trying to end her struggle for survival.Ada has now to fight with her own weapons. She will only prosper by her own merits. But two questions emerge. Do they exist? Are they better than Java's? Our opinion is that they do exist, and are not matched by any other programming language.
Resource view theory analysis of SAP as a source of competitive advantage for firms
Authors: Pereira Rex Eugene
Published: October 2004

This paper uses resource view theory to determine the means by which SAP technology could provide a sustainable competitive advantage to firms which have successfully implemented the SAP system. Resource view theory suggests that resources which are durable, not easily replicable, and imperfectly mobile can be effectively leveraged by the firm in order to achieve a sustainable competitive advantage over its competitors.The analysis which is presented in this paper suggests that the effective implementation of the SAP system by a firm requires not only an acquisition of a high level of technical expertise, but a change in organizational culture from one which rewards individual brilliance to one which encourages project teams. This will create an environment in which the success of any individual in his job is critically dependent on the skills possessed by the other team members. This will render the human component of the SAP resource imperfectly mobile and increase the capability of the firm to leverage this resource in order to achieve a sustainable competitive advantage.A second prescription which emerges from the analysis is that it is preferable to modify the business processes of the organization to fit the capabilities provided by the SAP system, rather than modify the SAP system to fit the reengineered business processes of the organization.
Application of intelligent agent technology for managerial data analysis and mining
Authors: Bose Ranjit , Sugumaran Vijayan
Published: October 2004

Data analysis and mining technologies help bring business intelligence into organizational decision support systems (DSS). While a myriad of data analysis and mining technologies are commercially available today, organizations are seeing a growing gap between powerful storage (data warehouse) systems and the business users' ability to analyze and act effectively on the information they contain. We contend that to narrow this gap effectively, a data analysis and mining environment is needed that can bring together and make available for use many of these technologies, that can support business users with different backgrounds, and with which the users can work comfortably.This paper illustrates the design and construction of such an environment, called the Intelligent Data Miner. IDM is Web-based and it is intended to provide an organization-wide decision support capability for business users. Intelligent agent technology is used as the basis for IDM design. IDM provides several types of data access capabilities to access and analyze the data contained in a data warehouse to obtain the critical information needed by business decision-makers. It supports both predefined and ad hoc data access, data analysis, data presentation, and data mining requests from non-technical users.An operational prototype of IDM, implemented using Java and JATLite (Java Agent Template, Lite from Stanford University), allowed us to examine the feasibility of having the "agents" automatically control and coordinate activities and tasks on the business users' behalf. These agents proved to hide the complexity of data analysis and mining activities, techniques, and methods from the business users, for effective use of the warehouse data.
A test of task-technology fit theory for group support systems
Authors: Zigurs Ilze , Buckland Bonnie K. , Connolly James R. , Wilson E. Vance
Published: October 2004

Group support systems (GSS) provide both promise and puzzlement. Experimental studies of different systems over the years have resulted in conflicting findings --- sometimes enhancing group performance, at other times having no effect, and occasionally even resulting in worse performance for GSS-supported groups than for traditional groups. Researchers have speculated that the mixed results are due to a poor fit of the GSS with the group's task. A recent model of task-technology fit has provided a theoretical perspective from which to test this issue. In this paper, a theory of task-technology fit is tested by applying it to a selected set of published GSS experiments. Key constructs in the theory are operationalized via coding instruments, and the application of the coding scheme provides support for the theory.
The relation of agenda creation and use to group support system experience
Authors: Niederman Fred , Volkema Roger J.
Published: October 2004

The meeting agenda is often recommended as a critical element for conducting successful meetings. However, assertions about the value of meeting agendas are rarely explained or empirically tested. This study surveyed 238 group facilitators, including 113 who reported facilitating at least one meeting using group support systems (GSS), to examine their views on the use of agendas in meetings.Analyses are based on overall responses by group facilitators and by responses of the subset of facilitators who have used GSS. In addition, correlation analyses between the amount of GSS experience and the responses of the full group of facilitators and the subset with GSS experience are reported. Frequency of agenda use and of evaluation of the "goodness of the agenda" both correlated with GSS experience. Pre-meeting sessions with the group sponsors correlated significantly with GSS experience as did the frequency of varying from the agenda. Finally, quality of meeting deliverables, satisfaction with outcomes, and satisfaction with process were viewed as most important benefits of using an agenda; but they did not correlate with GSS experience. Meeting efficiency as a benefit of agenda use was negatively correlated with GSS experience. The implications of these findings for GSS facilitation and for future research are discussed.
The facilitators perspective on meetings and implications for group support systems design
Authors: Hayne Stephen C.
Published: October 2004

Based on research into group process facilitation, a meeting model is proposed that defines the many activities comprising group work and highlights the critical facilitator actions. Facilitating group work is a dynamic process that involves managing relationships among people, tasks and technology, as well as structuring the interactions contributing to an effective meeting. By examining existing group support systems (GSS), it is shown that assistance for facilitation is low. With this information, methods are proposed to improve facilitation support (and therefore the meeting process) in GSS for face-to-face or dispersed environments.
Analysis of optimal thread pool size
Authors: Ling Yibei , Mullen Tracy , Lin Xiaola
Published: October 2004

The success of e-commerce, messaging middleware, and other Internet-based applications depends in part on the ability of network servers to respond in a timely and reliable manner to simultaneous service requests. Multithreaded systems, due to their efficient use of system resources and the popularity of shared-memory multi-processor architectures, have become the server implementation of choice. However, creating and destroying a thread is far from free, requiring run-time memory allocation and deallocation. These overheads become especially onerous during periods of high load and can be a major factor behind system slowdowns. A thread-pool architecture addresses this problem by prespawning and then managing a pool of threads. Threads in the pool are reused, so that thread creation and destruction overheads are incurred only once per thread, and not once per request. However, efficient thread management for a given system load highly depends on the thread pool size, which is currently determined heuristically. In this paper, we characterize several system resource costs associated with thread pool size. If the thread pool is too large, and threads go unused, then processing and memory resources are wasted maintaining the thread pool. If the thread pool is too small, then additional threads must be created and destroyed on the fly to handle new requests. We analytically determine the optimal thread pool size to maximize the expected gain of using a thread.
Runtime incremental concentrated scheduling on NOW(NRICS)
Authors: Ximing Chen , Xianliang Lu
Published: October 2004

Runtime Incremental Concentrated Scheduling on NOW(NRICS) is an important task scheduling and load balancing strategy on Network of Workstations(NOW), it divides the whole NOW system into two types of alternative phases: a system scheduling phase and an underlying system executing phase. It has four important features: runtime scheduling, incremental scheduling, concentrated scheduling and exchanging load among nodes parallelly. With this strategy, the load imbalance in one system executing phase can be improved and corrected in the next system scheduling phase, and so make all nodes' load continuously trend to balance. NRICS has good performance of parallel computing, load balancing, and scalability, it is an ideal task scheduling and load balancing strategy in a parallel computing environment based on NOW.
Endpoint admission control
Authors: Breslau Lee , Knightly Edward W. , Shenker Scott , Stoica Ion , Zhang Hui
Published: October 2004

The traditional approach to implementing admission control, as exemplified by the Integrated Services proposal in the IETF, uses a signalling protocol to establish reservations at all routers along the path. While providing excellent quality-of-service, this approach has limited scalability because it requires routers to keep per-flow state and to process per-flow reservation messages. In an attempt to implement admission control without these scalability problems, several recent papers have proposed various forms of
endpoint admission control
. In these designs, the hosts (the endpoints) probe the network to detect the level of congestion; the host admits the flow only if the detected level of congestion is sufficiently low. This paper is devoted to the study of endpoint admission control. We first consider several architectural issues that guide (and constrain) the design of such systems. We then use simulations to evaluate the performance of endpoint admission control in various settings. The modest performance degradation between traditional router-based admission control and endpoint admission control suggests that a real-time service based on endpoint probing may be viable.
Critical path analysis of TCP transactions
Authors: Barford Paul , Crovella Mark
Published: October 2004

Improving the performance of data transfers in the Internet (such as Web transfers) requires a detailed understanding of when and how delays are introduced. Unfortunately, the complexity of data transfers like those using HTTP is great enough that identifying the precise causes of delays is difficult. In this paper we describe a method for pinpointing where delays are introduced into applications like HTTP by using
critical path analysis.
By constructing and profiling the critical path, it is possible to determine what fraction of total transfer latency is due to packet propagation, network variation (
e.g.,
queuing at routers or route fluctuation), packet losses, and delays at the server and at the client. We have implemented our technique in a tool called tcpeval that automates critical path analysis for Web transactions. We show that our analysis method is robust enough to analyze traces taken for two different TCP implementations (Linux and FreeBSD). To demonstrate the utility of our approach, we present the results of critical path analysis for a set of Web transactions taken over 14 days under a variety of server and network conditions. The results show that critical path analysis can shed considerable light on the causes of delays in Web transfers, and can expose subtleties in the behavior of the entire end-to-end system.
Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED
Authors: Misra Vishal , Gong Wei-Bo , Towsley Don
Published: October 2004

In this paper we use jump process driven Stochastic Differential Equations to model the interactions of a set of TCP flows and Active Queue Management routers in a network setting. We show how the SDEs can be transformed into a set of Ordinary Differential Equations which can be easily solved numerically. Our solution methodology scales well to a large number of flows. As an application, we model and solve a system where RED is the AQM policy. Our results show excellent agreement with those of similar networks simulated using the well known ns simulator. Our model enables us to get an in-depth understanding of the RED algorithm. Using the tools developed in this paper, we present a critical analysis of the RED algorithm. We explain the role played by the RED configuration parameters on the behavior of the algorithm in a network. We point out a flaw in the RED averaging mechanism which we believe is a cause of tuning problems for RED. We believe this modeling/solution methodology has a great potential in analyzing and understanding various network congestion control algorithms.
Routing stability in congested networks
Authors: Shaikh Aman , Varma Anujan , Kalampoukas Lampros , Dube Rohit
Published: October 2004

Loss of the routing protocol messages due to network congestion can cause peering session failures in routers, leading to route flaps and routing instabilities. We study the effects of traffic overload on routing protocols by quantifying the stability and robustness properties of two common Internet routing protocols, OSPF and BGP, when the routing control traffic is not isolated from data traffic. We develop analytical models to quantify the effect of congestion on the robustness of OSPF and BGP as a function of the traffic overload factor, queueing delays, and packet sizes. We perform extensive measurements in an experimental network of routers to validate the analytical results. Subsequently we use the analytical framework to investigate the effect of factors that are difficult to incorporate into an experimental setup, such as a wide range of link propagation delays and packet dropping policies. Our results show that increased queueing and propagation delays adversely affect BGP's resilience to congestion, in spite of its use of a reliable transport protocol. Our findings demonstrate the importance of selective treatment of routing protocol messages from other traffic, by using scheduling and utilizing buffer management policies in the routers, to achieve stable and robust network operation.
SmartBridge
Authors: Rodeheffer Thomas L. , Thekkath Chandramohan A. , Anderson Darrell C.
Published: October 2004

As the number of hosts attached to a network increases beyond what can be connected by a single local area network (LAN), forwarding packets between hosts on different LANs becomes an issue. Two common solutions to the forwarding problem are
IP routing
and
spanning tree bridging
. IP routing scales well, but imposes the administrative burden of managing subnets and assigning addresses. Spanning tree bridging, in contrast, requires no administration, but often does not perform well in a large network, because too much traffic must detour toward the root of the spanning tree, wasting link bandwidth.
TCP is max-plus linear and what it tells us on its throughput
Authors: Baccelli François , Hong Dohy
Published: October 2004

We give a representation of the packet-level dynamical behavior of the Reno and Tahoe variants of TCP over a single end-to-end connection. This representation allows one to consider the case when the connection involves a network made of several, possibly heterogeneous, deterministic or random routers in series. It is shown that the key features of the protocol and of the network can be expressed via a linear dynamical system in the so called max-plus algebra. This opens new ways of both analytical evaluation and fast simulation based on products of matrices in this algebra. This also leads to closed form formulas for the throughput allowed by TCP under natural assumptions on the behavior of the routers and on the detection of losses and timeouts; these new formulas are shown to refine those obtained from earlier models which either assume that the network could be reduced to a single bottleneck router and/or approximate the packets by a fluid.
Deriving traffic demands for operational IP networks
Authors: Feldmann Anja , Greenberg Albert , Lund Carsten , Reingold Nick , Rexford Jennifer , True Fred
Published: October 2004

Engineering a large IP backbone network without an accurate, network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network elements can result in significant (and sudden) fluctuations in load. In this paper, we present a model of traffic demands to support traffic engineering and performance debugging of large Internet Service Provider networks. By defining a traffic demand as a volume of load originating from an ingress link and destined to a set of egress links, we can capture and predict how routing affects the traffic traveling between domains. To infer the traffic demands, we propose a measurement methodology that combines flow-level measurements collected at all ingress links with reachability information about all egress links. We discuss how to cope with situations where practical considerations limit the amount and quality of the necessary data. Specifically, we show how to infer interdomain traffic demands using measurements collected at a smaller number of edge links --- the peering links connecting to neighboring providers. We report on our experiences in deriving the traffic demands in the AT&T IP Backbone, by collecting, validating, and joining very large and diverse sets of usage, configuration, and routing data over extended periods of time. The paper concludes with a preliminary analysis of the observed dynamics of the traffic demands and a discussion of the practical implications for traffic engineering.
Trajectory sampling for direct traffic observation
Authors: Duffield N. G. , Grossglauser M.
Published: October 2004

Traffic measurement is a critical component for the control and engineering of communication networks. We argue that traffic measurement should make it possible to obtain the spatial flow of traffic through the domain, i.e., the paths followed by packets between any ingress and egress point of the domain. Most resource allocation and capacity planning tasks can benefit from such information. Also, traffic measurements should be obtained without a routing model and without knowledge of network state. This allows the traffic measurement process to be resilient to network failures and state uncertainty.

We propose a method that allows the direct inference of traffic flows through a domain by observing the trajectories of a subset of all packets traversing the network. The key advantages of the method are that (i) it does not rely on routing state, (ii) its implementation cost is small, and (iii) the measurement reporting traffic is modest and can be controlled precisely. The key idea of the method is to sample packets based on a hash function computed over the packet content. Using the same hash function will yield the same sample set of packets in the entire domain, and enables us to reconstruct packet trajectories.
Measuring link bandwidths using a deterministic model of packet delay
Authors: Lai Kevin , Baker Mary
Published: October 2004

We describe a deterministic model of packet delay and use it to derive both the
packet pair
[2] property of FIFO-queueing networks and a new technique
packet tailgating
) for actively measuring link bandwidths. Compared to previously known techniques, packet tailgating usually consumes less network bandwidth, does not rely on consistent behavior of routers handling ICMP packets, and does not rely on timely delivery of acknowledgments.
Practical network support for IP traceback
Authors: Savage Stefan , Wetherall David , Karlin Anna , Anderson Tom
Published: October 2004

This paper describes a technique for tracing anonymous packet flooding attacks in the Internet back towards their source. This work is motivated by the increased frequency and sophistication of denial-of-service attacks and by the difficulty in tracing packets with incorrect, or ``spoofed'', source addresses. In this paper we describe a general purpose traceback mechanism based on probabilistic packet marking in the network. Our approach allows a victim to identify the network path(s) traversed by attack traffic without requiring interactive operational support from Internet Service Providers (ISPs). Moreover, this traceback can be performed ``post-mortem'' -- after an attack has completed. We present an implementation of this technology that is incrementally deployable, (mostly) backwards compatible and can be efficiently implemented using conventional technology.
When the CRC and TCP checksum disagree
Authors: Stone Jonathan , Partridge Craig
Published: October 2004

Traces of Internet packets from the past two years show that between 1 packet in 1,100 and 1 packet in 32,000 fails the TCP checksum, even on links where link-level CRCs should catch all but 1 in 4 billion errors. For certain situations, the rate of checksum failures can be even higher: in one hour-long test we observed a checksum failure of 1 packet in 400. We investigate why so many errors are observed, when link-level CRCs should catch nearly all of them.

We have collected nearly 500,000 packets which failed the TCP or UDP or IP checksum. This dataset shows the Internet has a wide variety of error sources which can not be detected by link-level checks. We describe analysis tools that have identified nearly 100 different error patterns. Categorizing packet errors, we can infer likely causes which explain roughly half the observed errors. The causes span the entire spectrum of a network stack, from memory errors to bugs in TCP.

After an analysis we conclude that the checksum will fail to detect errors for roughly 1 in 16 million to 10 billion packets. From our analysis of the cause of errors, we propose simple changes to several protocols which will decrease the rate of undetected error. Even so, the highly non-random distribution of errors strongly suggests some applications should employ application-level checksums or equivalents.
Packet types
Authors: McCann Peter J. , Chandra Satish
Published: October 2004

In writing networking code, one is often faced with the task of interpreting a raw buffer according to a standardized packet format. This is needed, for example, when monitoring network traffic for specific kinds of packets, or when unmarshaling an incoming packet for protocol processing. In such cases, a programmer typically writes C code that understands the grammar of a packet and that also performs any necessary byte-order and alignment adjustments. Because of the complexity of certain protocol formats, and because of the low-level of programming involved, writing such code is usually a cumbersome and error-prone process. Furthermore, code written in this style loses the domain-specific information, viz. the packet format, in its details, making it difficult to maintain.
Algebraic acceptance mechanisms for polynomial time machines
Authors: Hertrampf Ulrich
Published: October 2004

We present several results, mainly taken from the author's recent conference articles [Her97a, Her97b, Her99], whose common theme is the application of (quite basic) algebraic techniques to describe complexity classes, which appear in the many ways nondeterministic polynomial time machines can be used (or abused).One possibility to motivate this is an exact characterization of the (at first glance) rather weak (2 out of 3)-P-set paradigm (see the Introduction for a description), which we will prove to be as powerful as PSPACE.
A potential-based amortized analysis of the union-find data structure
Authors: Harfst Gregory C. , Reingold Edward M.
Published: October 2004

We present a simple, new potential-based amortized analysis for the standard union-find data structure.
The construction of Huffman-equivalent prefix code in NC
Authors: Teng Shang-Hua
Published: October 2004

In this paper, we show that an optimal prefix code (Huffman-equivalent code) over Σ = {0,1,...,σ} for any
n
letters
a
1
,...,

a
n

of frequency
f
1
,...,

f
n

can be constructed in
O
(log
2
n
) time, using only polynomial number of processors. This is done by a uniform reduction of optimal prefix coding problem to a min-plus circuit value problem of polynomial size and linear degree. Thus we can use the parallel circuit evaluation algorithms presented in [7] and [8] to construct a time-efficient and processor-efficient parallel algorithm for optimal prefix coding problem.
An example case study on Ada tasking
Authors: Sumate Ken
Published: October 2004

Case studies are an important method for teaching complex aspects of a programming language. This is especially true for real-time/concurrent systems. This paper presents a software requirements specification for a small but realistic real-time system, and then presents the solution in Ada. The actual hardware interactions are abstracted out, allowing the solution to be developed on a multi-user system. The focus of the solution is on treatment of certain aspects of concurrency. The solution model is based on a paradigm of top-level design, detailed design, and code.
The efficient termination of Ada tasks in a multi-processor environment
Authors: Flynn Susan , Schonberg Edith , Schonberg Edmond
Published: October 2004

An efficient implementation of Ada task termination for shared memory MIMD architectures is presented. The solution is highly parallel and distributed; termination is not synchronized by a centralized supervisor, and there are no critical sections. The handling of block and subprogram termination that depend on nested tasks is also included. This implementation can be easily adapted to message based systems.
Observations on the portability of Ada I/O
Authors: Matthews Edmund R.
Published: October 2004

I have been involved recently in developing reusable Ada components which are portable (in theory) across multiple systems using multiple compilers. One of the biggest problem areas in Ada portability aside from Chapter 13 issues is Chapter 14, Ada I/O. This paper represents an informal collection of my working notes on the portability problems of Chapter 14. These notes are based on my experience with a wide variety of compilers on an even larger set of hardware. I have purposefully not mentioned any compilers by name as I only wish to show the differences between implementations and do not wish to imply that any compiler is better than any other. While I/O is inherently non-portable, packages of common I/O functions such as those described in Chapter 14 can be specified in a manner which ensures maximum portability. There are too many loopholes and areas for implementor interpretation in current Ada 1.0; I hope to see more stringent I/0 specifications in 1988.
Discrete-event simulation in Ada: concepts
Authors: Shore R. W.
Published: October 2004

Ada was designed to include unique features which make it appropriate for a wide variety of programming tasks. In addition, the packaging and separate-compilation features of Ada allow a programmer to extend the language through the inclusion of specialized toolkits for specific applications. This paper discusses the concepts behind a series of Ada packages which allow a programmer to construct a discrete-event simulation in Ada. A simple barbership simulation is used as a running example.
VLSI assist for a multiprocessor
Authors: Beck Bob , Kasten Bob , Thakkar Shreekant
Published: October 2004

Multiprocessors have long been of interest to computer community. They provide the potential for accelerating applications through parallelism and increased throughput for large multi-user system. Three factors have limited the commercial success of multiprocessor systems; entry cost, range of performance, and ease of application. Advances in very large scale integration (VLSI) and in computer aided design (CAD) have removed these limitations, making possible a new class of multiprocessor systems based on VLSI components. A set of requirements for building an efficient shared multiprocessor system are discussed, including: low-level mutual exclusion, interrupt distribution, inter-processor signaling, process dispatching, caching, and system configuration. A system that meets these requirements is described and evaluated.
Architectural support for multilanguage parallel programming on heterogeneous systems
Authors: Bisiani Roberto , Forin Alessandro
Published: October 2004

We have designed and implemented a software facility, called Agora, that supports the development of parallel applications written in multiple languages. At the core of Agora there is a mechanism that allows concurrent computations to share data structures independently of the computer architecture they are executed on. Concurrent computations exchange control information by using a pattern-directed technique. This paper describes the Agora shared memory and its software implementation on both tightly and loosely-coupled architectures.
Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures
Authors: Rashid Richard , Tevanian Avadis , Young Michael , Golub David , Baron Robert , Black David , Bolosky William , Chew Jonathan
Published: October 2004

This paper describes the design and implementation of virtual memory management within the CMU Mach Operating System and the experiences gained by the Mach kernel group in porting that system to a variety of architectures. As of this writing, Mach runs on more than half a dozen uniprocessors and multiprocessors including the VAX family of uniprocessors and multiprocessors, the IBM RT PC, the SUN 3, the Encore MultiMax, the Sequent Balance 21000 and several experimental computers. Although these systems vary considerably in the kind of hardware support for memory management they provide, the machine-dependent portion of Mach virtual memory consists of a single code module and its related header file. This separation of software memory management from hardware support has been accomplished without sacrificing system performance. In addition to improving portability, it makes possible a relatively unbiased examination of the pros and cons of various hardware memory management schemes, especially as they apply to the support of multiprocessors.
The dragon processor
Authors: Atkinson Russell R. , McCreight Edward M.
Published: October 2004

The Xerox PARC Dragon is a VLSI research computer that uses several techniques to achieve dense code and fast procedure calls in a system that can support multiple processors on a central high bandwidth memory bus.
Coherency for multiprocessor virtual address caches
Authors: Goodman James R.
Published: October 2004

A multiprocessor cache memory system is described that supplies data to the processor based on virtual addresses, but maintains consistency in the main memory, both across caches and across virtual address spaces. Pages in the same or different address spaces may be mapped to share a single physical page. The same hardware is used for maintaining consistency both among caches and among virtual addresses. Three different notions of a cache "block" are defined: (1) the unit for transferring data to/from main storage, (2) the unit over which tag information is maintained, and (3) the unit over which consistency is maintained. The relation among these block sizes is explored, and it is shown that they can be optimized independently. It is shown that the use of large address blocks results in low overhead for the virtual address cache.