We propose a new intra-domain IP routing algorithm called trail blazer (TB) that alleviates network congestion by local decisions based on latency measurements collected by scout packets. TB is a member of a class of traffic-aware routing algorithms based on the behavior of ants. TB maintains in every router a probability table that controls the selection of outgoing links for a given destination. This table is modified by passing scout packets. Some scout packets follow existing high probability paths, and other scout packets explore new paths by making random "mistakes" in order to find detours around congested areas of the network. Scout packets do not have global knowledge of the network topology. Rather, they are influenced by probability trails left by previous scout packets, and leave a trail of updated probability information. TB is meant to be an extension of existing link-state protocols such as OSPF or IS-IS, which provide shortest-path information to initialize the probability table. Simulations of UDP traffic in congested networks show a reduction of packet drops by factors of 3.4-38.4 and 1.8-8.2, for single-path and multi-path shortest-path routing, respectively, with a bounded reordering window. Even though TB may cause packet reordering which may affect the congesting control mechanisms of TCP, TCP traffic sent over TB has a similar bandwidth to shortest-path routing. Simulation of a hybrid routing algorithm that routes TCP traffic over shortest paths and UDP traffic over TB show reduced interference between TCP and UDP traffic.

This paper introduces a cryptographic engine, Janus, which assists clients in establishing and maintaining secure and pseudonymous relationships with multiple servers. The setting is such that clients reside on a particular subnet (e.g., corporate intranet, ISP) and the servers reside anywhere on the Internet. The Janus engine allows each client-server relationship to use either weak or strong authentication on each interaction. At the same time, each interaction preserves privacy by neither revealing a clients true identity (except for the subnet) nor the set of servers with which a particular client interacts. Furthermore, clients do not need any secure long-term memory, enabling scalability and mobility. The interaction model extends to allow servers to send data back to clients via e-mail at a later date. Hence, our results complement the functionality of current network anonymity tools and remailers. The paper also describes the design and implementation of the Lucent Personalized Web Assistant (LPWA), which is a practical system that provides secure and pseudonymous relations with multiple servers on the Internet. LPWA employs the Janus function to generate site-specific personæ, which consist of alias usernames, passwords, and e-mail addresses.

Monitoring the location of customer equipment is an important problem in the direct broadcasting sateMte indw try.This is because the service providers wotdd We to pr~ vent unauthorized movement of a customer's set top terminal (STT) from a home to a pubtic venue, or acro~an international border, due to tious kancid, copyright and po~ticd issues.h this paper we study four schemw for detecting the movement of the an STT using the ~ting (or emerging) communication tiastructttre.We start with the currently used scheme which is based on the telephone network's ~ or Cm (cdlw-~) featurw, and show how it can be undermined.Then we suggest three new schem= which are more robust than the cder ~scheme one that that uses the Globrd Positioning System (GPS), one that uses the cefldar phone's enhanced 911 (E911) service, and one that mea-sur~the tim~Werenceof-arriti of the sat eMte's broadcast.We ~the accuracy, featur~and vtdnerabtities of ed scheme.We *O present possible attacks that Mow pirates to coned their movement when these schemw are employed._-.

RAIDs (Redundant Arrays of Independent Disks) are a set of disks organized to achieve parallel I/O to multiple disks and to provide tolerance of disk failures. RAIDs offer these advantages at the cost of additional space and additional disk I/O for writes. Previous methods of reducing this I/O overhead suffered from such problems as requiring periods during which data is reorganized and not available, destroying the physical locality of data, or weakening the RAID's fault-tolerance properties. We propose a new method called data logging which reduces the I/O overhead without requiring periodic downtime for reorganization. Instead, incremental maintenance can be performed concurrently with routine processing. This is particularly advantageous in applications requiring "24/spl times/7" uptime. Data logging preserves both physical locality of data and RAID fault tolerance. The major cost of our method is a moderate amount of nonvolatile RAM. This paper describes our method, as well as two schemes for efficient encoding of the information that must be stored in nonvolatile RAM.

A portable parallelization of the Cooley–Tukey FFT algorithm for MIMD multiprocessors is presented. The implementation uses the virtual machine for multiprocessors (VMMP) and PVM portable software packages. Since VMMP provides the same set of services on all target machines, a single version of the parallel FFT code was used for shared memory (25-processor Sequent Symmetry), shared bus (MOS-running distributed UNIX) and distributed memory multiprocessor (transputer network and 64-processor IBM SP2). It is accompanied with detailed performance analysis of the implementations. The algorithm achieved high efficiencies on all target machines. The analysis indicates that most overheads are caused by the target architecture and not by VMMP or PVM inefficiencies. The portability analysis of the FFT provides several important insights. On the message passing architecture, the parallel FFT algorithm can obtain linearly increasing speedup with respect to the number of processors with only a moderate increase in the problem size. The parallel FFT can be executed by any number of processors, but generally the number of processors is much less than the length of the input data. The results indicate that the parallel FFT is portable: it achieves very good speedups on either a shared memory multiprocessor with high memory bandwidth or on a message passing multiprocessor without any change in the programs. © 1998 John Wiley & Sons, Ltd.

In order to support multiple real-time applications on a single platform, ,the operating system must provide Quality of Service (&OS) guarantees so that the system resources can be provisioned among applications to achieve desired levels of predictable performance.The traditional QoS parameters include fairness, delay, and throughput.In this paper we introduce a new QoS criterion called cumulative service.The cumulative service criterion relates the total service obtained by a process under a scheduling policy to the ideal service that the process would have accumulated by executing on each resource at a reserued rate.We say that a scheuling policy provides a cumulative service guarantee if the performance of the real system differs from the ideal system by at most a constant amount.A cumulative service guarantee is vital for applications (e.g., a continous media file service) that require multiple resources and demand predictable aggregated throughput over aII these resources.E.xisting scheduling algorithms that guarantee traditional QoS paramaters do not provide cumulative service guarantees.We present a new scheduling algorithm called Move-To-Rear List Scheduling which provides a cumulative service guarantee as well as the traditional guarantees such as fairness (proportional sharing) and bounded delay.The complexity of MTR-LS is o(ln(n))where n is the number of processes.

The Portable Parallelizing Fortran Compiler (PPFC) is an additional component for the portable programming environment developed in Tel-Aviv University for scientific code. This environment supports portable and efficient programming of diverse MIMD multiprocessors, both distributed- and shared-memory. Till now this environment has consisted of two tools: the Virtual Machine for MultiProcessors (VMMP) and the Portable Parallelizing Pascal compiler (P3C). We have added the PPFC which is an automatic parallelizer compiler for the Fortran language. The compiler is fully automatic (does not require additional declarations to assist parallelization), which is characterized by loops operating on regular data structures, and produces efficient and portable code for a variety of multiprocessors from the same serial code. The parallel implementation uses the VMMP, which is a software package that provides a coherent set of services for explicitly parallel application programs running on diverse MIMD multiprocessors. VMMP is intended to simplify parallel program writing and to promote portable and efficient programming. The PPFC parallelized 12 out of the 24 Livermore Loops. It was also applied to parallelize all the 14 Fortran application programs that where parallelized by the P3C and achieved the same speed-ups and efficiencies. In most examples the PPFC achieved high speed-ups and efficiencies on all target multiprocessors. The PPFC emphasizes efficiency and code portability. Although PPFC employs a relatively simple data flow analysis, it produces efficient code for various widely used application programs.

Abstract The use of a massively parallel machine is aimed at the development of applications programs to solve most significant scientific, engineering, industrial and commercial problems. High‐performance computing technology has emerged as a powerful and indispensable aid to scientific and engineering research, product and process development, and all aspects of manufacturing. Such computational power can be achieved only by massively parallel computers. It also requires a new and more effective mode of interaction between the computational sciences and applications and those parts of computer science concerned with the development of algorithms and software. We are interested in using parallel processing to handle large numerical tasks such as linear algebra problems. Yet, programming such systems has proven itself to be very complicated, error‐prone and architecture‐specific. One successful method for alleviating this problem, a method that worked well in the case of the massively pipelined supercomputers, is to use subprogram libraries. These libraries are built to efficiently perform some basic operations, while hiding low‐level system specifics from the programmer. Efficiently porting a library to a new hardware, be it a vector machine or a shared memory or message passing based multiprocessor, is a major undertaking. It is a slow process that requires an intimate knowledge of the hardware features and optimization issues. We propose a scheme for the creation of portable implementations of such libraries. We present an implementation of BLAS (basic linear algebra subprograms), which is used as a standard linear algebra library. Our parallel implementation uses the virtual machine for multiprocessors (VMMP) (1990), which is a software package that provides a coherent set of services for explicitly parallel application programs running on diverse MIMD multiprocessors, both shared memory and message passing. VMMP is intended to simplify parallell program writing and to promote portable and efficient programming. Furthermore, it ensures high portability of application programs by implementating the same services on all target multiprocessors. Software created using this scheme is automatically efficient on both categories of MIMD machines, and on any hardware VMMP has been ported to. An additional level of abstraction is achieved using the programming language C++, an object‐oriented language. Eckel, Stroustrup, 1989, 1986). For the programmer who is using BLAS‐3, it is hiding both the data structures used to define linear algebra objects, and the parallel nature of the operations performed on these objects. We coded BLAS on top of VMMP. This code was run without any modifications on two shared memory machines‐the commercial Sequent Symmetry and the experimental Taunop. (The code should run on any machine the VMMP was ported onto, given the availability of a C++ compiler). Performance results for this implementation are given. The speed‐up of the BLAS‐3 routines, tested on 22 processors of the Sequent, was in the range of 8.68 to 15.89. Application programs (e.g. Cholesky factorization) using the library routines achieved similar efficiency.

The VMMP (virtual machine for multiprocessors) software package is presented. It provides a coherent set of services for parallel application programs running on diverse multiple input multiple data (MIMD) multiprocessors, including shared memory and message passing multiprocessors. The communication, synchronization, and data distribution requirements of parallel algorithms are analyzed. Related languages and tools are described. VMMP services are identified. VMMP implementation, coding and portability are discussed. Some measurements of the performance of VROMP application programs and VMMP overhead are given. Several hints for improving the performance of application programs are described.>