waashk/acm huggingface dataset:
possibilities of using protocol converters for nir system construction volumes of information available from network information services have been increasing considerably in recent years. users' satisfaction with an information service depends very much on the quality of the network information retrieval (nir) system used to retrieve information. the construction of such a system involves two major development areas: user interface design and the implementation of nir protocols.in this paper we describe and discuss the possibilities of using formal methods of protocol converter design to construct the part of an nir system client that deals with network communication. if this approach is practicable it can make implementation of nir protocols more reliable and amenable to automation than traditional designs using general purpose programming languages. this will enable easy implementation of new nir protocols custom-tailored to specialized nir services, while the user interface remains the same for all these services.based on a simple example of implementing the gopher protocol client we conclude that the known formal methods of protocol converter design are generally not directly applicable for our approach. however, they could be used under certain circumstances when supplemented with other techniques which we propose in the discussion. sven ubik
a verified sliding window protocol with variable flow control  we present a verified sliding window protocol which uses modulo-n sequence numbers to achieve reliable flow-controlled data transfer between a source and a destination. communication channels are assumed to lose, duplicate and reorder messages in transit. the destination's data needs are represented by a receive window whose size can vary with time. the destination entity uses acknowledgement messages to inform the source entity of the current receive window size and the sequence number of the data word next expected. the source entity responds by sending segments of data words that lie within the allowed window. each data segment is accompanied by an identifying sequence number and the size of the data segment. the destination entity also uses selective acknowledgement and selective reject messages to inform the source entity of the reception or lack of reception, respectively, of out-of-sequence data segments. thus, this protocol is a proper extension of the arpanet's tcp. we have obtained the minimum value of n that ensures correct data transfer and flow control, in terms of the minimum message transmission time, the maximum message lifetime, and the maximum receive window size. the protocol imposes no constraints on the retransmissions of messages or on the data segment sizes; thus, any retransmission policy that optimizes the protocol's performance can be used.  a u shankar
floor acquisition multiple access (fama) in single-channel wireless networks  the fama-ncs protocol is introduced for wireless lans and ad-hoc networks that are based on a single channel and asynchronous transmissions (i.e., no time slotting). fama-ncs (for floor acquisition multiple access with non-persistent carrier sensing) guarantees that a single sender is able to send data packets free of collisions to a given receiver at any given time. fama-ncs is based on a three-way handshake between sender and receiver in which the sender uses non-persistent carrier sensing to transmit a request-to- send (rts) and the receiver sends a clear-to-send (cts) that lasts much longer than the rts to serve as a "busy tone" that forces all hidden nodes to back off long enough to allow a collision-free data packet to arrive at the receiver. it is shown that carrier sensing is needed to support collision-free transmissions in the presence of hidden terminals when nodes transmit rtss asynchronously. the throughput of fama-ncs is analyzed for single-channel networks with and without hidden terminals; the analysis shows that fama-ncs performs better than aloha, csma, and all prior proposals based on collision avoidance dialogues (e.g., maca, macaw, and ieee 802.11 dfwmac) in the presence of hidden terminals. simulation experiments are used to confirm the analytical results.  j. j. garcia-luna-aceves chane l. fullmer
simp (single instruction stream/multiple instruction pipelining): a novel high-speed single-processor architecture  simp is a novel multiple instruction-pipeline parallel architecture. it is targeted for enhancing the performance of sisd processors drastically by exploiting both temporal and spatial parallelisms, and for keeping program compatibility as well. degree of performance enhancement achieved by simp depends on; i) how to supply multiple instructions continuously, and ii) how to resolve data and control dependencies effectively. we have devised the outstanding techniques for instruction fetch and dependency resolution. the instruction fetch mechanism employs unique schemes of; i) prefetching multiple instructions with the help of branch prediction, ii) squashing instructions selectively, and iii) providing multiple conditional modes as a result. the dependency resolution mechanism permits out-of-order execution of sequential instruction stream. our out-of-order execution model is based on tomasulo's algorithm which has been used in single instruction-pipeline processors. however, it is greatly extended and accommodated to multiple instruction pipelining with; i) detecting and identifying multiple dependencies simultaneously, ii) alleviating the effects of control dependencies with both eager execution and advance execution, and iii) ensuring a precise machine state against branches and interrupts. by taking advantage of these techniques, simp is one of the most promising architectures toward the coming generation of high-speed single processors.  k. murakami n. irie s. tomita
the "worm" programs - early experience with a distributed computation  the "worm" programs were an experiment in the development of distributed computations: programs that span machine boundaries and also replicate themselves in idle machines. a "worm" is composed of multiple "segments," each running on a different machine. the underlying worm maintenance mechanisms are responsible for maintaining the worm---finding free machines when needed and replicating the program for each additional segment. these techniques were successfully used to support several real applications, ranging from a simple multimachine test program to a more sophisticated real-time animation system harnessing multiple machines.  john f. shoch jon a. hupp
a simulation study of the performance of the extra-stage cube and the augmented-shuffle exchange networks under faults  in this paper, we conducted a simulation study to compare the performance of the extra-stage cube(esc) and the augmented-shuffle exchange (ase) networks in the presence of multiple link failures. the main objective of this study is gain an insight as to which of these two networks can better support graceful degradation under varying network loads and link failure rates. to achieve this task, three pertormance metrics are introduced, these are throughput, message-delivery ratio, and average delay per message and three simulation experiments using the simulation package comnet ii.5 are designed.  the simulation results indicate that with respect to the three performance matrices, the esc network outperforms the ase for network size n≥32 and link mttf=0.75 hours. however, when the link mttf=0.12 hours, the asc network outperforms the esc network for n<64\\. in both cases, the esc network outperforms the ase network when n=64. this result appears to be directly related to the link complexities of the two networks. for large networks, the link complexity of the ase is much larger than that of the esc network and accounts for its poorer performance when n>32.  abdullah a. abonamah fadi n. sibai
best-effort versus reservations: a simple comparative analysis using a simple analytical model, this paper addresses the following question: should the internet retain its best-effort-only architecture, or should it adopt one that is reservation-capable? we characterize the differences between reservation- capable and best-effort-only networks in terms of application performance and total welfare. our analysis does not yield a definitive answer to the question we pose, since it would necessarily depend on unknowable factors such as the future cost of network bandwidth and the nature of the future traffic load. however, our model does reveal some interesting phenomena. first, in some circumstances, the amount of incremental bandwidth needed to make a best- effort-only network perform as well as a reservation capable one diverges as capacity increases. second, in some circumstances reservation-capable networks retain significant advantages over best-effort-only networks, no matter how cheap bandwidth becomes. lastly, we find bounds on the maximum performance advantage a reservation-capable network can achieve over best-effort architectures. lee breslau scott shenker
a function oriented corporate network  the itt/net is an internal corporate network built to satisfy the distributed programming requirements of itt technology and engineering communities. this paper describes the network: its goals, its architecture, its operational environment and prototype development activities.  the various issues involved in the construction of a corporate network based upon diverse, existing systems and communication methods are described in detail. the architectural and implementation decisions are discussed and justified. the programming process and the methodologies adopted are presented and some conclusions are drawn as to the practicality and usefulness of formal development methods in the context of this particular project.  p. s.-c. wang s. r. kimbleton
a simple multiple access protocol for metropolitan area networks  as lans/mans operate at higher speeds (100 mb/s-gb/s) and over longer distances (10's - 100's km) the access mechanism has to be chosen carefully so as to provide high utilization. protocols are available that operate efficiently at high speeds and long distances. we describe here a particularly simple access mechanism referred to as simple (s). performance is simulated under a range of traffic, physical lengths, number of stations and overload conditions. s is compared with both fasnet and the distributed queue dual bus (dqdb) schemes. it is almost as efficient as more complex protocols and its overload performance is well behaved.  j. o. limb
experience with test generation for real protocols  this paper presents results on the application of four protocol test sequence generation techniques (t-, u-, d-, and w-methods) to the nbs class 4 transport protocol (tp4). the ability of a test sequence to decide whether a protocol implementation conforms to its specification depend on the range of faults that it can capture. the study shows that a test sequence produced by the t-method has a poor fault detection capability whereas test sequences produced by the u-, d- and w-methods have comparable (superior to that for t-method) fault coverage on several classes of randomly generated machines. the lengths of test sequences produced by the four methods tend to be different. the length of a test sequence produced by the t-method (w-method) is the smallest (largest). the length of a test sequence from the u-method is smaller than that for the d-method and lengths for both are greater than that for the t-method and less than that for the w-method.  d. sidhu t. leung
alternative implementations of two-level adaptive branch prediction  as the issue rate and depth of pipelining of high performance superscalar processors increase, the importance of an excellent branch predictor becomes more vital to delivering the potential performance of a wide-issue, deep pipelined microarchitecture. we propose a new dynamic branch predictor (two- level adaptive branch prediction) that achieves substantially higher accuracy than any other scheme reported in the literature. the mechanism uses two levels of branch history information to make predictions, the history of the last k branches encountered, and the branch behavior for the last s occurrences of the specific pattern of these k branches. we have identified three variations of the two-level adaptive branch prediction, depending on how finely we resolve the history information gathered. we compute the hardware costs of implementing each of the three variations, and use these costs in evaluating their relative effectiveness. we measure the branch prediction accuracy of the three variations of two-level adaptive branch prediction, along with several other popular proposed dynamic and static prediction schemes, on the spec benchmarks. we show that the average prediction accuracy for two-level adaptive branch prediction is 97 percent, while the other known schemes achieve at most 94.4 percent average prediction accuracy. we measure the effectiveness of different prediction algorithms and different amounts of history and pattern information. we measure the costs of each variation to obtain the same prediction accuracy.  tse-yu yeh yale n. patt
towards an active network architecture active networks allow their users to inject customized programs into the nodes of the network. an extreme case, in which we are most interested, replaces packets with "capsules" - program fragments that are executed at each network router/switch they traverse.active architectures permit a massive increase in the sophistication of the computation that is performed within the network. they will enable new applications, especially those based on application-specific multicast, information fusion, and other services that leverage network-based computation and storage. furthermore, they will accelerate the pace of innovation by decoupling network services from the underlying hardware and allowing new services to be loaded into the infrastructure on demand.in this paper, we describe our vision of an active network architecture, outline our approach to its design, and survey the technologies that can be brought to bear on its implementation. we propose that the research community mount a joint effort to develop and deploy a wide area activenet. david l. tennenhouse david j. wetherall
performance analysis of four simd machines  this paper presents the results of an experiment to study the performance of four simd machines. the objectives of this study are to analyze the cost of regular communication on several simd machines and study its impact on the performance of two kernels. the machines are: a 32k processor cm2, a 16k processor mpp, a 16k processor maspar mp-1, and a 4k processor dap 610c. regular communication is exemplified, in this study, by the shift operation where all elements of an array are shifted some number of positions along an array dimension. the cost of shift operations on the four machines is measured and analyzed for several two-dimensional arrays. the study shows that shift cost varies significantly from one machine to another, and depends on several factors including network topology, communication bandwidth, and the compilation partitioning scheme. results also show that the communication overhead is quite significant on some of these machines even for nearest neighbor communication. finally, results from this study are useful for obtaining a rough estimate of the communication overhead for many algorithms on these machines.  rod fatoohi
design, implementation, and evaluation of a software-based real-time ethernet protocol distributed multimedia applications require performance guarantees from the underlying network subsystem. ethernet has been the dominant local area network architecture in the last decade, and we believe that it will remain popular because of its cost-effectiveness and the availability of higher-bandwidth ethernets. we present the design, implementation and evaluation of a software-based timed-token protocol called rether that provides real-time performance guarantees to multimedia applications without requiring any modifications to existing ethernet hardware. rether features a hybrid mode of operation to reduce the performance impact on non-real-time network traffic, a race-condition-free distributed admission control mechanism, and an efficient token-passing scheme that protects the network against token loss due to node failures or otherwise. to our knowledge, this is the first software implementation of a real-time protocol over existing ethernet hardware. performance measurements from experiments on a 10 mbps ethernet indicate that up to 60% of the raw bandwidth can be reserved without deteriorating the performance of non-real-time traffic. additional simulations for high bandwidth networks and faster workstation hardware indicate that the protocol allows reservation of a greater percentage of the available bandwidth. chitra venkatramani tzi-cker chiueh
analysis of a composite performance reliability measure for fault-tolerant systems  today's concomitant needs for higher computing power and reliability has increased the relevance of multiple-processor fault-tolerant systems. multiple functional units improve the raw performance (throughput, response time, etc.) of the system, and, as units fail, the system may continue to function albeit with degraded performance. such systems and other fault-tolerant systems are not adequately characterized by separate performance and reliability measures. a composite measure for the performance and reliability of a fault-tolerant system observed over a finite mission time is analyzed. a markov chain model is used for system state-space representation, and transient analysis is performed to obtain closed-form solutions for the density and moments of the composite measure. only failures that cannot be repaired until the end of the mission are modeled. the time spent in a specific system configuration is assumed to be large enough to permit the use of a hierarchical model and static measures to quantify the performance of the system in individual configurations. for a multiple- processor system, where performance measures are usually associated with and aggregated over many jobs, this is tantamount to assuming that the time to process a job is much smaller than the time between failures. an extension of the results to general acyclic markov chain models is included.  lorenzo donatiello balakrishna r. iyer
qosmic: quality of service sensitive multicast internet protocol in this paper, we present, qosmic, a multicast protocol for the internet that supports qos-sensitive routing, and minimizes the importance of _a priori configuration_ decisions (such as _core_ selection). the protocol is resource- efficient, robust, flexible, and scalable. in addition, our protocol is provably loop-free.our protocol starts with a resources-saving tree (shared tree) and individual receivers switch to a qos- competitive tree (source-based tree) when necessary. in both trees, the new destination is able to choose the most promising among several paths. an innovation is that we use dynamic routing information without relying on a link state exchange protocol to provide it. our protocol limits the effect of pre-configuration decisions drastically, by separating the management from the data transfer functions; administrative routers are not necessarily part of the tree. this separation increases the robustness, and flexibility of the protocol. furthermore, qosmic is able to adapt dynamically to the conditions of the network.the qosmic protocol introduces several new ideas that make it more flexible than other protocols proposed to date. in fact, many of the other protocols, (such as yam, pimsm, bgmp, cbt) can be seen as special cases of qosmic. this paper presents the motivation behind, and the design of qosmic, and provides both analytical and experimental results to support our claims. michalis faloutsos anindo banerjea rajesh pankaj
multiprocessor hardware: an architectural overview  the subject of multiprocessor computer systems has been discussed almost since the inception of the modern digital computer in its uniprocessor form. the motivation for multiprocessor system research and development activity arises from a consideration of one or more of the following factors:  throughput  flexibility  extendability  price/performance  availability  reliability  fault tolerance.  while any one of these factors may be the central issue, it should not be construed that these factors are disjoint. quite the contrary, each may have a subtle, nonobvious effect on any multiprocessor system design.  john tartar
mobile computing: dataman project perspective  the objective of mobile computing is to develop system and application level software for small, battery powered terminals equipped with the wireless network connection. there is a rapidly growing interest in this field with companies spending billions of dollars developing technology and buying spectrum in the recent pcs auctions. in this paper we offer a perspective of mobile computing from the standpoint of our own research project at rutgers university. the dataman project (t.imielinski as project director and b.r.badrinath as the codirector) is funded by arpa(within glomoprogram), and two awards from nsf as well as industry support through the industry sponsored wireless information networks laboratory (winlab).  tomasz imielinski
factors affecting the performance of distributed applications  a major reason for the rarity of distributed applications, despite the proliferation of networks, is the sensitivity of their performance to various aspects of the network environment. contrary to much popular opinion, we demonstrate that cpu speed remains the predominant factor. with respect to network issues, we focus on two approaches to performance enhancement: (1) improving the performance of reliable, byte-stream protocols such as tcp; (2) the use of high-level protocols that reduce the frequency and volume of communication.  keith a. lantz william i. nowicki marvin m. theimer
software implementation strategies for power-conscious systems a variety of systems with possibly embedded computing power, such as small portable robots, hand-held computer, and automated vehicles, have power supply constraints. their batteries generally last only for a few hours before being replaced or recharged. it is important that all design efforts are made to conserve power in those systems. energy consumption in a system can be reduced using a number of techniques, such as low-power electronics, architecture-level power reduction, compiler techniques, to name just a few. however, energy conservation at the application software-level has not yet been explored. in this paper, we show the impact of various software implementation techniques on energy saving. based on the observation that different instructions of a processor cost different amount of energy, we propose three energy saving strategies, namely (i) assigning live variables to registers, (ii) avoiding repetitive address computations, and (iii) minimizing memory accesses. we also study how a variety of algorithm design and implementation techniques affect energy consumption. in particular, we focus on the following aspects: (i) recursive versus iterative (with stacks and without stacks), (ii) indifferent representations of the same algorithms, (iii) different algorithms --- with identical asymptotic complexity --- for the same problem, and (iv) different input representations. we demonstrate the energy saving capabilities of these approaches by studying a variety of applications related to power-conscious systems, such as sorting, pattern matching, matrix operations, depth-first search, and dynamic programming. from our experimental results, we conclude that by suitably choosing an algorithm for a problem and applying the energy saving techniques, energy savings in excess of 60% can be achieved. kshirasagar naik david s. l. wei