waashk/acm huggingface dataset:
stability of binary exponential backoff  binary exponential backoff is a randomized protocol for regulating transmissions on a multiple-access broadcast channel. ethernet, a local-area network, is built upon this protocol. the fundamental theoretical issue is stability: does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough? it is assumed n ≥ 2 stations share the channel, each having an infinite buffer where packets accumulate while the station attempts to transmit the first from the buffer. here, it is established that binary exponential backoff is stable if the sum of the arrival rates is sufficiently small. detailed results are obtained on which rates lead to stability when n = 2 stations share the channel. in passing, several other results are derived bearing on the efficiency of the conflict resolution process. simulation results are reported that, in particular, indicate alternative retransmission protocols can significantly improve performance.  jonathan goodman albert g. greenberg neal madras peter march
delegating remote operation execution in a mobile computing environment  remote operation execution is nowadays the most popular paradigm used to build distributed systems and applications. this success originates in the simplicity exhibited by programming along the client-server paradigm. unfortunately, connectivity and bandwidth restrictions defy the unchanged porting of this well known mechanisms to the mobile computing field. in this paper we present an approach that allows to develop applications which are tailored for the specific requirement of mobile computing, while retaining the simple and well understood remote execution paradigm. the approach provides the additional benefit that established services could easily be used from mobile platforms. the cornerstone of our approach is integrated linguistic support for dynamically delegating the execution and control of remote procedure calls (rpc) to a delegate located on the fixed part of the network. besides presenting the language constructs, we discuss the extensions to the rpc-based development process and the necessary run-time support. remote operation execution is nowadays the most popular paradigm used to build distributed systems and applications. this success originates in the simplicity exhibited by programming along the client-server paradigm. unfortunately, connectivity and bandwidth restrictions defy theunchanged porting of this well known mechanisms to the mobile computing field. in this paper we present an approach that allows to develop applications which are tailored for the specific requirement of mobile computing, while retaining the simple and well understood remote execution paradigm. the approach provides the additional benefit that established services could easily be used from mobile platforms. the cornerstone of our approach is integrated linguistic support for dynamically delegating the execution and control of remote procedure calls (rpc) to a delegate located on the fixed part of the network. besides presenting the language constructs, we discuss the extensions to the rpc-based development process and the necessary run-time support.  dietmar a. kottmann ralph wittmann markus posur
a graph-oriented mapping strategy for a hypercube  the mapping problem is the problem of implementing a computational task on a target architecture in order to maximize some performance metric. for a hypercube-interconnected multiprocessor, the mapping problem arises when the topology of a task graph is different from a hypercube. it is desirable to find a mapping of tasks to processors that minimizes average path length and hence interprocessor communication. the problem of finding an optimal mapping, however, has been proven to be np-complete. several different approaches have been taken to discover suitable mappings for a variety of target architectures. since the mapping problem is np-complete, approximation algorithms are used to find good mappings instead of optimal ones. usually, greedy and/or local search algorithms are introduced to approximate the optimal solutions. this paper presents a greedy mapping algorithm for hypercube interconnection structures, which utilizes the graph- oriented mapping strategy to map a communication graph to a hypercube. the strategy is compared to previous strategies for attacking the mapping problem. a simulation is performed to estimate both the worst-case bounds for the greedy mapping strategy and the average performance.  w-k. chen e. f. gehringer
improving ap1000 parallel computer performance with message communication  the performance of message-passing applications depends on cpu speed, communication throughput and latency, and message handling overhead. in this paper we investigate the effect of varying these parameters and applying techniques to reduce message handling overhead on the execution efficiency of ten different applications. using a message level simulator set up for the architecture of the ap1000, we showed that improving communication performance, especially message handling, improves total performance. if a cpu that is 32 times faster is provided, the total performance increases by less than ten times unless message handling overhead is reduced. overlapping computation with message reception improves performance significantly. we also discuss how to improve the ap1000 architecture.  takeshi horie kenichi hayashi toshiyuki shimizu hiroaki ishihata
prefetch unit for vector operations on scalar computers (abstract)  current caches are not adequate for vector operations. a new kind of support for vector operations, called prefetch unit, is designed to improve the performance of the scalar (sisd) processors. the prefetch unit can be used for any sisd architecutre and also for many kinds of mimd architectures. it may run in parallel and asynchronously with other parts of processor. it keeps trace of the history of memory references, and initializes rarely any superfluous prefetches.  ivan sklenar
the jitter time-stamp approach for clock recovery of real-time variable bit- rate traffic when multimedia streams arrive at the receiver, their temporal relationships may be distorted due to jitter. assuming the media stream is packetized, the jitter is then the packet's arrival time deviation from its expected arrival time. there are various ways to reduce jitter, which include synchronization at the application layer, or synchronization at the _asynchronous transfer mode_ (atm) _adaptation layer_ (aal). the new source rate recovery scheme called _jitter time-stamp_ (jts) provides synchronization at the _atm adaptation layer 2_ (aal2) which is used to carry variable bit- rate traffic such as compressed voice and video. jts is implemented, and experiments have shown that it is able to recover the source rate. weilian su ian f. akyildiz
distributed testing and measurement across the atlantic packet satellite network(satnet)  the analysis of the test and measurement of tcp/ip performance over the atlantic packet satellite network (satnet) is described. both the methodology and tools as well as the results and their analysis are discussed. because of the internetwork nature of the environment, the tests were designed to allow the satnet measurement taskforce to look at the effects of each component of the end-to-end path, e.g., local networks, gateways, satnet, and protocol layers. results are given for the ip service provided by satnet as a function of offered load and for tcp behavior as a function of offered load and the underlying ip service.  k. seo j. crowcroft p. spilling j. laws j. leddy
a quantitative analysis of cache policies for scalable network file systems  current network file system protocols rely heavily on a central server to coordinate file activity among client workstations. this central server can become a bottleneck that limits scalability for environments with large numbers of clients. in central server systems such as nfs and afs, all client writes, cache misses, and coherence messages are handled by the server. to keep up with this workload, expensive server machines are needed, configured with high-performance cpus, memory systems, and i/o channels. since the server stores all data, it must be physically capable of connecting to many disks. this reliance on a central server also makes current systems inappropriate for wide area network use where the network bandwidth to the server may be limited.  in this paper, we investigate the quantitative performance effect of moving as many of the server responsibilities as possible to client workstations to reduce the need for high-performance server machines. we have devised a cache protocol in which all data reside on clients and all data transfers proceed directly from client to client. the server is used only to coordinate these data transfers. this protocol is being incorporated as part of our experimental file system, xfs. we present results from a trace-driven simulation study of the protocol using traces from a 237 client nfs installation. we find that the xfs protocol reduces server load by more than a factor of six compared to afs without significantly affecting response time or file availability.  michael d. dahlin clifford j. mather randolph y. wang thomas e. anderson david a. patterson
meta-level architectures for component-based mobile computing  we present an approach to mobile-aware application development that integrates mobile-awareness into existing distributed component designs. our proposed mobile components encapsulate a context of distributed components that collaborate to fulfill a set of published application functions. the approach os based on a set of meta-level architectures for mobility. first, we present a reflective layered-adaptation model derived from a proposed set of dynamic adaptation architectures. then, we present a set of mobility-enhanced component services and corresponding object-oriented architectures for their realization. the approach is demonstrated with the development of a video delivery component. we show how mobile awareness can be integrated into an existing component-based design based on our proposed mobility-enhanced corba- based services.  arnel i. periquet eric c. lin
uniform theory of the shuffle-exchange type permutation networks  this paper presents the uniform theory for describing of the shuffle-exchange type permutation networks - the theory of ek stages. the use of this new approach is demonstrated by applying it to the flip, omega, and other incomplete permutation networks and to some complete networks /e.g. the beneš network/ as well. especially the paper deals with the p, 2p, and /2p 1/-stage networks, where p log2n and n is number of the inputs /or outputs/ of these networks.  františek soviš
the computational speed of supercomputers  problems related to the evaluation of computational speeds of supercomputers are discussed. measurements of sequential speeds, vector speeds, and asynchronous parallel processing speeds are presented. a simple model is developed that allows us to evaluate the workload-dependent effective speed of current systems such as vector computers and asynchronous parallel processing systems. results indicate that the effective speed of a supercomputer is severely limited by its slowest processing mode unless the fraction of the workload that has to be processed in this mode is negligibly small.  ingrid y. bucher
building a high-performance communication layer over virtual interface architecture on linux clusters  the virtual interface architecture (via) is an industry standard user-level communication architecture for cluster or system area networks. the via provides a protected, directly- accessible interface to a network hardware, removing the operating system from the critical communication path. although the via enables low-latency high- bandwidth communication, the application programming interface defined in the via specification lacks many high-level features.  in this paper, we develop a high performance communication layer over via, named sovia (sockets over via). our goal is to make the sovia layer as efficient as possible so that the performance of native via can be delivered to the application, while retaining the portable sockets semantics. we find that the single-threaded implementation with conditional sender-side buffering is effective in reducing latency. to increase bandwidth, we implement a flow control mechanism similar to the tcp's sliding window protocol. our flow control mechanism is enhanced further by adding delayed acknowledgments and the ability to combine small messages.  with these optimizations, sovia realizes comparable performance to native via, showing the latency of 10.5 _sec_ for 4-byte messages and the peak bandwidth of 814mbps on giganet's clan. the functional validity of sovia is verified by porting ftp (file transfer protocol) application over sovia.  jin-soo kim kangho kim sung-in jung
lan based distributed database management system architecture (laddbms) (abstract only)  the integration of the heterogeneous independent databases within the office should not adversely impact on the local autonomy, reliability or availability of data. it is thus necessary to allow for both fragmented and replicated data. most query processing strategies do not handle multiple copies or the processing of fragments or restrict them to the processing of disjoint fragments. these approaches are thus unsatisfactory for the office environment. the query processing algorithms in a distributed environment make use of the global directory schema; the global schema directory placement and maintenance is in itself a distributed database problem. we present an architecture of laddbms that is capable of handling both fragmented and replicated data and does not require the availability of a global directory. the query processing approach is based upon the self- identification of a 'best' node. a query is decomposed into disjunctive subqueries by the originator node and the subqueries are broadcast. each node examines if it is well placed to respond and if so takes on the task of the subquery evaluation. the evaluation is measured for performance and the node updates its query answering capabilities based on this evaluation.  t. s. narayanan
random oracles in constantipole: practical asynchronous byzantine agreement using cryptography (extended abstract)  byzantine agreement requires a set of parties in a distributed system to agree on a value even if some parties are corrupted. a new protocol for byzantine agreement in a completely asynchronous network is presented that makes use of cryptography, specifically of threshold signatures and coin-tossing protocols. these cryptographic protocols have practical and provably secure implementations in the "random oracle" model. in particular, a coin-tossing protocol based on the diffie-hellman problem is presented and analyzed.  the resulting asynchronous byzantine agreement protocol is both practical and nearly matches the known theoretical lower bounds. more precisely, it tolerates the maximum number of corrupted parties, runs in constant expected time, has message and communication complexity close to the maximum, and uses a trusted dealer only in a setup phase, after which it can process a virtually unlimited number of transactions. novel dual- threshold variants of both cryptographic protocols are used.  the protocol is formulated as a transaction processing service in a cryptographic security model, which differs from the standard information- theoretic formalization and may be of independent interest.  christian cachin klaus kursawe victor shoup
wavevideo - an integrated approach to adaptive wireless video  the transmission of wireless video in acceptable quality is only possible by following an end-to-end approach. wavevideo is an integrated, adaptive video coding architecture designed for heterogeneous wireless networks. it includes basic video compression algorithms based on wavelet transformations, an efficient channel coding, a filter architecture for receiver-based media scaling, and error-control methods to adapt video transmissions to the wireless environment. using a joint source/channel coding approach, wavevideo offers a high degree of error tolerance on noisy channels, still being competitive in terms of compression. adaptation to channel conditions and user requirements is implemented on three levels. the coding itself features spatial and temporal measures to conceal transmission errors. additionally, the amount of introduced error-control information is controlled by feedback. the video stream coding, applied to multicast capable networks, can serve different user's needs effeiciently at the same time by scaling the video stream in the network according to receivers' quality reqirements. the wavevideo architecture is unique in terms of its capability to use qos mapping and adaptation functions across all network nodes providing the same uniform interface.  george fankhauser marcel dasen nathalie weiler bernhard plattner burkhard stiller
a comparison of mechanisms for improving tcp performance over wireless links reliable transport protocols such as tcp are tuned to perform well in traditional networks where packet losses occur mostly because of congestion. however, networks with wireless and other lossy links also suffer from significant non-congestion-related losses due to reasons such as bit errors and handoffs. tcp responds to all losses by invoking congestion control and avoidance algorithms, resulting in degraded end-to-end performance in wireless and lossy systems. in this paper, we compare several schemes designed to improve the performance of tcp in such networks. these schemes are classified into three broad categories: end-to-end protocols, where the sender is aware of the wireless link; link-layer protocols, that provide local reliability; and split-connection protocols, that break the end-to-end connection into two parts at the base station. we present the results of several experiments performed in both lan and wan environments, using throughput and goodput as the metrics for comparison.our results show that a reliable link-layer protocol with some knowledge of tcp provides very good performance. furthermore, it is possible to achieve good performance without splitting the end-to-end connection at the base station. we also demonstrate that selective acknowledgments and explicit loss notifications result in significant performance improvements. hari balakrishnan venkata n. padmanabhan srinivasan seshan randy h. katz
increased capacity through hierarchical cellular structures with inter-layer reuse in an enhanced gsm radio network  in today's cellular networks it becomes harder to provide the resources for the increasing and fluctuating traffic demand exactly in the place and at the time where and when they are needed. moreover, frequency planning for a hierarchical cellular network, especially to cover indoor areas and hot-spots, is a complicated and expensive task. therefore, we study the ability of hierarchical cellular structures with inter-layer resuse to increase the capacity of a gsm (global system for mobile communications) radio network by applying total frequency hopping (t-fh) and adaptive frequency allocation (afa) as a strategy to reuse the macro- and microcell resources without frequency planning in indoor picocells. the presented interface analysis indicates a considerable interference reduction gain by t-fh in conjunction with afa, which can be used for carrying an additional indoor traffic of more than 300 erlang/km2, i.e., increasing the spectral capacity by over 50%, namely 33 erlang/km2/mhz. from these results we draw a number of general conclusions for the design of hierarchical cellular structures in future mobile radio networks. for example, we may conclude that they require reuse strategies that not only adapt to the current local interference situation, but additionally distribute the remaining interference to as many resources as possible. for a hierarchical gsm network this requirement is fulfilled by the t-fh/afa technique very well.  jurgen deissner gerhard p. fettweis
fast object-oriented procedure calls: lessons from the intel 432  as modular programming grows in importance, the efficiency of procedure calls assumes an ever more critical role in system performance. meanwhile, software designers are becoming more aware of the benefits of object-oriented programming in structuring large software systems. but object-oriented programming requires a good deal of support, which can best be distributed between the compiler and architectural levels. a major part of this support relates to the execution of procedure calls. must such support exact an unacceptable performance penalty? by considering the case of the intel 432, a prominent object-oriented architecture, we argue that it need not. the 432 provided all the facilities needed to support object orientation. though its procedure call was slow, the reasons were only tenuously related to object orientation. most of the inefficiency could be removed in future designs by the adoption of a few new mechanisms: stack-based allocation of contexts, a memory-clearing coprocessor, and the use of multiple register sets to hold addressing information. these proposals offer the prospect of an object- oriented procedure call that can, on average, be performed nearly as fast as an ordinary unprotected procedure call.  e. f. gehringer r. p. colwell
algorithms for energy-efficient multicasting in static ad hoc wireless networks in this paper we address the problem of multicasting in ad hoc wireless networks from the viewpoint of energy efficiency. we discuss the impact of the wireless medium on the multicasting problem and the fundamental trade-offs that arise. we propose and evaluate several algorithms for defining multicast trees for session (or connection-oriented) traffic when transceiver resources are limited. the algorithms select the relay nodes and the corresponding transmission power levels, and achieve different degrees of scalability and performance. we demonstrate that the incorporation of energy considerations into multicast algorithms can, indeed, result in improved energy efficiency. jeffrey e. wieselthier gam d. nguyen anthony ephremides
when the crc and tcp checksum disagree  traces of internet packets from the past two years show that between 1 packet in 1,100 and 1 packet in 32,000 fails the tcp checksum, even on links where link-level crcs should catch all but 1 in 4 billion errors. for certain situations, the rate of checksum failures can be even higher: in one hour-long test we observed a checksum failure of 1 packet in 400. we investigate why so many errors are observed, when link-level crcs should catch nearly all of them.  we have collected nearly 500,000 packets which failed the tcp or udp or ip checksum. this dataset shows the internet has a wide variety of error sources which can not be detected by link-level checks. we describe analysis tools that have identified nearly 100 different error patterns. categorizing packet errors, we can infer likely causes which explain roughly half the observed errors. the causes span the entire spectrum of a network stack, from memory errors to bugs in tcp.  after an analysis we conclude that the checksum will fail to detect errors for roughly 1 in 16 million to 10 billion packets. from our analysis of the cause of errors, we propose simple changes to several protocols which will decrease the rate of undetected error. even so, the highly non-random distribution of errors strongly suggests some applications should employ application-level checksums or equivalents.  jonathan stone craig partridge