waashk/acm huggingface dataset:
implications of hierarchical n-body methods for multiprocessor architecture  we first examine the key architectural implications of realistically scaling a representative member of this important class of applications. using scaling methods that reflect the concerns of an application scientist leads to different conclusions than does naive scaling model, both the communication to computation ratio and the amount of cache memory per processor required for effective performance increase with scaling. we then examine the effect of a shared address space versus message passing as the communication abstraction. we show that the lack of a shared address space substantially increases the programming complexity and performance overheads of a message-passing implementation.  jaswinder pal singh
optimal implementation of the weakest failure detector for solving consensus (brief announcement)  unreliable failure detectors were introduced by chandra and toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. they showed how unreliable failure detectors can be used to solve the consensus problem in asynchronous systems. they also showed in [1] that one of the classes of failure detectors they defined, namely eventually strong ( s), is the weakest class allowing to solve consensus1.  this brief announcement presents a new algorithm implementing s. due to space limitation, the reader is referred to [4] for an in-depth presentation of the algorithm (system model, correctness proof, and performance analysis). here, we present the general idea of the algorithm and compare it with other algorithms implementing unreliable failure detectors.  the algorithm works as follows. we have n processes, p1, …, pn. initially, process p1 starts sending messages periodically to the rest of processes. the rest of processes initially trust p1, and wait for its messages. if a process does not receive a message within some timeout period from its trusted process, then it suspects its trusted process and takes the next process as its new trusted process. if a process trusts itself, then it starts sending messages periodically to its successors. otherwise, it just waits for periodical messages from its trusted process.  if, at some point, a process receives a message from a process pi such that pi precedes its trusted process, then it will trust pi again, increasing the value of its timeout period with respect to p< subscrpt>i.  with this algorithm, eventually all the correct processes will permanently trust the same correct process. this provides the eventual weak accuracy property required by s. by simply suspecting the rest of processes, we obtain the strong completeness property required by s.  our algorithm compares favorably with the algorithms proposed in [2] and [3] in terms of the number and size of the messages periodically sent and the total amount of information periodically exchanged. since algorithms implementing failure detectors need not necessarily be periodic, we propose a new and (we believe) more adequate performance measure, which we call eventual monitoring degree. informally, this measure counts the number of pairs of correct processes that will infinitely often communicate. we show that the proposed algorithm is optimal with respect to this measure. table 1 summarizes the comparison, where c denotes the number of correct processes and lfa denotes the proposed algorithm.  mikel larrea antonio fernández sergio arevalo
interleaving: a multithreading technique targeting multiprocessors and workstations  there is an increasing trend to use commodity microprocessors as the compute engines in large-scale multiprocessors. however, given that the majority of the microprocessors are sold in the workstation market, not in the multiprocessor market, it is only natural that architectural features that benefit only multiprocessors are less likely to be adopted in commodity microprocessors. in this paper, we explore multiple- context processors, an architectural technique proposed to hide the large memory latency in multiprocessors. we show that while current multiple-context designs work reasonably well for multiprocessors, they are ineffective in hiding the much shorter uniprocessor latencies using the limited parallelism found in workstation environments. we propose an alternative design that combines the best features of two existing approaches, and present simulation results that show it yields better performance for both multiprogrammed workloads on a workstation and parallel applications on a multiprocessor. by addressing the needs of the workstation environment, our proposal makes multiple contexts more attractive for commodity microprocessors.  james laudon anoop gupta mark horowitz
protocol implementation on the nectar communication processor  we have built a high-speed local-area network called nectar that uses programmable communication processors as host interfaces. in contrast to most protocol engines, our communication processors have a flexible runtime system that supports multiple transport protocols as well as application-specific activities. in particular, we have implemented the tcp/ip protocol suite and nectar-specific communication protocols on the communication processor. the nectar network currently has 25 hosts and has been in use for over a year.  the flexibility of our communication processor design does not compromise its performance. the latency of a remote procedure call between application tasks executing on two nectar hosts is less than 500 μsec. the same tasks can obtain a throughput of 28 mbit/sec using either tcp/ip or nectar-specific transport protocols. this throughput is limited by the vme bus that connects a host and its communication processor. application tasks executing on two communication processors can obtain 90 mbit/sec of the possible 100 mbit/sec physical bandwidth using nectar-specific transport protocols.  e. c. cooper p. a. steenkiste r. d. sansom b. d. zill
performance and implementation of clustered-ofdm for wireless communications  an elegant means by which high-speed burst wireless transmission can be accomplished with small amounts of overhead is through a novel technique referred to as clustered-ofdm (cimini et al., 1996). by using ofdm modulation with a long symbol interval, clustered-ofdm overcomes the complex and costly equalization requirements associated with single carrier systems. moreover, the need for highly linear power amplifiers typically required in ofdm systems is alleviated through the use of multiple transmit antennas combined with nonlinear coding. the clustering technique also leads to a natural implementation of transmit diversity. this paper reports on preliminary results on the performance of a clustered-ofdm system as well as the design and implementation of a clustered-ofdm transmitter. the prototype transmitter can deliver 7.5 mbps, and it is expected that this data rate could be easily tripled with existing technology in a second generation system. the paper also describes the architectural trade-offs made in order to reduce the hardware complexity of the boards as well as some experimental results showing the operation of the transmitter.  babak daneshrad leonard j. cimini manny carloni nelson sollenberger
a binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer we propose a scheme for _congestion avoidance_ in networksusing a connectionless protocol at the network layer. the schemeuses feedback from the network to the users of the network. theinteresting challenge for the scheme is to use a minimal amount offeedback (one bit in each packet) from the network to adjust theamount of traffic allowed into the network. the servers in thenetwork detect congestion and set a _congestion indication_bit on packets flowing in the forward direction. the congestionindication is communicated back to the users through the transportlevel acknowledgement.  the scheme is distributed, adapts to the dynamic state of thenetwork, converges to the optimal operating point, is quite simpleto implement, and has low overhead while operational. the schemealso addresses a very important aspect of _fairness_ in theservice provided to the various sources utilizing the network. thescheme attempts to maintain fairness in service provided tomultiple sources.  this paper presents the scheme and the analysis that went intothe choice of the various decision mechanisms. we also address theperformance of the scheme under transient changes in the networkand for pathological conditions.  k. k. ramakrishnan raj jain
dynamic rerouting tag schemes for the augmented data manipulator network  the augmented data manipulator (adm) is a multistage interconnection network designed for large-scale, parallel processing systems. this paper is an extension of an earlier work in which the use of the inverse adm (iadm) network in an mimd environment was investigated. dynamically rerouting messages to avoid busy or faulty links is explored for both the adm and iadm networks. several schemes are presented. in some cases, there is no increase in tag overhead, but the switching elements are more complex. in other cases, the size of the routing tag is increased by one bit, but the switching elements are not as complex. a new broadcasting capability is developed that allows one processor to send a message to any number of other processors (with some restriction on the destination addresses). finally, a scheme for dynamically rerouting a broadcast message is presented.  robert j. mcmillen howard jay siegel
twentenet: a lan with message priorities, design and performance considerations.  this paper discusses design and performance aspects of twentenet, one of the few implemented lans which offers a service based on message priorities. the medium access mechanism uses the csma/cd principle, however with a deterministic collision resolution method. these characteristics make twentenet suitable for real-time applications, as well as a mixture of real- time and non real-time applications. the general system structure is introduced followed by a detailed description of the priority access method. the performance of the system is shown for various traffic conditions and distributions of message priorities. the effect of system parameters, such as transmission rate, message length, cable length, and retry limits, is indicated.  i. g. niemegeers c. a. vissers
dynamic reservation multiple access (drma): a new multiple access scheme for personal communication systems (pcs)  to improve the spectrum efficiency of integrated voice and data services in personal communication system (pcs), several reservation-type multiple access schemes, such as packet reservation multiple access (prma), dynamic time division multiple access (d-tdma), resource auction multiple access (rama), etc., have been proposed. prma uses the data packet itself to make a channel reservation, and is inefficient in that each unsuccessful reservation wastes one slot. however, it does not have a fixed reservation overhead and offers shorter access delay. on the other hand, fixed reservation overhead is unavoidable in both rama and d-tdma. compared to d-tdma and prma, rama is superior in the sense that its slot assignment is independent of the traffic load. but its implementation is difficult. with these observations, a new reservation protocol, called dynamic reservation multiple access (drma), is proposed in this paper. with this new protocol, the success probability of channel access is greatly improved at the expense of slightly increased system complexity. it solves the problem of inefficiency in prma, but without introducing the fixed reservation overhead as in d-tdma and rama. in addition, it is more suited to the dynamic behavior of the integrated traffic because there is no fixed boundary between voice and data slots (which is mandatory in d-tdma and rama). our numerical results indicate that its performance is superior to the existing reservation protocols, especially in the integrated traffic scenario. moreover, the soft capacity feature is exhibited when the traffic load increases.  xiaoxin qiu victor o. k. li
the utility of feedback in layered multicast congestion control  layered multicast is a common approach for dissemination of audio and video in heterogeneous network environments. layered multicast schemes can be classified into two categories - feedback-based and feedback-free - depending on whether or not the scheme delivers feedback to the sender of the multicast session. advocates of feedback-based schemes claim that feedback is necessary to match the heterogeneous receiver capabilities efficiently. supporters of feedback-free schemes believe that feedback introduces significant complexity and that a moderate amount of additional layers can balance any benefit the feedback provides. surprisingly, there has been no systematic evaluation of these claims. this paper provides a quantitative comparison of feedback-based and feedback-free layered multicast schemes with respect to aligning the provided service to the capabilities of heterogeneous receivers. we discover realistic scenarios when feedback-free schemes require a very large number of additional layers to match the performance of feedback-based schemes. our studies also demonstrate that a light-weight feedback-based scheme can offer substantial improvement in performance over feedback-free schemes and can closely approximate the efficiency achieved by the optimal feedback-based scheme.  sergey gorinsky harrick vin
a novel load balancing scheme for the tele-traffic hot spot problem in cellular networks  we propose a dynamic load balancing scheme for the tele-traffic hot spot problem in cellular networks. a tele-traffic hot spot is a region of adjacent hot cells where the channel demand has exceeded a certain threshold. a hot spot is depicted as a stack of hexagonal `rings' of cells and is classified as complete if all cells within it are hot. otherwise it is termed incomplete. the rings containing all cold cells outside the hot spot are called `peripheral rings'. our load balancing scheme migrates channels through a structured borrowing mechanism from the cold cells within the `rings' or `peripheral rings' to the hot cells constituting the hot spot. a hot cell in `ring i' can only borrow a certain fixed number of channels from adjacent cells in `ring i+1'. we first propose a load balancing algorithm for a complete hot spot, which is then extended to the more general case of an incomplete hot spot. in the latter case, by further classifying a cell as cold safe, cold semi-safe or cold unsafe, a demand graph is constructed which describes the channel demand of each cell within the hot spot or its `peripheral rings' from its adjacent cells in the next outer ring. the channel borrowing algorithm works on the demand graph in a bottom up fashion, satisfying the demands of the cells in each subsequent inner ring until `ring 0' is reached. a markov chain model is first developed for a cell within a hot spot, the results of which are used to develop a similar model which captures the evolution of the entire hot spot region. detailed simulation experiments are conducted to evaluate the performance of our load balancing scheme. comparison with another well known load balancing strategy, known as cbwl, shows that under moderate and heavy tele-traffic conditions, a performance improvement as high as 12% in terms of call blockade is acheived by our load balancing scheme.  sajal k. das sanjoy k. sen rajeev jayaram
characterization of user mobility in low earth orbit mobile satellite systems  future mobile communication networks will provide a global coverage by means of constellations with nongeosynchronous satellites. multi - spot - beam antennas on satellites will allow a cellular coverage all over the earth. due to the unstationarity of satellites a call may require many cell changes during its lifetime. these passages will be managed by inter - beam handover procedures. this paper deals with the modeling of the user cell change process during call lifetime in low earth orbit - mobile satellite systems leo - msss . the analytical derivations presented in this study can be also applied to different mobility models provided that basic assumptions are fulfilled. this paper evaluates the impact of user mobility on the blocking performance of channel allocation techniques. moreover, the handover arrival process towards a cell has been characterized by using a usual statistical parameter for stationary point processes. finally, a performance analysis has been carried out on the basis of the classic teletraffic theory for telephone systems.  enrico del re romano fantacci giovanni giambene
location based services in a wireless wan using cellular digital packet data (cdpd)  this paper shows how a standard mobile data technology, cellular digital packet data (cdpd), can be used to localize mobile data users, and provide location based services. we present a location determination system that is handset-based. using cdpd and modem protocols, this system extracts the location of the users up to the cell site coverage in the network; it also exposes this location information to the application layer. we have implemented a prototype of the entire system; it works nationwide with mobile laptop and pocket pc users. the system is adequate for providing personalized location based service such as finding close businesses of interest, or business services such as tracking and fleet management, or traffic and re- routing applications, among others.  rittwik jana theodore johnson s. muthukrishnan andrea vitaletti
performance comparison of the cray-2 and cray x-mp/416 supercomputers  the serial and parallel performance of one of the world's fastest general purpose computers, the cray-2, is analyzed using the standard los alamos benchmark set plus codes adopted for parallel processing. for comparison, architectural and performance data are also given for the cray x-mp/416. factors affecting performance, such as memory bandwidth, size and access speed of memory, and software exploitation of hardware, are examined. the parallel processing environments of both machines are evaluated, and speed-up measurements for the parallel codes are given.  m. l. simmons h. j. wasserman
communication protocol design to facilitate re-use based on the object- oriented paradigm  the main motivation for the present work stems from the wide gap which exists between the research efforts devoted to developing formal descriptions for communication protocols and the effective development methodologies used in industrial implementations. we apply object-oriented (oo) modelling principles to networking protocols, exploring the potential for producing re-useable software modules by discovering the underlying generic class structures and behaviour. petri nets (pns) are used to derive re-useable model elements and a slightly modified ttcn notation is used for message sequence encoding. this demonstrates a formal, practical approach to the development of a protocol implementation through oo modelling. our utilisation of pns in the context of object based modelling allows for isolation of the behavioural characterisation of objects into a separate design plane, treated as a meta- level object control. this separation permits greater execution flexibility of the underlying object models. it is that very aspect of our modelling approach which can be utilised in software implementations where dynamically determined "re-programming" (i.e., change of procedures) is needed. for example, one of the requirements in wireless networking software is the ability to cope with ever-changing transmission/reception conditions and that, in turn, creates greatly varying error rates. similarly, handoff procedures create situations where dynamically determined change of operational modes is required. to illustrate the modelling concepts, the paper addresses the problem of inter- layer communication among multiple protocol entities (pes), assuming the standard iso/osi reference model. a generalised model called the inter-layer communication (ilc) model is proposed. an example of a pe based on the alternating-bit protocol (abp) is also discussed. the final example demonstrates how meta-level object control (pns) allows for the dynamic selection of different arq based algorithms.  andrew a. hanish tharam s. dillon
mobile facility location (extended abstract)  in this paper we investigate the location of mobile facilities (in l∞ and l2 metric) under the motion of clients. in particular, we present lower bounds and efficient algorithms for exact and approximate maintenance of 1-center and 1-median for a set of moving points in the plane. our algorithms are based on the kinetic framework introduced by basch et. al [5].  s. bespamyatnikh b. bhattacharya d. kirkpatrick m. segal
nomadicity: anytime, anywhere in a disconnected world  nomadic computing and communications is upon us. we are all nomads, but we lack the systems support to assist us in our various forms of mobility. in this paper, we discuss the vision of nomadicity, its technical challenges, and approaches to the resolution of these challenges. one of the key characteristics of this paradigmshift in the way we deal with the information is that we face dramatic and sudden changes in connectivity and latency. our systems must be "nomadically-enabled" in that mechanisms must be developed that deal with such changes in a natural and transparent fashion. currently, this is not the case in that our systems typically treat such changes as exceptions or failures; this is unacceptable. moreover, the industry is producing "piece parts" that are populating our desktops, briefcases and belt- hooks, but that do not interoperate with each other, in general. we require innovative and systemwide solutions to overcome these problems. such are the issues we address in this paper.  leonard kleinrock
the design philosophy of the darpa internet protocols the internet protocol suite, tcp/ip, was first proposed fifteen years ago. it was developed by the defense advanced research projects agency (darpa), and has been used widely in military and commercial systems. while there have been papers and specifications that describe how the protocols work, it is sometimes difficult to deduce from these why the protocol is as it is. for example, the internet protocol is based on a connectionless or datagram mode of service. the motivation for this has been greatly misunderstood. this paper attempts to capture some of the early reasoning which shaped the internet protocols. david d. clark
end-to-end congestion control for the internet: delays and stability under the assumption that queueing delays will eventually become small relative to propagation delays, we derive stability results for a fluid flow model of end- to-end internet congestion control. the theoretical results of the paper are intended to be decentralized and locally implemented: each end system needs knowledge only of its own round-trip delay. criteria for local stability and rate of convergence are completely characterized for a single resource, single user system. stability criteria are also described for networks where all users share the same round-trip delay. numerical experiments investigate extensions to more general networks. through simulations, we are able to evaluate the relative importance of queueing delays and propagation delays on network stability. finally, we suggest how these results may be used to design network resources. ramesh johari david kim hong tan