waashk/dblp huggingface dataset:
peer-to-peer communication across network address translators. network address translation (nat) causes well-known difficulties for peer-to-peer (p2p) communication, since the peers involved may not be reachable at any globally valid ip address. several nat traversal techniques are known, but their documentation is slim, and data about their robustness or relative merits is slimmer. this paper documents and analyzes one of the simplest but most robust and practical nat traversal techniques, commonly known as hole punching. hole punching is moderately well-understood for udp communication, but we show how it can be reliably used to set up peer-to-peer tcp streams as well. after gathering data on the reliability of this technique on a wide variety of deployed nats, we nd that about 82% of the nats tested support hole punching for udp, and about 64% support hole punching for tcp streams. as nat vendors become increasingly conscious of the needs of important p2p applications such as voice over ip and online gaming protocols, support for hole punching is likely to increase in the future.
large granularity cache coherence for intermittent connectivity. to function in mobile computing environments, distributed file systems must cope with networks that are slow, intermittent, or both. intermittence vitiates the effectiveness of callback-based cache coherence schemes in reducing client-server communication, because clients must validate files when connections are reestablished. in this paper we show how maintaining cache coherence at a large granularity alleviates this problem. we report on the implementation and performance of large granularity cache coherence for the coda file system. our measurements confirm the value of this technique. at 9.6 kbps, this technique takes only 4-20% of the time required by two other strategies to validate the cache for a sample of coda users. even at this speed, the network is effectively eliminated as the bottleneck for cache validation.
swarm: a log-structured storage system for linux. swarm [3] is a storage system for linux that provides scalable, reliable, and cost-effective data storage. at its lowest level, swarm implements a log-structured interface to a cluster of storage devices. above the log, swarm provides an infrastructure that allows high-level abstractions and functionality to be implemented easily and efficiently. this paper describes the design and implementation of swarm, paying particular attention to the swarm infrastructure and how it has been used to construct two storage systems: sting, a log-structured file system for linux, and ext2fs/swarm, a swarm-based version of the linux ext2 file system that runs unmodified above ablock device compatibility layer. the paper concludes with a discussion of our experiences using linux as a platform for research.
an overview of the netware operating system. the netware operating system is designed specifically to provide service to clients over a computer network. this design has resulted in a system that differs in several respects from more general-purpose operating systems. in addition to highlighting the design decisions that have led to these differences, this paper provides an overview of the netware operating system, with a detailed description of its kernel and its software-based approach to fault tolerance.
reducing the disk i/o of web proxy server caches. the dramatic increase of http traffic on the internet has resulted in wide-spread use of large caching proxy servers as critical internet infrastructure components. with continued growth the demand for larger caches and higher performance proxies grows as well. the common bottleneck of large caching proxy servers is disk i/o. in this paper we evaluate ways to reduce the amount of required disk i/o. first we compare the file system interactions of two existing web proxy servers, cern and squid. then we show how design adjustments to the current squid cache architecture can dramatically reduce disk i/o. our findings suggest two that strategies can significantly reduce disk i/o: (1) preserve locality of the http reference stream while translating these references into cache references, and (2) use virtual memory instead of the file system for objects smaller than the system page size. the evaluated techniques reduced disk i/o by 50% to 70%.
an analysis of process and memory models to support high-speed networking in a unix environment. in order to reap the benefits of high-speed networks, the performance of the host operating system must at least match that of the underlying network. a barrier to achieving high throughput is the cost of copying data within current host architectures. we present a performance comparison of three styles of network device driver designed for a conventional monolithic unix kernel. each driver performs a different number of copies. the zero-copy driver works by allowing the memory on the network adapter to be mapped directly into user address space. this maximises performance at the cost of: 1) breaking the semantics of existing network apis such as bsd sockets and svr4 tli; 2) pushing responsibility for network buffer management up from the kernel into the application layer. the single-copy driver works by copying data directly between user space and adapter memory obviating the need for an intermediate copy into kernel buffers in main memory. this approach can be made transparent to existing application code but, like the zero-copy case, relies on an adapter with a generous quantity of on-board memory for buffering network data. the two-copy driver is a conventional streams driver. the two-copy approach sacrifices performance for generality. we observe that the streams overhead for small packets is significant. we report on the benefit of the hardware cache in ameliorating the effect of the second copy, although we note that streaming network data through the cache reduces the level of cache residency seen by the rest of the system. a barrier to achieving low jitter is the non-deterministic nature of many operating system schedulers. we describe the implementation and report on the performance of a kernel streaming driver that allows data to be copied between a network adapter and another i/o device without involving the process scheduler. this provides performance benefits in terms of increased throughput, increased cpu availability and reduced jitter.
finding similar files in a large file system. we present a tool, called sif, for finding all similar files in a large file system. files are considered similar if they have significant number of common pieces, even if they are very different otherwise. for example, one file may be contained, possibly with some changes, in another file, or a file may be a reorganization of another file. the running time for finding all groups of similar files, even for as little as 25% similarity, is on the order of 500mb to 1gb an hour. the amount of similarity and several other customized parameters can be determined by the user at a post-processing stage, which is very fast. sif can also be used to very quickly identify all similar files to a query file using a preprocessed index. application of sif can be found in file management, information collecting (to remove duplicates), program reuse, file synchronization, data compression, and maybe even plagiarism detection.
glimpse: a tool to search through entire file systems. glimpse, which stands for global implicit search, provides indexing and query schemes for file systems. the novelty of glimpse is that it uses a very small index - in most cases 2-4% of the size of the text - and still allows very flexible full-text retrieval including boolean queries, approximate matching (i.e., allowing misspelling), and even searching for regular expressions. in a sense, glimpse extends agrep to entire file systems, while preserving most of its functionality and simplicity. query times are typically slower than with inverted indexes, but they are still fast enough for many applications. for example, it took 5 seconds of cpu time to find all 19 occurrences of usenix and winter in a file system containing 69mb of text spanning 4300 files. glimpse is particularly designed for personal information, such as one's own file system. the main characteristic of personal information is that it is non-uniform and includes many types of documents. an information retrieval system for personal information should support many types of queries, flexible interaction, low overhead, and customization, all these are important features of glimpse.
high performance dynamic linking through caching. the spring operating system provides high performance dynamic linking of program images. spring uses caching of both fixed-up program images and partially fixed-up shared libraries to make dynamic linking of program images efficient, to reduce the need for pic (position-independent code), and to improve page sharing between different program images running the same libraries. the result is that with program image caching, dynamically-linked programs have a start-up cost similar to statically-linked programs regardless of the number of unresolved symbols in dynamically-linked program images and shared libraries. in addition, with library and program image caching, we have reduced the need for pic and have increased page sharing.
a uniform name service for spring's unix environment. the spring operating system provides a uniform name service that can be used to associate any name with any object independent of the type of object, and allows arbitrary name spaces to be created and used as first-class objects. we have used this name service to unify the many unix® name spaces. objects that on unix systems are typically stored in separate name spaces are all accessible via a single uniform name service in spring. in addition, it is easy to add new spring objects that are not currently available in unix systems without modifying the underlying name service.
implementation of a reliable remote memory pager. traditional operating systems use magnetic disks as paging devices, even though the cost of a disk transfer measured in processor cycles continues to increase. in this paper we explore the use of remote main memory for paging. we describe the design, implementation and evaluation of a pager that uses main memory of remote workstations as a faster-than-disk paging device and provides reliability in case of single workstation failures. our pager has been implemented as a block device driver linked to the dec osf/1 operating system, without any modifications to the kernel code. using several test applications we measure the performance of remote memory paging over an ethernet interconnection network and find it to be faster than traditional disk paging. we evaluate the performance of various reliability policies and prove their feasibility even over low bandwidth networks, like ethernet. we conclude that the benefits of reliable remote memory paging in workstation clusters are significant today and will probably increase in the near future.
learning spam: simple techniques for freely-available software. the problem of automatically filtering out spam email using a classifier based on machine learning methods is of great recent interest. this paper gives an introduction to machine learning methods for spam filtering, reviewing some of the relevant ideas and work in the open source community. an overview of several feature detection and machine learning techniques for spam filtering is given. the authors' freely-available implementations of these techniques are discussed. the techniques' performance on several different corpora are evaluated. finally, some conclusions are drawn about the state of the art and about fruitful directions for spam filtering for freely-available unix software practitioners.
the design and implementation of a dcd device driver for unix. recent research results [1, 2] using simulation have demonstrated that disk caching disk (dcd), a new disk i/o architecture, has the potential for drastically improving disk write performance besides its higher reliability than traditional disk systems. to validate whether dcd can live up to its promise in the real world environment, we have designed and implemented a dcd device driver for the sun's solaris operating system. measured performance results are very promising. for metadata intensive benchmarks, our dcd driver outperforms the traditional system by a factor of 2-6 in terms of program execution speeds. the driver also guarantees file system integrity in the events of system crashes or failures. moreover, unlike other approaches such as log-structured file systems or soft updates, the dcd driver is completely transparent to the os. it does not require any changes to the os or the on-disk data layout. as a result, it can be used as a "drop-in" replacement for the traditional disk device driver in an existing system to obtain immediate performance improvement. our multi-layered device-driver approach significantly reduces the implementation overhead and improves portability.
an operating system in java for the lego mindstorms rcx microcontroller. the lego mindstorms is a lego bricks based robotics toy series produced by the lego group, based on the ideas developed at the massachusetts institute of technology in the programmable brick project. the heart of a lego robot, the rcx microcontroller, hosts a hitachi h8 microcontroller with 28 kilobytes of memory available for downloadable firmware and applications. in addition to the gui based programming environment provided by lego, a number of alternative programming environments have been developed for the rcx. however, these alternative programming environments are written in c, tightly bound to the hardware, and provide only relatively low level services. the strong hardware dependency makes it hard to debug programs; in practice, a hardware simulator is needed, and such a simulator does not yet exist in an open source form. in this paper we present a new type of operating system and new programming environments for the lego rcx brick. the operating system is written almost completely in java, and currently provides runtime support for java, c and c++ programs. in the case of java applications, simulation and debugging is relatively simple as it can be performed on a standard java virtual machine with just a small hardware simulation package.
the bsd packet filter: a new architecture for user-level packet capture. many versions of unix provide facilities for user-level packet capture, making possible the use of general purpose workstations for network monitoring. because network monitors run as user-level processes, packets must be copied across the kernel/user-space protection boundary. this copying can be minimized by deploying a kernel agent called a packet filter, which discards unwanted packets as early as possible. the original unix packet filter was designed around a stack-based filter evaluator that performs sub-optimally on current risc cpus. the bsd packet filter (bpf) uses a new, register-based filter evaluator that is up to 20 times faster than the original design. bpf alson uses a straighforward buffering strategy that makes its overall performance up to 100 times faster than sun's nit running on the same hardware.
glitz: hardware accelerated image compositing using opengl. in recent years 2d graphics applications and window systems tend to use more demanding graphics features such as alpha blending, image transformations and anti-aliasing. these features contribute to the user interfaces by making it possible to add more visual effects as well as new usable functionalities. all together it makes the graphical interface a more hospitable, as well as efficient, environment for the user. even with today's powerful computers these tasks constitute a heavy burden on the cpu. this is why many proprietary window systems have developed powerful 2d graphics engines to carry out these tasks by utilizing the acceleration capabilities in modern graphics hard-ware. we present glitz, an open source implementation of such a graphics engine, a portable 2d graphics library that can be used to render hardware accelerated graphics. glitz is layered on top of opengl and is designed to act as an additional backend for cairo, providing it with hardware accelerated output. furthermore, an effort has been made to investigate if the level of hardware acceleration provided by the x window system can be improved by using glitz to carry out its fundamental drawing operations.
mosix: how linux clusters solve real-world problems. as the complexity of software increases, the size of the software tends to increase as well, which incurs longer compilation and build cycles. in this paper, the authors present one example of how clusters of linux systems, using the mosix extensions for load monitoring and remote execution, were used to eliminate a performance bottleneck and to reduce the cost of building software. we present a discussion of our original software development cluster, an analysis of the performance issues in that cluster, and the development and modifications done to mosix and linux in order to produce a solution to our problem. we finish by presenting future developments that will enhance our cluster.
process labeled kernel profiling: a new facility to profile system activities. profiling tools that empirically measure the resource usage of a program have been widely used in program development. these tools have traditionally focused on the behavior of the target program. the target program, however, actually performs its job in collaboration with other programs, such as servers and an operating system kernel, in a modern system environment. process-labeled kernel profiling is a novel facility that measures and attributes the kernel resource consumption of programs benefiting from it. this facility, in conjunction with a conventional profiler, enables a programmer to grasp the resource consumption of programs from an overall system point of view. using this information, the programmer is better able to reduce overall resource consumption.
soft updates: a technique for eliminating most synchronous writes in the fast filesystem. traditionally, filesystem consistency has been maintained across system failures either by using synchronous writes to sequence dependent metadata updates or by using write-ahead logging to atomically group them. soft updates, an alternative to these approaches, is an implementation mechanism that tracks and enforces metadata update dependencies to ensure that the disk image is always kept consistent. the use of soft updates obviates the need for a separate log or for most synchronous writes. indeed, the ability of soft updates to aggregate many operations previously done individually and synchronously reduces the number of disk writes by 40 to 70% for file-intensive environments (e.g., program development, mail servers, etc.). in addition to performance enhancement, soft updates can also maintain better disk consistency. by ensuring that the only inconsistencies are unclaimed blocks or inodes, soft updates can eliminate the need to run a filesystem check program after every system crash. instead, the system is brought up immediately. when it is convenient, a background task can be run on the active filesystem to reclaim any lost blocks and inodes. this paper describes an implementation of soft updates and its incorporation into the 4.4bsd fast filesystem. it details the changes that were needed, both to the original research prototype and to the bsd system, to create a production-quality system. it also discusses the experiences, difficulties, and lessons learned in moving soft updates from research to reality; as is often the case, non-focal operations (e.g., fsck and "fsync") required rethinking and additional code. experiences with the resulting system validate the earlier research: soft updates integrates well with existing filesystems and enforces metadata dependencies with performance that is within a few percent of optimal.
lmbench: portable tools for performance analysis. lmbench is a micro-benchmark suite designed to focus attention on the basic building blocks of many common system applications, such as databases, simulations, software development, and networking. in almost all cases, the individual tests are the result of analysis and isolation of a customer's actual performance problem. these tools can be, and currently are, used to compare different system implementations from different vendors. in several cases, the benchmarks have uncovered previously unknown bugs and design flaws. the results have shown a strong correlation between memory system performance and overall performance. lmbench includes an extensible database of results from systems current as of late 1995.
the gnome canvas: a generic engine for structured graphics. the gnome canvas is a generic engine for structured graphics that offers a rich imaging model, high performance rendering, and a powerful high-level api. application programmers can use the canvas to create interactive graphics displays easily. many gnome applications use the canvas as their main display engine, some of them using the basic functionality provided by the canvas, and others by extending it for their particular needs. this paper describes the architecture of the canvas in detail and examines the way it is used in several gnome applications.
berkeley db. berkeley db is an open source embedded database system with a number of key advantages over comparable systems. it is simple to use, supports concurrent access by multiple users, and provides industrial-strength transaction support, including surviving system and disk crashes. this paper describes the design and technical features of berkeley db, the distribution, and its license.
protocol independence using the sockets api. the bsd sockets api provides abstractions and other features that help applications be protocol-independent. unfortunately, not all of the api is abstract and generic, and many programs do not use the apis in a protocol-independent way. this means that most network programs, in practice, only work with one layered set of communications protocols - usually tcp over ip. this hinders compatibility with older protocols and deployment of new ones, and is making ip a victim of its own success. during the course of next-generation ip development, implementors worked to convert protocol-dependent applications into protocol-independent applications. along the way, they defined new interfaces to fix some problems and they found a number of usage problems that lead to protocol dependencies. this paper explains many of the problems encountered, using examples from freely available software, and how to solve them. it also explains many of the new protocol-independent interfaces.
safety checking of kernel extensions. there are many places in operating systems today where extending the running kernel with small and fast extensions is an interesting thing to do. for example, the berkeley packet filter (bpf) allows code for a virtual machine to be uploaded intoa running kernel and executed at packet reception, allowing fairly arbitrary filtering of packets before they cross the expensive kernel to user interface. whatever mechanism is used needs to provide some reasonable guarantees about the safety of the resulting code, which makes this problem complex. this paper describes a simple x86 bytecode verifier that is intended to be used to verify that a small program that is to be loaded obeys a reasonable safety policy. for program constructs that it is able to reason about, it can verify that code does not execute privileged instructions, only accesses known memory locations, and terminates. it cannot reason about arbitrary programs, but can reason about simple programs and developers that know the prover's limitations can write their code to be recognizable by the verifier. the contribution of this work is to show that a very limited prover can operate on native machine code and can efficiently reason about a small but still interesting set of programs.