bluuebunny/crossref_metadata_2025 huggingface dataset:
A blueprint for introducing disruptive technology into the Internet
Authors: Peterson Larry , Anderson Tom , Culler David , Roscoe Timothy
Published: October 2004

This paper argues that a new class of geographically distributed network services is emerging, and that the most effective way to design, evaluate, and deploy these services is by using an overlay-based testbed. Unlike conventional network testbeds, however, we advocate an approach that supports both researchers that want to develop new services, and clients that want to use them. This dual use, in turn, suggests four design principles that are not widely supported in existing testbeds: services should be able to run continuously and access a slice of the overlay's resources, control over resources should be distributed, overlay management services should be unbundled and run in their own slices, and APIs should be designed to promote application development. We believe a testbed that supports these design principles will facilitate the emergence of a new
service-oriented network architecture
. Towards this end, the paper also briefly describes PlanetLab, an overlay network being designed with these four principles in mind.
Feedback based routing
Authors: Zhu Dapeng , Gritter Mark , Cheriton David R.
Published: October 2004

In this paper, we describe the problems that affect availability in BGP, such as vulnerability to attacks, slow convergence time, and lack of scalability. These problems arise from the basic assumption of BGP: every router has to cooperate to make routing work. We propose a new routing system, feedback based routing, which bifurcates structural information and dynamic information. Only structural information is propagated. Dynamic information is discovered by the routers based on feedback and probes. Routing decisions are made based on the dynamic information. We argue that this system is resilient to minority compromises in the infrastructure, provides higher availability than BGP, and can scale to the size of the Internet of the future.
Secure traceroute to detect faulty or malicious routing
Authors: Padmanabhan Venkata N. , Simon Daniel R.
Published: October 2004

Network routing is vulnerable to disruptions caused by malfunctioning or malicious routers that draw traffic towards themselves but fail to correctly forward the traffic. The existing approach to addressing this problem is to secure the routing protocol by having it validate routing updates, i.e., verify their authenticity, accuracy, and/or consistency. In this paper, we argue that it is also important to ensure the robustness of packet forwarding itself. To this end, we propose a different approach, the central idea of which is a
secure traceroute
protocol that enables end hosts or routers to detect and locate the source of (arbitrarily severe) routing misbehaviors, so that appropriate action can be taken.
pSearch
Authors: Tang Chunqiang , Xu Zhichen , Mahalingam Mallik
Published: October 2004

We describe an efficient peer-to-peer information retrieval system, pSearch; that supports state-of-the-art content- and semantic-based full-text searches. pSearch avoids the scalability problem of existing systems that employ centralized indexing, or index/query flooding. It also avoids the nondeterminism that is exhibited by heuristic-based approaches. In pSearch; documents in the network are organized around their vector representations (based on modern document ranking algorithms) such that the search space for a given query is organized around related documents, achieving both efficiency and accuracy.
A case for associative peer to peer overlays
Authors: Cohen Edith , Fiat Amos , Kaplan Haim
Published: October 2004

The success of a P2P file-sharing network highly depends on the scalability and versatility of its search mechanism. Two particularly desirable search features are scope (ability to find infrequent items) and support for partial-match queries (queries that contain typos or include a subset of keywords). While centralized-index architectures (such as Napster) can support both these features, existing decentralized architectures seem to support at most one: prevailing protocols (such as Gnutella and FastTrack) support partial-match queries, but since search is unrelated to the query, they have limited scope. Distributed Hash Tables (such as CAN and CHORD) constitute another class of P2P architectures promoted by the research community. DHTs couple index location with the item's hash value and are able to provide scope but can not effectively support partial-match queries; another hurdle in DHT deployment is their tight control the overlay structure and data placement which makes them more sensitive to failures.Associative overlays are a new class of decentralized P2P architectures. They are designed as a collection of unstructured P2P networks (based on popular architectures such as gnutella or FastTrack), and the design retains many of their appealing properties including support for partial match queries, and relative resilience to peer failures. Yet, the search process is orders of magnitude more effective in locating rare items. Our design exploits associations inherent in human selections to steer the search process to peers that are more likely to have an answer to the query.
Design guidelines for robust Internet protocols
Authors: Anderson Tom , Shenker Scott , Stoica Ion , Wetherall David
Published: October 2004

Robustness has long been a central design goal of the Internet. Much of the initial effort towards robustness focusedon the "fail-stop" model, where node failures are complete and easily detectable by other nodes. The Internet is quite robust against such failures, routinely surviving various catastrophes with only limited outages. This robustness is largely due to the widespread belief in a set of guidelines for critical design decisions such as where to initiate recovery and how to maintain state.However, the Internet remains extremely vulnerable to more arbitrary failures where, through either error or malice, a node issues syntactically correct responses that are not semantically correct. Such failures, some as simple as misconfigured routing state, can seriously undemnine the functioning of the Internet. With the Internet playing such a central role in the global telecommunications infrastructure, this level of vulnerability is no longer acceptable.In this paper we argue that to make the Internet more robust to these kinds of arbitrary failures, we need to change the way we design network protocols. To this end, we propose a set of six design guidelines for improving the network protocol design. These guidelines emerged from a study of past examples of failures, and determining what could have been done to prevent the problem from occurring in the first place. The unifying theme behind the various guidelines is that we need to design protocols more defensively, expecting malicious attack, misimplementation, and misconfiguration at every turn.
MCTS nucleus
Authors: Brown Ralph R.
Published: October 2004

The goals of the total MCTS System are stated in terms of capabilities which the customer tasks should be allowed to exercise. Treating these as premises, several derivative goals were deduced for the MCTS System, and these dictated the structure of the operating system and the nucleus. The deductions are exhibited, and the structure of the nucleus is derived. The body of this paper does not reference the hardware description of the computer on which the nucleus was implemented, and indeed the structure of the MCTS nucleus is philosophically hardware independent, except that it assumes a large scale processor with virtual memory address translation hardware, as is explained in the paper.The nucleus consists of three separate modules which cooperate to provide the environment in which the MCTS system operates. In that environment the individual components of the system execute as separate subtasks within a single task, the MCTS system task. They are written in a PL/I-like language; they are interruptible, yet each is run to its completion, thereby eliminating the need to synchronize between subtasks; they are suspended during requested I/O operations thus making I/O appear to be instantaneous; and their creation, modification, and checkout proved to be easy and fast.
On unifying module interfaces
Authors: Stroustrup Bjarne
Published: October 2004

This paper presents the outline of a uniform interface mechanism for activating different kinds of modules, e.g. processes, monitors, and procedures. The usefulness of such an interface in the design of modules and in the tuning of a system is discussed. The overheads involved in using it are explained, together with some implications that its general use has on the system structure.
Performance evaluation under Unix and a study of PDP-II instruction usage
Authors: Rose Greg
Published: October 2004

The Unix operating system has been modified to allow the gathering of statistics of program performance and instruction usage. A procedure to produce instruction usage statistics is outlined, and a selection of statistics gathered by this method is displayed. The statistics are presented as food for thought, and only tentative conclusions are drawn. Some typical aspects and tentative conclusions specific to the computer, the operating system, and the monitor are then presented.
An operating system case study
Authors: Lions J.
Published: October 2004

A case study approach for teaching a course on operating systems is described and evaluated. The choice of a particular system, UNIX, for case study is explained and evaluated. The wider ramifications of this system for the Computer Science curriculum at the University of New South Wales are also mentioned.
From the chair
Authors: Sipior Janice C. , Schatzberg Laurie , Leidner Dorothy , Niederman Fred , Lending Diane
Published: October 2004

Greetings! I am happy to report that the ACM- SIGMIS CPR (Computer Personnel Research) 2003 Conference held in Philadelphia, PA, April 10- 12, 2003 was a success! Please join me in extending a warm thank you to the members of the Conference Committee for all their efforts:

Conference Chair:
Munir Mandviwalla, Temple University (mandviwa@ temple. edu)

Program Chair:
Eileen Trauth, The Pennsylvania State University (etrauth@ ist. psu. edu)

Conference Treasurer:
Diane Lending, James Madison University (lendindc@ jmu. edu)

Publicity Chair:
Sandra Slaughter, Carnegie Mellon University (sandras@ andrew. cmu. edu)

Local Arrangements Chair:
Anat Hovav, Temple University (ahovav@ sbm. temple. edu)

The first annual SIGMIS/ CPR Business Meeting, for the merged SIGs, was held on Saturday afternoon, immediately after the close of the conference. Discussions centered on consolidating the newly joined SIGMIS/ CPR. Fred Niederman continues in his role as CPR Committee Chair. Diane Lending is the newly appointed Information Director. Special sections in Data Base will be devoted to CPR. Finally, SIGMIS is committed to preserving and developing the CPR Conference.A Preliminary Outcome Report for the CPR 2003 Conference was presented by Munir Mandviwalla, CPR 2003 Conference Chair. A Progress Report for the CPR 2004 Conference was given by Suzie Weisband, CPR 2004 Program Chair. A Progress Report, on naming the Best Paper Award at the CPR conference for Magid Igbaria, was presented by Fred Niederman.Plans for next year's CPR 2004 Conference, to be held in Arizona, are now underway. All members are welcome. Please contact the Conference Chair: Mohan Tanniru, University of Arizona, mtanniru@ eller. arizona. edu for more information.The meeting concluded with a brainstorming session on activities and initiatives to better serve the members. We encourage and welcome your suggestions. Please feel free to contact any one of us with your input or ideas. Have a great summer!
The e-tailer's dilemma
Authors: Lee Seung C. , Brandyberry Alan A.
Published: October 2004

The e-tailer's dilemma refers to the difficulty web-based retailers (or e-tailers) have experienced in achieving profitability. The problem centers on the need to increase effective (purchasing) visitors and on the increased costs associated with the electronic commerce infrastructure upgrades necessary to service these additional visitors. This may lead e-tailers into a cycle of achieving increased revenues that are merely offset by rising costs. There are ample examples where commonly employed metrics (unique visitors, page views, sales, etc.) suggest success while companies struggle to obtain profitability. This paper examines several aspects of this dilemma. The formalization of both the tangible and intangible aspects of an electronic commerce infrastructure is proposed. Next, an intuitive, utility-based model to help describe and interpret e-tail visitor dynamics is developed. Finally, a visitor function model of e-tail profitability incorporating necessary infrastructure improvements and visitor characteristics is developed.
Parallel speedup of sequential machines: a defense of parallel computation thesis
Authors: Parberry I
Published: October 2004

It is reasonable to expect parallel machines to be faster than sequential ones. But exactly how much faster do we expect them to be? Various authors have observed that an exponential speedup is possible if sufficiently many processors are available. One such author has claimed (erroneously) that this is a counterexample to the parallel computation thesis. We show that even more startling speedups are possible. In fact, if enough processors are used, any recursive function can be computed in constant time. Although such machines clearly do not obey the parallel computation thesis, we argue that they still provide evidence in favour of it. In contrast, we show that an arbitrary polynomial speedup of sequential machines is possible on a model which satisfies the parallel computation thesis. If, as widely conjectured, P⊈POLYLOGSPACE, then there can be no exponential speedup on such a model.
Defensive programming
Authors: Qie Xiaohu , Pang Ruoming , Peterson Larry
Published: October 2004

This paper describes a toolkit to help improve the robustness of code against DoS attacks. We observe that when developing software, programmers primarily focus on functionality. Protecting code from attacks is often considered the responsibility of the OS, firewalls and intrusion detection systems. As a result, many DoS vulnerabilities are not discovered until the system is attacked and the damage is done. Instead of reacting to attacks after the fact, this paper argues that a better solution is to make software
defensive
by systematically injecting protection mechanisms into the code itself. Our toolkit provides an API that programmers use to annotate their code. At runtime, these annotations serve as both sensors and actuators: watching for resource abuse and taking the appropriate action should abuse be detected. This paper presents the design and implementation of the toolkit, as well as evaluation of its effectiveness with three widely-deployed network services.
CMC
Authors: Musuvathi Madanlal , Park David Y. W. , Chou Andy , Engler Dawson R. , Dill David L.
Published: October 2004

Many system errors do not emerge unless some intricate sequence of events occurs. In practice, this means that most systems have errors that only trigger after days or weeks of execution. Model checking [4] is an effective way to find such subtle errors. It takes a simplified description of the code and exhaustively tests it on all inputs, using techniques to explore vast state spaces efficiently. Unfortunately, while model checking systems code would be wonderful, it is almost never done in practice: building models is just too hard. It can take significantly more time to write a model than it did to write the code. Furthermore, by checking an abstraction of the code rather than the code itself, it is easy to miss errors.The paper's first contribution is a new model checker, CMC, which checks C and C++ implementations directly, eliminating the need for a separate abstract description of the system behavior. This has two major advantages: it reduces the effort to use model checking, and it reduces missed errors as well as time-wasting false error reports resulting from inconsistencies between the abstract description and the actual implementation. In addition, changes in the implementation can be checked immediately without updating a high-level description.The paper's second contribution is demonstrating that CMC works well on real code by applying it to three implementations of the Ad-hoc On-demand Distance Vector (AODV) networking protocol [7]. We found 34 distinct errors (roughly one bug per 328 lines of code), including a bug in the AODV specification itself. Given our experience building systems, it appears that the approach will work well in other contexts, and especially well for other networking protocols.
Cooperative I/O
Authors: Weissel Andreas , Beutel Björn , Bellosa Frank
Published: October 2004

In this paper we demonstrate the benefits of application involvement in operating system power management. We present Coop-I/O, an approach to reduce the power consumption of devices while encompassing all levels of the system---from the hardware and OS to a new interface for cooperative I/O that can be used by energy-aware applications. We assume devices which can be set to low-power operation modes if they are not accessed and where switching between modes consumes additional energy, e.g. devices with rotating components or network devices consuming energy for the establishment and shutdown of network connections. In these cases frequent mode switches should be avoided.With Coop-I/O, applications can declare open, read and write operations as
deferrable
and even
abortable
by specifying a time-out and a cancel flag. This information enables the operating system to delay and batch requests so that the number of power mode switches is reduced and the device can be kept longer in a low-power mode. We have deployed our concept to the IDE hard disk driver and Ext2 file system of Linux and to typical real-life programs so that they make use of the new cooperative I/O functions. With energy savings of up to 50%, the experimental results demonstrate the benefits of the concept. We will show that Coop-I/O even outperforms the "oracle" shutdown policy which defines the lower bound in power consumption if the timing of requests can not be influenced.
Fine-grained network time synchronization using reference broadcasts
Authors: Elson Jeremy , Girod Lewis , Estrin Deborah
Published: October 2004

Recent advances in miniaturization and low-cost, low-power design have led to active research in large-scale networks of small, wireless, low-power sensors and actuators. Time synchronization is critical in sensor networks for diverse purposes including sensor data fusion, coordinated actuation, and power-efficient duty cycling. Though the clock accuracy and precision requirements are often stricter than in traditional distributed systems, strict energy constraints limit the resources available to meet these goals.We present
Reference-Broadcast Synchronization
, a scheme in which nodes send reference beacons to their neighbors using physical-layer broadcasts. A reference broadcast does not contain an explicit timestamp; instead, receivers use its arrival time as a point of reference for comparing their clocks. In this paper, we use measurements from two wireless implementations to show that removing the sender's nondeterminism from the critical path in this way produces high-precision clock agreement (1.85 ± 1.28μsec, using off-the-shelf 802.11 wireless Ethernet), while using minimal energy. We also describe a novel algorithm that uses this same broadcast property to federate clocks across broadcast domains with a slow decay in precision (3.68 ± 2.57μsec after 4 hops). RBS can be used without external references, forming a precise relative timescale, or can maintain microsecond-level synchronization to an external timescale such as UTC. We show a significant improvement over the Network Time Protocol (NTP) under similar conditions.
Scale and performance in the Denali isolation kernel
Authors: Whitaker Andrew , Shaw Marianne , Gribble Steven D.
Published: October 2004

This paper describes the Denali isolation kernel, an operating system architecture that safely multiplexes a large number of untrusted Internet services on shared hardware. Denali's goal is to allow new Internet services to be "pushed" into third party infrastructure, relieving Internet service authors from the burden of acquiring and maintaining physical infrastructure. Our isolation kernel exposes a virtual machine abstraction, but unlike conventional virtual machine monitors, Denali does not attempt to emulate the underlying physical architecture precisely, and instead modifies the virtual architecture to gain scale, performance, and simplicity of implementation. In this paper, we first discuss design principles of isolation kernels, and then we describe the design and implementation of Denali. Following this, we present a detailed evaluation of Denali, demonstrating that the overhead of virtualization is small, that our architectural choices are warranted, and that we can successfully scale to more than 10,000 virtual machines on commodity hardware.
Integrated resource management for cluster-based Internet services
Authors: Shen Kai , Tang Hong , Yang Tao , Chu Lingkun
Published: October 2004

Client request rates for Internet services tend to be bursty and thus it is important to maintain efficient resource utilization under a wide range of load conditions. Network service clients typically seek services interactively and maintaining reasonable response time is often imperative for such services. In addition, providing differentiated service qualities and resource allocation to multiple service classes can also be desirable at times. This paper presents an integrated resource management framework (part of
Neptune system
) that provides flexible service quality specification, efficient resource utilization, and service differentiation for cluster-based services. This framework introduces the metric of
quality-aware service yield
to combine the overall system efficiency and individual service response time in one flexible model. Resources are managed through a two-level request distribution and scheduling scheme. At the cluster level, a fully decentralized request distribution architecture is employed to achieve high scalability and availability. Inside each service node, an adaptive scheduling policy maintains efficient resource utilization under a wide range of load conditions. Our trace-driven evaluations demonstrate the performance, scalability, and service differentiation achieved by the proposed techniques.
An integrated experimental environment for distributed systems and networks
Authors: White Brian , Lepreau Jay , Stoller Leigh , Ricci Robert , Guruprasad Shashi , Newbold Mac , Hibler Mike , Barb Chad , Joglekar Abhijeet
Published: October 2004

Three experimental environments traditionally support network and distributed systems research: network emulators, network simulators, and live networks. The continued use of multiple approaches highlights both the value and inadequacy of each. Netbed, a descendant of Emulab, provides an experimentation facility that integrates these approaches, allowing researchers to configure and access networks composed of emulated, simulated, and wide-area nodes and links. Netbed's primary goals are
ease of use, control
, and
realism
, achieved through consistent use of virtualization and abstraction.By providing operating system-like services, such as resource allocation and scheduling, and by virtualizing heterogeneous resources, Netbed acts as a virtual machine for network experimentation. This paper presents Netbed's overall design and implementation and demonstrates its ability to improve experimental automation and efficiency. These, in turn, lead to new methods of experimentation, including automated parameter-space studies within emulation and straightforward comparisons of simulated, emulated, and wide-area scenarios.
Scalability and accuracy in a large-scale network emulator
Authors: Vahdat Amin , Yocum Ken , Walsh Kevin , Mahadevan Priya , Kostić Dejan , Chase Jeff , Becker David
Published: October 2004

This paper presents ModelNet, a scalable Internet emulation environment that enables researchers to deploy unmodified software prototypes in a configurable Internet-like environment and subject them to faults and varying network conditions. Edge nodes running user-specified OS and application software are configured to route their packets through a set of ModelNet core nodes, which cooperate to subject the traffic to the bandwidth, congestion constraints, latency, and loss profile of a target network topology.This paper describes and evaluates the ModelNet architecture and its implementation, including novel techniques to balance emulation accuracy against scalability. The current ModelNet prototype is able to accurately subject thousands of instances of a distrbuted application to Internet-like conditions with gigabits of bisection bandwidth. Experiments with several large-scale distributed services demonstrate the generality and effectiveness of the infrastructure.
TCP Nice
Authors: Venkataramani Arun , Kokku Ravi , Dahlin Mike
Published: October 2004

Many distributed applications can make use of large
background transfers
--transfers of data that humans are not waiting for--to improve availability, reliability, latency or consistency. However, given the rapid fluctuations of available network bandwidth and changing resource costs due to technology trends, hand tuning the aggressiveness of background transfers risks (1) complicating applications, (2) being too aggressive and interfering with other applications, and (3) being too timid and not gaining the benefits of background transfers. Our goal is for the operating system to manage network resources in order to provide a simple abstraction of near zero-cost background transfers. Our system, TCP Nice, can provably bound the interference inflicted by background flows on foreground flows in a restricted network model. And our microbenchmarks and case study applications suggest that in practice it interferes little with foreground flows, reaps a large fraction of spare network bandwidth, and simplifies application construction and deployment. For example, in our prefetching case study application, aggressive prefetching improves demand performance by a factor of three when Nice manages resources; but the same prefetching hurts demand performance by a factor of six under standard network congestion control.
Optimizing the migration of virtual computers
Authors: Sapuntzakis Constantine P. , Chandra Ramesh , Pfaff Ben , Chow Jim , Lam Monica S. , Rosenblum Mendel
Published: October 2004

This paper shows how to quickly move the state of a running computer across a network, including the state in its disks, memory, CPU registers, and I/O devices. We call this state a
capsule
. Capsule state is hardware state, so it includes the entire operating system as well as applications and running processes.We have chosen to move
x
86 computer states because
x
86 computers are common, cheap, run the software we use, and have tools for migration. Unfortunately,
x
86 capsules can be large, containing hundreds of megabytes of memory and gigabytes of disk data. We have developed techniques to reduce the amount of data sent over the network: copy-on-write disks track just the updates to capsule disks, "ballooning" zeros unused memory, demand paging fetches only needed blocks, and hashing avoids sending blocks that already exist at the remote end. We demonstrate these optimizations in a prototype system that uses VMware GSX Server virtual, machine monitor to create and run
x
86 capsules. The system targets networks as slow as 384 kbps.Our experimental results suggest that efficient capsule migration can improve user mobility and system management. Software updates or installations on a set of machines can be accomplished simply by distributing a capsule with the new changes. Assuming the presence of a prior capsule, the amount of traffic incurred is commensurate with the size of the update or installation package itself. Capsule migration makes it possible for machines to start running an application within 20 minutes on a 384 kbps link, without having to first install the application or even the underlying operating system. Furthermore, users' capsules can be migrated during a commute between home and work in even less time.
Luna
Authors: Hawblitzel Chris , von Eicken Thorsten
Published: October 2004

Extensible Java systems face a difficult trade-off between sharing and protection. On one hand, Java's ability to run different protection domains in a single virtual machine enables domains to share data easily and communicate without address space switches. On the other hand, unrestricted sharing blurs the boundaries between protection domains, making it difficult to terminate domains and enforce restrictions on resource usage. Existing solutions to these problems restrict sharing in an ad-hoc fashion, ruling out many desirable programming styles.This paper presents an extension to Java's type system that systematically addresses the issues of data sharing, revocation, thread control, and resource control. Multiple
tasks
running in a single virtual machines share data using special
remote pointers
, which have different types from local pointers. The distinction between local and remote pointers allows the Java runtime system to mediate the communication between tasks without slowing down operations on ordinary pointers. The extensions to Java are implemented by a system called Luna, based on the Guavac and Marmot compilers, extended with special optimizations to support both fast inter-task communication and dynamic access control. The paper describes two applications written in Luna: a simple extensible web server, and an extension of the Squid web cache to support dynamic content generation.
Commercially viable active networking
Authors: Eichert Stuart , Ertugay Osman N. , Nessett Dan , Vobbilisetty Suresh
Published: October 2004

Active Networking is a new technology receiving significant attention from the research community. To this point, however, it has not been examined from the perspective of commercial viability. This paper presents an analysis of active networking issues with a view to its possible uses in a commercial environment. It then describes a prototype system built to address these issues.
LND
Authors: Mao Yun , Zhang Youhui , Wang Dongsheng , Zheng Weimin
Published: October 2004

The expensive overhead of synchronous I/O has now become the bottleneck of increasing efficiency of data storage in transaction-based systems. This paper proposes a multi-tier storage device, the LND (Local-Network Ram- Disk) device, which uses idle memories and disks in NOW (Network of Workstations) as persistent repositories so that access latency is transformed from magnetic disk seek-and-transfer latency to the sum of network transfer latency, memory write latency, and asynchronous I/O latency. Two fast data consistency protocols based on multicast technique are also introduced to improve performance without sacrificing reliability. Experimental results show that the LND device is one order of magnitude faster than traditional disks in synchronous I/O performance. Moreover, a fault tolerant recovery algorithm is proposed to protect the system from various kinds of failures and to facilitate quick recovery from crashes.
Habitat monitoring
Authors: Cerpa Alberto , Elson Jeremy , Estrin Deborah , Girod Lewis , Hamilton Michael , Zhao Jerry
Published: October 2004

As new fabrication and integration technologies reduce the cost and size of micro-sensors and wireless interfaces, it becomes feasible to deploy densely distributed wireless networks of sensors and actuators. These systems promise to revolutionize biological, earth, and environmental monitoring applications, providing data at granularities unrealizable by other means. In addition to the challenges of miniaturization, new system architectures and new network algorithms must be developed to transform the vast quantity of raw sensor data into a manageable stream of high-level data. To address this, we propose a tiered system architecture in which data collected at numerous, inexpensive sensor nodes is filtered by local processing on its way through to larger, more capable and more expensive nodes.We briefly describe Habitat monitoring as our motivating application and introduce initial system building blocks designed to support this application. The remainder of the paper presents details of our experimental platform.
Review of traffic scheduler features on general purpose platforms
Authors: Magaña Eduardo , Izkue Edurne , Villadangos Jesús
Published: October 2004

In this study, we review the features of a traffic scheduler running on a general-purpose platform, specifically a PC with a Linux operating system. The traffic scheduler was configured to manage a CBQ (
Class Based Queueing
) queue discipline, and by means of a series of experiments, we proved that the limitations of the system are due to the accuracy of the clock. After we modified this factor, we reviewed the features of the scheduler again. We were able to prove that the features of the scheduler improve greatly at the expense of a very small increase (around 10%) in the use of the system's CPU.
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 touters 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.
On estimating end-to-end network path properties
Authors: Allman Mark , Paxson Vern
Published: October 2004

The more information about current network conditions available to a transport protocol, the more efficiently it can use the network to transfer its data. In networks such as the Internet, the transport protocol must often form its own estimates of network properties based on measurements performed by the connection endpoints. We consider two basic transport estimation problems: determining the setting of the retransmission timer (RTO) for a reliable protocol, and estimating the bandwidth available to a connection as it begins. We look at both of these problems in the context of TCP, using a large TCP measurement set [Pax97b] for trace
MMTP
Authors: Magalhaes Luiz , Kravets Robin
Published: October 2004

Multimedia data has special requirements that are hard to be met on mobile hosts due to potentially low bandwidth and disruptions due to host mobility. Such limited communication capabilities of mobile hosts can be offset by the simultaneous use of multiple link layer technologies. MMTP is a member of a suite of protocols that share the novel characteristic of aggregating bandwidth from multiple link-layer channels. The use of multiple channels to transport user data provides five key benefits: (1) a fatter pipe,(2) a fast feedback path, (3) the retransmission of selected lost messages, without delaying the playout of the data stream, (4) less sensitivity to minor bandwidth fluctuations on any one individual channel, and (5) smooth vertical handoffs for active data streams.MMTP is a rate-based protocol designed for transferring multimedia data on mobile systems, and makes simultaneous use of every communication channel available to send data at the required rate. Transmission in MMTP is governed by two mechanisms. The first is a set of rate control protocols associated with each outgoing channel. The second is a scheduling algorithm that places incoming packets on the appropriate channel. MMTP is link-layer aware protocol that uses bandwidth estimation for congestion control, and relays to the application information needed for rate adaptation. In this paper, we show that the quality of data transmission can be improved through the use of MMTP through experimental comparisons with data transmitted via UDP. We also demonstrate the economy of bandwidth: MMTP only sends packets that it estimates will arrive within the packet deadline, thus decreasing the number of late packets that will be discarded at the receiver.
A user-controlled synchronization method
Authors: Chambers John M.
Published: October 2004

In any system that allows the sharing of facilities between independently-running processes, it is occasionally necessary to 'synchronize' references to shared facilities. A method is presented here that enables any set of processes to achieve such synchronization without any aid from the executive system or special hardware. Only normal load and store operations on two arrays of shared data are required. No overhead is required for unsynchronized operations. And dead-locks are avoided, since it is never necessary to 'block' a process.This method can be viewed as a generalization of Dijkstra's example [D3], though the connection may not be obvious at first glance.
A study of storage partitioning using a mathematical model of locality
Authors: Coffman E. G. , Ryan Thomas A.
Published: October 2004

Both fixed and dynamic storage partitioning procedures are examined for use in multiprogramming systems. The storage requirement of programs is modeled as a stationary Gaussian process. Experiments justifying this model are described. By means of this model dynamic storage partitioning is shown to provide substantial increases in storage utilization and operating efficiency over fixed partitioning.
Process synchronization by counter variables
Authors: Gerber A. J.
Published: October 2004

A new method for expressing synchronization is presented which derives from several concepts in existing notational schemes. Synchronization conditions are expressed in terms of (integer) counters which are incorporated into the definitions of data objects shared by several asynchronous processes. It is shown that the method is at least as powerful as PV-type synchronization, and the solutions to some "classical" problems are presented using the notation.
Abstract machines modelling network control systems
Authors: Hopper K. , Kugler H. J. , Unger C.
Published: October 2004

A major problem in designing computer systems is to match the needs of all types of computer users with the real resources available. The concept of an abstract machine working for the user is introduced to overcome this problem. The applicability of this concept in a wide variety of practical environments leads to the development of a proposed standard architecture for network control systems.
On the duality of operating system structures
Authors: Lauer Hugh C. , Needham Roger M.
Published: October 2004

Many operating system designs can be placed into one of two very rough categories, depending upon how they implement and use the notions of process and synchronization. One category, the "Message-oriented System," is characterized by a relatively small, static number of processes with an explicit message system for communicating among them. The other category, the "Procedure-oriented System," is characterized by a large, rapidly changing number of small processes and a process synchronization mechanism based on shared data.In this paper, it is demonstrated that these two categories are duals of each other and that a system which is constructed according to one model has a direct counterpart in the other. The principal conclusion is that neither model is inherently preferable, and the main consideration for choosing between them is the nature of the machine architecture upon which the system is being built, not the application which the system will ultimately support.
A penetration analysis of the Michigan Terminal System
Authors: Hebbard B. , Grosso P. , Baldridge T. , Chan C. , Fishman D. , Goshgarian P. , Hilton T. , Hoshen J. , Hoult K. , Huntley G. , Stolarchuk M. , Warner L.
Published: October 2004

The successful penetration testing of a major time-sharing operating system is described. The educational value of such a project is stressed, and principles of methodology and team organization are discussed as well as the technical conclusions from the study.
A hardware implementation of capability-based addressing
Authors: Myers G. J. , Buckingham B. R. S.
Published: October 2004

The SWARD architecture, an experimental higher-level architecture, contains the naming and protection concept of capability-based addressing. After discussing the merits of capability-based addressing, its general representation in the SWARD architecture is discussed. The initial representation of capability-based addressing in the architecture led to a set of problems; these problems are described, as well as their solutions. Finally, the implementation of capabilities by the processor is discussed.
Using type-extension to organize virtual-memory mechanisms
Authors: Janson P. A.
Published: October 2004

Much effort is currently being devoted to producing computer systems that are easy to understand, to verify and to develop. The general methodology for designing such a system consists of decomposing it into a structured set of modules so that the modules can be understood, verified and developed individually, and so that the understanding/verification of the system can be derived from the understanding/verification of its modules. While many of the mechanisms in a computer system have been decomposed successfully into a structured set of modules, no technique has been proposed to organize the virtual memory mechanism of a system in such a way.The present paper proposes using type extension for that purpose. The virtaul memory mechanism consists of a set of type manager modules implementing abstract information containers. The structure of the mechanism reflects the structure of the containers that are implemented. While using type extension to organize a virtual memory mechanism is conceptually simple, it is hard to achieve in practice. All existing or proposed uses of type extension assume the existence of information containers that are uniformly accessible, can always be grown and are protected. Using type extension inside a virtual memory mechanism raises implementation problems since such containers are not implemented. Their implementation is precisely the objective of the virtual memory mechanism. In addition to explaining how type extension can be supported inside a virtual memory mechanism, the paper briefly discusses some aspects of its application to the reorganization of the kernal of a commercial, general-purpose, time-sharing system. It concludes by presenting some results of that case study concerning the organization of operating systems.
Jade
Authors: Witten Ian H. , Birtwistle Graham M. , Cleary John , Hill David R. , Levinson Danny , Lomow Greg , Neal Radford , Peterson Murray , Unger Brian W. , Wyvill Brian
Published: October 2004

The Jade research project is aimed at building an environment which comfortably supports the design, construction, and testing of distributed computer systems. This note is an informal project description which delimits the scope of the work and identifies the research problems which are tackled. Some design issues are discussed, and progress to date is described.
The Deadlock problem
Authors: Zöbel Dieter
Published: October 2004

The desire for a better utilisation of resources and an acceleration of computing introduced the concept of parallelism with all its difficulties. Soon the danger of eternal delays of processes was discovered and called deadlock. For almost twenty years a lot of publications have dealt with problems considering deadlocks or their environment.Here we want to give a classification of our collected publications. We do not claim that this collection is complete in any sense, but we hope to have found essential articles (underlined) for nearly all the different topics fitting under the title "Deadlock".This classification regards different aspects of the problem and cannot always be given unambigiously so that many publications are listed several times. We would appreciate to get knowledge of other interesting articles or textbooks to this theme.
Virtual memory transaction management
Authors: Stonebraker Michael
Published: October 2004

In this paper we examine the consequences of an operating system providing transaction management in an environment where files are bound into a user's address space. The discussion focuses on inherent limitations in providing concurrency control and crash recovery services in this environment and on hardware extensions needed to overcome these deficiencies.
An experiment using registers for fast message-based interprocess communication
Authors: Cheriton David R.
Published: October 2004

Message interprocess communication has appeal for structuring operating systems but has the reputation of being slow. Register architectures have advantages for fast sequential execution but are considered to increase context-switching costs. This note describes an experiment in which registers are used for transmitting messages in the V kernel, resulting in a factor of 3 improvement in elapsed time for local message transactions and a factor of 6 reduction in kernel time for the associated kernel operations.
Efficient commit protocols for the tree of processes model of distributed transactions
Authors: Mohan C. , Lindsay B.
Published: October 2004

This paper describes two efficient distributed transaction commit protocols, the Presumed Abort (PA) and Presumed Commit (PC) protocols, which have been implemented in the distributed data base system R* [DSHLM82, LHMWY83]. PA and PC are extensions of the well-known two-phase (2P) commit protocol [Gray78, Lamp80, LSGGL80]. PA is optimized for read-only transactions and a class of multi-site update transactions, and PC is optimized for other classes of multi-site update transactions. The optimizations result in reduced inter-site message traffic and log writes, and, consequently, a better response time for such transactions. We derive the new protocols in a step-wise fashion by modifying the 2P protocol.
A well structured parallel file system for PM
Authors: Braban Bruno , Schlenk Peter
Published: October 2004

PM is a new object-oriented methodology which allows a more structured approach to the specification and implementation of software for distributed and multiprocessor architectures. In order to evaluate the correctness and efficiency of the PM prototype implementation, it has been decided to build a highly parallel distributed file system as a first application.This paper outlines the design of this file system. Starting with the proposal of an overall structure for the system, we will then detail each type of object it will be made of and propose solutions in response to the classical problems encountered in the area of file systems, provision of a transaction mechanism and guarantee of the consistency of the users' data.