bluuebunny/crossref_metadata_2025 huggingface dataset:
The changing nature of network traffic
Authors: Feldmann A. , Gilbert A. C. , Willinger W. , Kurtz T. G.
Published: October 2004

In this paper, we report on some preliminary results from an in-depth, wavelet-based analysis of a set of high-quality, packet-level traffic measurements, collected over the last 6-7 years from a number of different wide-area networks (WANs). We first validate and confirm an earlier finding, originally due to Paxson and Floyd [14], that actual WAN traffic is consistent with statistical self-similarity for sufficiently large time scales. We then relate this large-time scaling phenomenon to the empirically observed characteristics of WAN traffic at the level of individual connections or applications. In particular, we present here original results about a detailed statistical analysis of Web-session characteristics, and report on an intriguing scaling property of measured WAN traffic at the transport layer (i.e., number of TCP connection arrivals per time unit). This scaling property of WAN traffic at the TCP layer was absent in the pre-Web period but has become ubiquitous in today's WWW-dominated WANs and is a direct consequence of the ever-increasing popularity of the Web (WWW) and its emergence as the major contributor to WAN traffic. Moreover, we show that this changing nature of WAN traffic can be naturally accounted for by self-similar traffic models, primarily because of their ability to provide physical explanations for empirically observed traffic phenomena in a networking context. Finally, we provide empirical evidence that actual WAN traffic traces also exhibit scaling properties over small time scales, but that the small-time scaling phenomenon is distinctly different from the observed large-time scaling property. We relate this newly observed characteristic of WAN traffic to the effects that the dominant network protocols (e.g., TCP) and controls have on the flow of packets across the network and discuss the potential thatmultifractalshave in this context for providing a structural modeling approach for WAN traffic and for capturing in a compact and parsimonious manner the observed scaling phenomena at large as well as small time scales.
Resource aggregation for fault tolerance in integrated services networks
Authors: Dovrolis Constantinos , Ramanathan Parameswaran
Published: October 2004

For several real-time applications it is critical that the failure of a network component does not lead to unexpected termination or long disruption of service. In this paper, we propose a scheme called RAFT (Resource Aggregation for Fault Tolerance) that guarantees recovery in a timely and resource-efficient manner. RAFT is presented in the framework of the Reliable Back-bone (RBone), a virtual network layered on top of an integrated services network. Applications can request fault tolerance against RBone link and node failures. The basic idea of RAFT is to setup every fault tolerant flow along a secondary path that serves as a backup in case the primary path fails. The secondary path resource reservations are aggregated whenever possible to reduce the overhead of providing fault tolerance. We show that the RSVP resource reservation protocol can support RAFT with simple extensions.
Policy tree multicast routing
Authors: Hodel Horst
Published: October 2004

Bandwidth-sensitive multicast delivery controlled by routing criteria pertinent to the actual traffic flow is very costly in terms of router state and control overhead and it scales poorly towards larger, wide-area networks. PIM-SM (Protocol-independent Multicast - Sparse Mode) has been introduced as a simple, flexible and scalable concept for Internet-wide multicasting. Yet, PIM's efficiency potential (like that of alternative wide-area multicast concepts) can only be fully exploited if it is based on Reverse Path Forwarding (RPF), a low-cost mechanism, which however does not select prescribed delivery paths if link parameters or routing policies are asymmetric. This paper presents an extension to protocols like PIM-SM, called Policy Tree Multicast Routing (PTMR). This concept leads to multicast delivery trees which, even under asymmetric conditions, readily comply with imposed macroscopic policies and moreover enable support of shortest path and QoS criteria. PTMR gives no consideration to how the policy-sensitive paths have been established; they may be imposed by the network itself but also by providers, recipients and even sources. PTMR amends the PIM-SM mechanism with a macroscopic control layer which marks (pegs) domain border routers on policy-sensitive forward paths. In a given domain, a pegged ingress border router is then joined by local group members as well as by its child pegs. This results in optimally fusing transit paths into local distribution trees. PTMR performance and policy control potential are restricted primarily: by the congestion of control messages at the multicast sources, introduced by source-originating tree construction; by the possible extent of policy-sensitive path aggregation; and by the intra-domain (transit) delivery conditions. PTMR is a single-layer protocol, appending PIM-SM with a policy dedicated delivery mode. Ist primary design target is to forward multicast traffic in accordance with any underlying multicast-relevant routing, including comprehensive policy routing. In comparison, Border Gateway Multicast Protocol (BGMP) is a proposal for an intra-domain MR protocol based on BGP-type routing, which focuses on fusing heterogenous multicast routing domains and which allows ASs to control multicast transit traffic.
Multicast ATM switches
Authors: Guo Ming-Huang , Chang Ruay-Shiung
Published: October 2004

Computer networks are undergoing a remarkable transformation. The widespread use of optical fiber to transmit data has made tremendous increases in network bandwidth. Furthermore, greater CPU power, increasing disk capacity, and support for digital audio and video are creating demand for a new class of network services. For example, video-on-demand, distant learning, distant diagnosis, video conferences, and many others applications have popped up one after another in recent years. Many of these services have one thing in common. They all require that the same piece of data be sent to multiple recipients. Even in traditional networks, this operation, called multicasting, can not be handled easily and cheaply. When scaled up to high speed ATM-based networks, the situation could be worse. Multiple streams of data travel around ATM networks. Each tries to send to many different destinations simultaneously. Therefore, designing economical ATM network switches which can support multicasting operations easily is very important in the future generation high speed networks. In the past twelve years or so, many designs for multicasting ATM switches are proposed. It seems about time to do a historical survey. It is hoped that by learning from the wisdom of the previous authors, new spark or angle can be found and exploited to design new multicasting ATM switches. Without easy and inexpensive multicasting, all the exciting services may become unaffordable. This will in turn lead to the diminishing of customer bases and finally will hinder the full-scale deployment of high speed networks.
AdaGIDE: a friendly introductory programming environment for a freshman computer science course
Authors: Carlisle Martin C. , Chamillard A. T.
Published: October 2004

We have recently transitioned the programming language in our Introduction to Computer Science course at the U.S. Air Force Academy from Pascal to Ada. Providing an intuitive and straightforward Integrated Development Environment (IDE) for Ada that is suitable for freshman use has been one of our greatest challenges. Although we recognize that a number of Ada IDEs are available, these IDEs do not seem to be designed for beginning programmers. Most of them are either too expensive for students to purchase or are designed for development of large programming projects, carrying significant overhead for the small programs we require in our freshman course. Error messages tend to be fairly complicated, assuming a relatively thorough understanding of the language syntax and semantics. Finally, both commercial and free IDEs can have extensive lead time for bug fix development and are not readily extensible.These concerns led us to develop a Windows 95 Ada IDE that is free to the students, contains the appropriate level of functionality for our freshman course, has a minimal, lead time for bug fix development (since we maintain the code in-house), and can be easily extended to contain additional help for the students. Because we implemented this environment in Ada we can also demonstrate to our students that Ada is applicable to real, large projects, and its usefulness is not limited to the small programs they create in the freshman course. This paper describes our preliminary experience with this environment.The next section briefly describes the IDE and the third section lists a number of issues we have faced trying to interface to Windows 95. The fourth and fifth sections discuss student and faculty reaction to and use of the environment. The final section presents our conclusions and our plans for future enhancements to the IDE.
Addressing security for object-oriented design and Ada 95 development
Authors: Reisner John A. , Demurjian Steven A.
Published: October 2004

During the 1990s, we have seen an explosive growth in object-oriented design and development. Ada95 and its strong ties to DoD and government software, and Java with an increasing impact on commercial internet-based and general-purpose software, both expand the base of software professionals working on object-oriented platforms. Security is a paramount concern in both languages; in Ada 95 to manage access to government sensitive data, and in Java to control the effects of platform-independent software. Organizations will demand high constancy and high assurance in object-oriented software, across a wide range of domains. For example, health care systems need instant access to data in life-critical situations, while CAD applications must insure that the most up-to-date specifications on mechanical parts are available in a shared manner to promote cooperation and facilitate productivity. The successful Ada 95 Tool Chest for the Year 2000 must contain tools and techniques that support the definition, analyses, and enforcement of security for object-oriented software. This paper investigates security for object-oriented design with a focus on its realization in Ada 95.
Rethinking testing with Ada95
Authors: Rymer John
Published: October 2004

The new definition of Ada (Ada95) provides full support for the Object Oriented (OO) paradigm. With the use of OO comes many new challenges. OO analysis, design, and coding techniques have been well defined and documented. This paper looks at the challenges associated with software development testing of an OO project and makes specific recommendations concerning unit testing and object integration in the Ada95 environment.
GRASP
Authors: Hendrix T. Dean , Cross James H. , Barowski Larry A. , Mathias Karl S.
Published: October 2004

GRASP is a prototype software visualization and development tool currently being used both in industry and in computer science curricula. GRASP is freely available for Solaris, Linux, Windows 95, and Windows NT. This paper describes the Windows version of GRASP along with its primary visualization, the Control Structure Diagram.
An ADA reuse support system for Windows 95/NT
Authors: Battaglia David , Burke Austin , Beidler John
Published: October 2004

This paper describes a software resource that is being developed as part of the graduation requirement for the Master in Software Engineering degree at the University of Scranton. This project evolved from a series of experiments that were performed in undergraduate and graduate courses at the University. A basic editor was developed as part of an undergraduate course in rapid prototyping. Several students used that project as the basis for undergraduate Senior Projects. All undergraduates are required to complete a project as a degree requirement. This basic editor was handed over to a graduate course in Software Generation and Maintenance and used as the starting point for the construction of various software project management features. The system was constructed to support Ada source code development. However, the system could be readily modified to support source code management in other languages, notably C++. This paper describes the construction of resources that encourage the use of reusable software. Subsequent sections describe the overall framework of the system and selected details that carry out features that make reuse attractive. The system is called
ReUSE
(the
Re
use
U
niversity of
S
cranton
E
nvironment).ReUSE is an Ada programming environment which facilitates and promotes code reuse by individual developers or teams of developers. It provides centralized storage of project files, a package browser, automatic function and procedure call creation, a compiler interface, interactive error processing, multiple simultaneous editors, standard windows tools (menus, toolbars, etc.), and other features to help the developer write and reuse Ada code efficiently.ReUSE was developed in Microsoft Visual Basic 4.0 (32-bit) for the Windows 95 / NT operating systems.
Early projects using Ada at the United States Air Force Academy
Authors: Grier Samuel
Published: October 2004

Ada is the language of choice in the computer science curriculum at the Air Force Academy. Its richness, complexity and strong typing are ideal for teaching abstraction, encapsulation and object-oriented programming in the context of good programming practices.Specifically, the Department of Computer Science teaches Ada in its introductory course required of all students at the Academy. Those cadets majoring in computer science then take an additional Ada programming course in the Fall of their sophomore year, followed by a course in programming languages in the Spring semester. It is this third course, Computer Science 359, that gives cadets their first experience programming a problem of significant complexity in Ada, while introducing them to a wide variety of topics and language capabilities.Computer Science 359 has the following goals and objectives:1. Gain a basic understanding of the four programming language paradigms: imperative, object-oriented, functional and logic-oriented.2. Gain a broad knowledge of the Ada programming language.3. Gain a working knowledge of object-oriented programming.4. Gain familiarity with a functional and logic-oriented programming language.5. Gain a working knowledge of recursion.This paper discusses the type and scope of projects that have been used to teach the Ada programming portion of the course.
Test results of the commercial internet multimedia trials
Authors: Baugher Mark , Jarrar Saib
Published: October 2004

This paper reports the test results of applications and services from the Commercial Internet Multimedia Trials. The Trials were a twelve-month effort by three companies to evaluate the product readiness of multimedia applications and services in business environments by supporting multimedia services on production IP networks. The test beds were enabled for IP multicast routing; one of the test beds was enabled for RSVP. The results of our RSVP tests and user surveys are reported, and some of issues related to the deployment of multimedia services and applications on corporate IP networks are considered.
On routes and multicast trees in the Internet
Authors: Pansiot Jean-Jacques , Grad Dominique
Published: October 2004

Multicasting has an increasing importance for network applications such as groupware or videoconferencing. Several multicast routing protocols have been defined. However they cannot be used directly in the Internet since most inter-domain routers do no implement multicasting. Thus these protocols are mainly tested either on a small scale inside a domain, or through the Mboné, whose topology is not really the same as Internet topology. The purpose of this paper is to construct a graph using actual routes of the Internet, and then to use this graph to compare some parameters - delays, scaling in term of state or traffic concentration - of multicast routing trees constructed by different algorithms - source shortest path trees and shared trees.
Reprints from computing reviews
Authors: Seiferas Joel
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 $43 per year by writing to ACM headquarters.
Scalable QoS provision through buffer management
Authors: Guérin R. , Kamat S. , Peris V. , Rajan R.
Published: October 2004

In recent years, a number of link scheduling algorithms have been proposed that greatly improve upon traditional FIFO scheduling in being able to assure rate and delay bounds for individual sessions. However, they cannot be easily deployed in a backbone environment with thousands of sessions, as their complexity increases with the number of sessions. In this paper, we propose and analyze an approach that uses a simple buffer management scheme to provide rate guarantees to individual flows (or to a set of flows) multiplexed into a common FIFO queue. We establish the buffer allocation requirements to achieve these rate guarantees and study the trade-off between the achievable link utilization and the buffer size required with the proposed scheme. The aspect of fair access to excess bandwidth is also addressed, and its mapping onto a buffer allocation rule is investigated. Numerical examples are provided that illustrate the performance of the proposed schemes. Finally, a scalable architecture for QoS provisioning is presented that integrates the proposed buffer management scheme with WFQ scheduling that uses a small number of queues.
Data networks as cascades
Authors: Feldmann A. , Gilbert A. C. , Willinger W.
Published: October 2004

In apparent contrast to the well-documented self-similar (i.e., monofractal) scaling behavior of measured LAN traffic, recent studies have suggested that measured TCP/IP and ATM WAN traffic exhibits more complex scaling behavior, consistent with multifractals. To bring multifractals into the realm of networking, this paper provides a simple construction based on cascades (also known as multiplicative processes) that is motivated by the protocol hierarchy of IP data networks. The cascade framework allows for a plausible physical explanation of the observed multifractal scaling behavior of data traffic and suggests that the underlying multiplicative structure is a traffic invariant for WAN traffic that co-exists with self-similarity. In particular, cascades allow us to refine the previously observed self-similar nature of data traffic to account for local irregularities in WAN traffic that are typically associated with networking mechanisms operating on small time scales, such as TCP flow control.To validate our approach, we show that recent measurements of Internet WAN traffic from both an ISP and a corporate environment are consistent with the proposed cascade paradigm and hence with multifractality. We rely on wavelet-based time-scale analysis techniques to visualize and to infer the scaling behavior of the traces, both globally and locally. We also discuss and illustrate with some examples how this cascade-based approach to describing data network traffic suggests novel ways for dealing with networking problems and helps in building intuition and physical understanding about the possible implications of multifractality on issues related to network performance analysis.
The MASC/BGMP architecture for inter-domain multicast routing
Authors: Kumar Satish , Radoslavov Pavlin , Thaler David , Alaettinoğlu Cengiz , Estrin Deborah , Handley Mark
Published: October 2004

Multicast routing enables efficient data distribution to multiple recipients. However, existing work has concentrated on extending single-domain techniques to wide-area networks, rather than providing mechanisms to realize inter-domain multicast on a global scale in the Internet.We describe an architecture for inter-domain multicast routing that consists of two complementary protocols. The Multicast Address-Set Claim (MASC) protocol forms the basis for a hierarchical address allocation architecture. It dynamically allocates to domains multicast address ranges from which groups initiated in the domain get their multicast addresses. The Border-Gateway Multicast Protocol (BGMP), run by the border routers of a domain, constructs inter-domain bidirectional shared trees, while allowing any existing multicast routing protocol to be used within individual domains. The resulting shared tree for a group is rooted at the domain whose address range covers the group's address; this domain is typically the group initiator's domain. We demonstrate the feasibility and performance of these complementary protocols through simulation.This architecture, together with existing protocols operating within each domain, is intended as a framework in which to solve the problems facing the current multicast addressing and routing infrastructure.
Core
-stateless fair queueing
Authors: Stoica Ion , Shenker Scott , Zhang Hui
Published: October 2004

Router mechanisms designed to achieve fair bandwidth allocations, like Fair Queueing, have many desirable properties for congestion control in the Internet. However, such mechanisms usually need to maintain state, manage buffers, and/or perform packet scheduling on a per flow basis, and this complexity may prevent them from being cost-effectively implemented and widely deployed. In this paper, we propose an architecture that significantly reduces this implementation complexity yet still achieves approximately fair bandwidth allocations. We apply this approach to an island of routers --- that is, a contiguous region of the network --- and we distinguish between edge routers and core routers. Edge routers maintain per flow state; they estimate the incoming rate of each flow and insert a label into each packet header based on this estimate. Core routers maintain
no
per flow state; they use FIFO packet scheduling augmented by a probabilistic dropping algorithm that uses the packet labels and an estimate of the aggregate traffic at the router. We call the scheme
Core
-Stateless Fair Queueing. We present simulations and analysis on the performance of this approach, and discuss an alternate approach.
The performance of query control schemes for the zone routing protocol
Authors: Haas Zygmunt J. , Pearlman Marc R.
Published: October 2004

In this paper, we study the performance of route query control mechanisms for the recently proposed Zone Routing Protocol (ZRP) for ad-hoc networks. The ZRP proactively maintains routing information for a local neighborhood (routing zone), while reactively acquiring routes to destinations beyond the routing zone. This hybrid routing approach has the potential to be more efficient in the generation of control traffic than traditional routing schemes. However, without proper query control techniques, the ZRP can actually produce more traffic than standard flooding protocols.Our proposed query control schemes exploit the structure of the routing zone to provide enhanced detection (Query Detection (QD1/QD2)), termination (Loop-back Termination (LT), Early Termination (ET)) and prevention (Selective Bordercasting (SBC)) of overlapping queries. We demonstrate how certain combinations of these techniques can be applied to single channel or multiple channel ad-hoc networks to improve both the delay and control traffic performance of the ZRP. Our query control mechanisms allow the ZRP to provide routes to all accessible network nodes with only a fraction of the control traffic generated by purely proactive distance vector and purely reactive flooding schemes, and with a response time as low as 10% of a flooding route query delay.
An extensible probe architecture for network protocol performance measurement
Authors: Malan G. Robert , Jahanian Farnam
Published: October 2004

This paper describes the architecture and implementation of Windmill, a passive network protocol performance measurement tool. Windmill enables experimenters to measure a broad range of protocol performance metrics by both reconstructing application-level network protocols and exposing the underlying protocol layers' events. Windmill is split into three functional components: a dynamically compiled Windmill Protocol Filter (WPF), a set of abstract protocol modules, and an extensible experiment engine. To demonstrate Windmill's utility, the results from several experiments are presented. The first set of experiments suggests a possible cause for the correlation between Internet routing instability and network utilization. The second set of experiments highlights: Windmill's ability to act as a driver for a complementary active Internet measurement apparatus, its ability to perform online data reduction, and the non-intrusive measurement of a closed system.
Router plugins: a software architecture for next generation routers
Authors: Decasper Dan , Dittia Zubin , Parulkar Guru , Plattner Bernhard
Published: October 2004

Present day routers typically employ monolithic operating systems which are not easily upgradable and extensible. With the rapid rate of protocol development it is becoming increasingly important to dynamically upgrade router software in an incremental fashion. We have designed and implemented a high performance, modular, extended integrated services router software architecture in the NetBSD operating system kernel. This architecture allows code modules, called
plugins
, to be dynamically added and configured at run time. One of the novel features of our design is the ability to bind different plugins to individual flows; this allows for distinct plugin implementations to seamlessly coexist in the same runtime environment. High performance is achieved through a carefully designed modular architecture; an innovative packet classification algorithm that is both powerful and highly efficient; and by caching that exploits the flow-like characteristics of Internet traffic. Compared to a monolithic best-effort kernel, our implementation requires an average increase in packet processing overhead of only 8%, or 500 cycles/2.1ms per packet when running on a P6/233.
Accelerated reliability analysis for self-healing SONET networks
Authors: Cankaya Hakki C. , Nair V. S. S.
Published: October 2004

Recently, a parametric State Reward Markov Model (SRMM/p) has been developed for the reliability and availability analysis of self-healing SONET mesh networks [2]. In this paper, we investigate the factors that affect the run-time complexity of the model presented in [2]. In order to accelerate the reliability and availability analysis, we present an approach that aggregates a set of states in the model based on 2-phase hypoexponential distribution. A comparison of the original and the reduced model, with respect to runtime complexity and accuracy, is carried out by applying the models for the analysis of few complex networks.
The Ada recommendation—a year later
Authors: Vaughn Rayford B.
Published: October 2004

In January 1997, the National Research Council published a report to the Department of Defense entitled Ada and Beyond, Software Policies for the Department of Defense. The author of this paper was a member of the committee that produced that report. This paper looks at the original recommendations of the report and comments on the results (intended and unintended) within the DoD community over the past year.
Graphics for free
Authors: Carlisle Martin C.
Published: October 2004

Students find computer graphics one of the most interesting topics in computer science. Unfortunately, writing programs with graphics requires understanding concepts that are usually beyond the scope of an introductory computer science course. For example, in Windows 95, a program that uses graphics must have an event loop that dispatches messages to the appropriate handler. Event loops, messages and handlers are well beyond the grasp of someone just learning about variables! As a result, programming assignments for introductory courses tend to use no graphics, or simple ANSI graphics (see, e.g. Feldman and Koffman [1]). These programs compare unfavorably to the graphics of games most students are accustomed to using, and motivation to program in an introductory course may be lost.Ideally, we would like to be able to have students write programs that have more appealing interfaces, yet do not require a large amount of additional conceptual complexity. In fact, the best case would be to have the student write a program as if it were a simple text-based program, and have the compiler automatically add a graphical interface. Languages that provide overloading, such as Ada 95, allow us to accomplish precisely that.This paper describes a library, Graphics_110 (named in honor of our introductory course), which, using overloading, replaces the standard I/O libraries in Ada 95: Ada.Text_IO, Ada.Float_Text_IO, and Ada.Integer_Text_IO. By following a simple contract and replacing calls to the standard libraries with calls to Graphics_110, the student obtains a program, with a Windows-style interface without ever having to worry about the implementation details. Although we use Ada 95 for this paper, the ideas extend to any programming language that provides subtypes and overloading.The next section describes the "contract" the programmer must follow to use the library and the third section describes the implementation of Graphics_110. In each section, we describe how Graphics_110 was used with a battleship game implemented in our introductory course. The final section presents conclusions and ideas for future work.
Assessing GRASP utilization through instrumentation
Authors: Hendrix T. Dean , Cross James H. , Teate Joe C. , Barowski Larry A. , Mathias Karl S.
Published: October 2004

The idea that representing something visually can help us understand it has long been promoted in common practice and in the literature [1,2,3,4,5,6]. Indeed, "a picture is worth a thousand words" has become a standard cliché in our culture. In the case of software, however, one must take great care that it is the correct thousand words that are being conveyed [5]. Nonetheless, appropriate visualizations of software can be quite beneficial to programmers, especially when faced with program comprehension tasks. Such tasks exist throughout the software life cycle (e.g., formal technical reviews, debugging, verification, reverse engineering) and in the classroom (e.g., students reading examples from the text or examples from the professor).The GRASP (Graphical Representations of Algorithms, Structures, and Processes) research project at Auburn University seeks to develop tools and techniques for the effective use of graphical representations and visualizations of software. The overall goal of this research is to increase the efficiency of programmer comprehension and understanding of source code, and thereby decrease overall software cost. As an integral part of the research project, the GRASP software engineering tool has been developed as a continuously evolving prototype. The emphasis of the tool to this point has been on visualizing program structure and complexity via the automatic generation of Control Structure Diagrams (CSDs) and Complexity Profile Graphs (CPGs) from Ada source code [7]. The current release of GRASP provides generation of CSDs and CPGs together with other program comprehension aids such as syntax coloring, typographical enhancements, and source code folding [8]. When coupled with an appropriate compilation system such as GNAT, GRASP becomes an integrated graphical development environment for Ada 95, allowing users to edit, visualize, pretty-print, compile, link, execute and debug Ada software.The GRASP prototype for Ada was first made available to the public in January 1996. Since that time, thousands of copies of GRASP have been downloaded via anonymous file transfer protocol (FTP) and the World Wide Web (WWW) from educational, government, military and commercial sites, both in the United States and abroad. When it was released to the public, GRASP was also made available to users of the Auburn University College of Engineering computer network. GRASP is now used extensively throughout the computer science and engineering curriculum at Auburn University, in approximately three to five courses per quarter.
Differentiated end-to-end Internet services using a weighted proportional fair sharing TCP
Authors: Crowcroft Jon , Oechslin Philippe
Published: October 2004

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

The Technology Acceptance Model (TAM) suggests that the perceived usefulness (PU) and the perceived ease of use (PEOU) of an information system (IS) are major determinants of its use. Previous research has demonstrated the validity of this model across a wide variety of IS types. However, prior research has not identified antecedents of PU and there has been only limited research on the antecedents of PEOU. Consequently, research has provided little guidance to IS managers on methods to increase use by augmenting PU and PEOU.Viewing IS development as an instance of Social Exchange Theory (SET), this study proposes that IS managers can influence both the PU and the PEOU of an IS through a constructive social exchange with the user. One means of building and maintaining a constructive social exchange is through developer responsiveness. The results of this study, examining the adoption of an expert system, indeed support this notion. Specifically, developer responsiveness strongly influenced both PU and PEOU, but only indirectly affected actual behavior --- IS use --- in accordance with the predictions of SET. An extension of TAM based on SET is presented and the implications of this extended model are discussed from both a managerial and theoretical perspective.
An MIS course integrating information technology and organizational issues
Authors: Zack Michael H.
Published: October 2004

Integrating technologies and applications to provide better access to, and sharing of, corporate data and to coordinate enterprise-wide tasks and processes is a critical means to adding business value through information technology. Consequently, potential employers seek information systems professionals whose skills focus on the integration of information technologies, information resources, and business strategy. However, these companies also perceive that universities are not providing graduates the necessary integration skills.This paper describes a course, Business Systems Integration, that addresses the gap between the information systems integration skills that employers desire and those that universities teach. The course approaches information systems integration from three perspectives: 1) integrating information technologies, 2) integrating the content of the MIS curriculum, and 3) integrating organizations via cross-functional business processes. Attaining a practical level of knowledge about systems integration requires a sufficiently complex, real-world environment; thus the course relies on an extensive organizational simulation as the primary pedagogical method. That simulation is described in this paper.
What's up with downward collapse
Authors: Hemaspaandra Edith , Hemaspaandra Lane A. , Hempel Harald
Published: October 2004

During the past decade, nine papers have obtained increasingly strong consequences from the assumption that boolean or bounded-query hierarchies collapse. The final four papers of this nine-paper progression actually achieve downward collapse---that is, they show that high-level collapses induce collapses at (what before-the-fact seemed to be) lower complexity levels. For example, for each
k
≥ 2 it. is now known that if one query to σ
p
k
is as powerful as two queries to σ
p
k
(i.e., P
Σ[1]
= P
Σ[2]
), then PH = σ
p
k
. This article surveys the history, the results, and the method---the so-called easy-hard technique---of the just-mentioned nine-paper progression:1. J. Kadin. The polynomial time hierarchy collapses if the boolean hierarchy collapses.
SIAM Journal on Computing
, 17(6):1263--1282, 1988. Erratum appears in the same journal. 20(2):404.2. K. Wagner. Number-of-query hierarchies. Technical Report 158, Institut für Mathematik. Universität Augsburg, Augsburg, Germany, October 1987.3. K. Wagner. Number-of-query hierarchies. Technical Report 4. Institut für Informatik. Universität Würzburg, Würzburg, Germany, February 1989.4. R. Chang and J. Kadin. The boolean hierarchy and the polynomial hierarchy: A closer connection.
SIAM Journal on Computing
. 25(2):340--354. 1996.5. R. Beigel. R. Chang. and M. Ogiwara. A relationship between difference hierarchies and relativized polynomial hierarchies.
Mathematical Systems Theory
. 26(3):293--310, 1993.6. E. Hemaspaandra, L. Hemaspaandra. and H. Hempel. An upward separation in the polynomial hierarchy. Technical Report Math/Inf/96/15, Institut für Informatik, Friedrich-Schiller-Universität Jena, Jena, Germany, June 1996.7. E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. A downward collapse within the polynomial hierarchy.
SIAM Journal on Computing
, 28(2):383--393, 1999.8. H. Buhrman and L. Fortnow. Two queries. In
Proceedings of the 13th Annual IEEE Conference on Computational Complexity
. 13--19. IEEE Computer Society Press, June 1998.9. E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. Translating equality downwards. Technical Report TR-657. Department of Computer Science, University of Rochester, Rochester, NY. April 1997.
On a theory of computing symposia
Authors: Blum Avrim , Raghavan Prabhakar
Published: October 2004

We consider the problem of scheduling a conference to achieve the benefits in time-compression of parallel sessions, but without the associated high degree of conflict between talks. We describe a randomized construction meeting these goals that we analyze based on an expansion property of an associated graph. We also give algorithms for attendees scheduling their time within such a conference, and algorithms for verifying a proposed conference schedule. Finally, we present simulation results for typical conference sizes.
A new family of authentication protocols
Authors: Anderson Ross , Bergadano Francesco , Crispo Bruno , Lee Jong-Hyeon , Manifavas Charalampos , Needham Roger
Published: October 2004

We present a related family of authentication and digital signature protocols based on symmetric cryptographic primitives which perform substantially better than previous constructions. Previously, one-time digital signatures based on hash functions involved hundreds of hash function computations for each signature; we show that given online access to a timestamping service, we can sign messages using only two computations of a hash function. Previously, techniques to sign infinite streams involved one such one-time signature for each message block; we show that in many realistic scenarios a small number of hash function computations is sufficient. Previously, the Diffie Hellman protocol enabled two principals to create a confidentiality key from scratch: we provide an equivalent protocol for integrity, which enables two people who do not share a secret to set up a securely serialised channel into which attackers cannot subsequently intrude. In addition to being of potential use in real applications, our constructions also raise interesting questions about the definition of a digital signature, and the relationship between integrity and authenticity.
ID-based secret-key cryptography
Authors: Joye Marc , Yen Sung-Ming
Published: October 2004

This paper introduces
ID-based secret-key cryptography,
in which secret keys are privately and uniquely binded to an identity. This enables to extend public-key cryptography features at the high throughput rate of secret-key cryptography. As applications, efficient login protocols, an enhanced version of Kerberos, and an ID-based MAC algorithm are presented.ID-based systems were initially developed in the context of public-key cryptography by removing the need of explicit public keys. The idea was to derive, in a publicly known way, a public key from an identity. Similarly, in secret-key cryptography, ID-based systems allow authorized entities to derive a secret key from an identity. So, large databases maintaining the correspondence between an identity and the corresponding secret key are no longer required, resulting in better performances and higher security.
Synchronization in portable device drivers
Authors: Ryan Stein J.
Published: October 2004

We present an overview of the synchronization mechanisms offered to device drivers by different operating systems and develop a foundation for writing portable device drivers by unifying these mechanisms. Our foundation has been used to implement an efficient portable cluster adapter driver for three different operating systems as part of the runtime system for a heterogeneous PC cluster. We show how our portable synchronization mechanisms map to the native synchronization mechanisms of these three operating systems.
On the generation and use of TCP acknowledgments
Authors: Allman Mark
Published: October 2004

This paper presents a simulation study of various TCP acknowledgment generation and utilization techniques. We investigate the standard version of TCP and the two standard acknowledgment strategies employed by receivers: those that acknowledge each incoming segment and those that implement delayed acknowledgments. We show the delayed acknowledgment mechanism hurts TCP performance, especially during slow start. Next we examine three alternate mechanisms for generating and using acknowledgments designed to mitigate the negative impact of delayed acknowledgments. The first method is to generate delayed ACKs only when the sender is not using the slow start algorithm. The second mechanism, called
byte counting
, allows TCP senders to increase the amount of data being injected into the network based on the amount of data acknowledged rather than on the number of acknowledgments received. The last mechanism is a limited form of byte counting. Each of these mechanisms is evaluated in a simulated network with no competing traffic, as well as a dynamic environment with a varying amount of competing traffic. We study the costs and benefits of the alternate mechanisms when compared to the standard algorithm with delayed ACKs.
On the efficient implementation of fair non-repudiation
Authors: You Cheng-Hwee , Zhou Jianying , Lam Kwok-Yan
Published: October 2004

Due to the explosive growth of electronic businesses carried on the Internet, non-repudiation services turn out to be increasingly important. Non-repudiation services protect the transacting parties against any false denial that a particular event or action has taken place, in which evidence will be generated, collected and maintained to enable the settlement of disputes. Several fair non-repudiation protocols have been proposed, which support non-repudiation of origin and non-repudiation of receipt while neither the originator nor the recipient can gain an advantage by quitting prematurely or otherwise misbehaving during a transaction. However, a critical issue on how to maintain the validity of non-repudiation evidence efficiently during and after a transaction was not considered. This paper uses the idea of evidence chaining to address such a problem.
OSI distributed transaction processing commitment optimizations
Authors: Banks Richard , Furniss Peter , Heien Klaus , Wiehle H. Rüdiger
Published: October 2004

This paper briefly summarizes the work towards the final version of 'Distributed Transaction Processing' (OSI TP). Several well-known optimizations of the presumed abort protocol are introduced: dynamic flow of READY-messages, a one-phase protocol, a read-only extension. Moreover, some useful extensions such as containment of heuristic decisions and reporting of the completion status of a transaction are presented. The requirements and the functionality are discussed especially from the user's point of view. Finally, the evolving requirements for distributed transaction processing are discussed given the increasing number of applications on the Internet (Electronic Commerce).
Comparing lower bounds on messages and rounds for two classes of key establishment protocols
Authors: Mathuria Anish
Published: October 2004

An important requirement in designing protocols for key establishment is to provide assurance to protocol participants that a session key is fresh. This paper compares lower bounds on messages and rounds for two classes of protocols based on fundamentally different methods for achieving session key freshness.
Writing and editing complexity theory
Authors: Hemaspaandra Lane A. , Selman Alan L.
Published: October 2004

Each researcher should have a full shelf---physical or virtual---of books on writing and editing prose. Though we make no claim to any special degree of expertise, we recently edited a book of complexity theory surveys [HS97], and in doing so we were brought into particularly close contact with the subject of this article, and with a number of the excellent resources available to writers and editors. In this article, we list some of these resources, and we also relate some of the adventures we had as our book moved from concept to reality.
SCR algorithm
Authors: Xiao-Hui Wei , Jiu-Bin Ju
Published: October 2004

Fault-tolerance is very important in cluster computing. Many famous cluster-computing systems have implemented fault-tolerance by using checkpoint/restart mechanism. But existent checkpointing algorithms can not restore the states of a file system when roll-backing the running of a program, so there are many restrictions on file accesses in existent fault-tolerance systems. SCR algorithm, an algorithm based on atomic operation and consistent schedule, which can restore the states of file systems, is present in this paper. In SCR algorithm, system calls on file sytems are classified into idempotent operations and non-idempotent operations. A non-idempotent operation modifies a file system's states, and an idempotent operation does not. SCR algorithm dynamically follows the tracks of a program's running, logs each non-idempotent operation used by the program and the information that can restore the operation in disks. When checkpointing roll-backing the program, SCR algorithm will revert the file system states to the last checkpoint time. By using SCR algorithm, users are allowed to use any file operation in their programs.